头像

Florentino




离线:6小时前



// 删除魔法.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;
int n;
char a[602];
int sum = 0;
int res = 0;
int dp[700][700];  //dp[i][j]记录i到j的最小删除步数
int DP(int l,int r) 
{
    if (dp[l][r] != -1) return  dp[l][r];  //不等于-1(已经计算过)返回dp[l][r]
    if (l == r)return 1; 
    if (l > r)return 0;
    int res;
        res = DP(l + 1, r) + 1;  //第一个元素单独删除
    int i;
    for (i = l + 1; i <= r; i++) {  //遍历,寻找最少的删除步数
        if (a[i] == a[l]) {
            res = min(res, DP(l + 1, i - 1) + DP(i, r));
        }
    }
    dp[l][r] = res;  //赋值,得到dp[l][r]的值
    return res;
}
int main()
{
    cin >> n;
    char c = getchar();
    char last = ' ';
    memset(dp, -1, sizeof dp);

    for (int i = 1; i <= n; i++) {
        scanf("%c", &c);
        if (c != last) {
            sum++;
            a[sum] = c;
        }
        last = c;
    }
    cout << DP(1, sum)<<endl;
    /*for (int i = 0; i <= 50; i++) {
        for (int j = 0; j <= 10; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }*/
}



int  getless(int temp) {
    int l = 1, r = maxp_num;
    while (l < r) {
        int mid = (l + r) / 2;
        if (prime[mid] > temp) {
            r = mid - 1;
        }
        else if (prime[mid] == temp)
        {
            break;
        }
        else {
            l = mid + 1;
        }
    }

    int mid = (l + r) / 2;
    //cout << a[mid]<<endl;
    if (prime[mid] > temp) {
        mid--;
    }
    return mid;
}



#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N];
//f[i]表示以第i个数结尾的最长上升序列的长度
int main()
{
    cin >> n ;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    int res = 0;
    for (int i = 1; i <= n; i ++ ){
        f[i] = 1;    //初始化为1,(当之前没有数字比他大的时候)
        for (int j = 1; j < i; j ++ )
            if (a[i] > a[j])  //找第i个数之前所有的数字,若有比它小的,那么取f[i]和f[j]+1的最大值
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}



整体思路,先把所有的数字设置为1(素数),之后遍历,若等于1,即为素数,若不为1,则是合数。

每次遍历一个新的数,要把之前所有的素数与他相乘,把得到的结果设置为0(合数)。

注意最后要

if(i % prime[j] == 0)//i中也含有Prime[j]这个因子
    break; //重要步骤。见原理

因为如果i包含有质数prime[j] ,那么之前这个i已经被设置为质数了,所以直接退出即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include<iomanip>
#include<fstream>
using namespace std;
int n,q;
bool isprime[100000010];
int prime[1000010];
int num[100010];
int main ()
{
    cin>>n>>q;
    int cnt=0;

    memset(isprime,1,sizeof isprime);
    isprime[1]=0;
    for (int i=2;i<=n;i++){
        if (isprime[i]==1){
            cnt++;
            prime[cnt]=i;
        }
        for (int j=1;j<=cnt&& i*prime[j]<=n;j++){
            isprime[i*prime[j]]=0;
            if(i % prime[j] == 0)//i中也含有Prime[j]这个因子
                break; //重要步骤。见原理
        }
    }
    int d;
    for (int i=1;i<=q;i++){
        scanf("%d",&d);
        printf("%d\n", prime[d]);
    }

    return 0;
}




典型的dfs问题。

分析解决dfs这类问题的关键所在是:
1、(层)确定递归的层是什么:比如在本问题中,递归的层就是将要进栈的车的序号,dfs(x)表示第x个车等待入栈

2、(类)确定分类:在当前位置和状态,所有可能出现的情况,一般是两种:比如当前位置选或者不选。在本题中,就是分成栈顶出栈(依旧在这一层)和元素入栈(进入下一层)。同时,要记得回溯。

3、(停)确定停止条件:在层数达到最后一层确定如何停止(到达最后一层,只输出20个答案)

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 26;
int n;    //n为列车数量
int st[N]; //所有元素入栈后,栈中的元素 
int ans[N]; //所有元素入栈后,已经出栈的元素序列 
int top = 0;
int t = 0;
int num = 0;
void z(int x)    //x表示第x个元素等待入栈 
{
    if (x == n + 1) { //遍历到最后一位
        if (++num > 20) return;  //数目大于20,返回
        for (int i = 1; i <= t; i++) printf("%d", ans[i]);  //输出 (所有元素入栈后,已经出栈的元素序列 ) 
        for (int i = top; i ; i -- ) printf("%d", st[i]);  //输出 (所有元素入栈后,栈中的元素 ),从栈顶到栈底 
        cout << endl; 
        return;
    }
    //两种可能性:1、栈顶元素出栈;2、元素入栈 
    if (top) {      //1、栈顶元素出栈;
                                //如果栈顶不为空,即栈中没有元素 
        ans[++t] = st[top--];   // 出栈的元素,多一个栈顶元素 
        z(x);                   //还是遍历这一位 
        st[++top] = ans[t--];   //回溯 
    }
    st[++top] = x;    //栈顶加一个元素 
    z(x + 1);           //遍历下一个 
    --top;              //回溯
}
int main() 
{
    cin >> n;
    z(1);    //输出结果,从列车1开始
    return 0;
}





#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int L, R, C;
const int N = 110;
typedef struct point {
    int x, y, z;
}point;
point start, END;
int dis[N][N][N];
char g[N][N][N];
int bfs() {
    queue<point> q;
    q.push(start);
    memset(dis,-1,sizeof dis);
    dis[start.x][start.y][start.z] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        int dx[] = {1,-1,0,0,0,0};
        int dy[] = {0,0,1,-1,0,0};
        int dz[] = {0,0,0,0,1,-1};
        for (int i = 0; i < 6; i++) {
            int X = dx[i] + t.x;
            int Y = dy[i] + t.y;
            int Z = dz[i] + t.z;
            if (dis[X][Y][Z] != -1)continue;
            if (g[X][Y][Z] == '#')continue;
            if (X<=0 || X>L || Y<=0 || Y>R || Z<=0 || Z>C)continue;
            dis[X][Y][Z] = dis[t.x][t.y][t.z] + 1;
            if (END.x == X && END.y == Y && END.z == Z)return dis[X][Y][Z];
            q.push({ X,Y,Z });
        }
    }
    return -1;
}
int main()
{
    while (1) {
        scanf("%d%d%d",&L,&R,&C);
        if (L == 0 && R == 0 && C == 0) {
            break;
        }
        for (int i = 1; i <= L; i++) {
            for (int j = 1; j <= R; j++) {
                for (int k = 1; k <= C; k++) {
                    cin >> g[i][j][k];
                    if (g[i][j][k] == 'S') {
                        start = {i,j,k};
                    }
                    else if (g[i][j][k] == 'E') {
                        END = { i,j,k };
                    }
                }
            }
        }
        int d = bfs();
        if (d == -1) {
            printf("Trapped!\n");
        }
        else {
            printf("Escaped in %d minute(s).\n",d);
        }
    }
    return 0;
}




#define _CRT_SECURE_NO_WARNINGS 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<cmath> 
using namespace std; 
const int MAXN = 11; 
//dp[S][k]表示现在所选的状态集合为S,当前所选的数,组成的数字对d取余后的值为k,这样就可以转移了。
//首先枚举所有的状态S,然后再枚举所有没有被选的数j,再枚举余数k即可转移。 
int T, d, a[MAXN], cnt, dp[1 << MAXN][1002]; 
bool b[MAXN];
char s[MAXN];
int PowTwo(int width)  //2的width次方 
{     
    return 1 << width;    
}     
int main() 
{ 
    scanf("%d", &T);  
    int len; 
    while (T--)  
    { 
        memset(dp, 0, sizeof(dp));   //dp数组清零 
        scanf("%s%d", s + 1, &d);   //输入串和除数d 
        len = strlen(s + 1);       //串的长度 
        cnt = 0; 
        for ( int i = 1; i <= len; i++) {  //register使用cpu中央处理器,更加快 
            a[i] = s[i] - '0';     //把所有数字存一下 
        } 
        dp[0][0] = 1;       //赋初值 
        //   1<<len== 2^len    
        for ( int S = 0; S < PowTwo(len)- 1; S++) { //S表示当前所选的状态集合,0 ———— 2^len - 1
            memset(b, 0, sizeof(b));          //注意清零 
            for ( int j = 1; j <= len; j++){     // 1————len
                if (   !( S & PowTwo(j - 1) )  &&  ! b[a[j]]) {  
                //S按位与2^(j-1),按位与1左移j-1位等于0,并且 b[a[j]]=0,没用过 
                    //如果a[j]已经转移过就不能继续转移了,j表示遍历s中的各位数字。 
                    b[ a[j] ] = 1;   //转移了      
                    for ( int k = 0; k < d; k ++ ) {  //k表示对d取余后的数 
                        dp[ S | 1<<(j-1)  ][  (  k * 10 + a[j]  ) % d ] += dp[S][k]; 
                        //符号|是按位或,S按位或2^(j-1)   
                    }  
                } 
            } 
        } 
        printf("%d\n", dp[PowTwo(len) - 1][0]); 
    } 
    return 0; 
} 



Florentino
1个月前

之后写




Florentino
1个月前

在一段k+1的数字中,一定有一个数字是删除的,现在逆向思维,我们要计算出逆向过程中,即计算出删除最小的和是多少。
利用单调队列进行辅助

# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# include <cmath>
# include <ctime>
# define R register
# define LL long long

using namespace std;

LL tot,d,n,k;
LL p[100010],head = 1,tail = 1;
LL q[100010],f[100010],ans;

inline void in(R LL &a){   //输入部分的处理
    R char c = getchar();R LL x=0,f=1;
    while(!isdigit(c)){if(c == '-') f=-1; c  =getchar();}
    while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
    a = x*f;
}

inline void maxx(R LL &a,const LL b){a>b? 0:a=b;}

inline LL yg(){
    // freopen("bronlily.in","r",stdin);
    // freopen("bronlily.out","w",stdout);
    in(n),in(k);
    for(R int i=1; i<=n; ++i)
    {
        in(d);
        tot += d;   //总数记录
        f[i] = q[head]+1LL*d;  //f[i]表示前i个数删除的最小的和

        //加上d,这里是有点晕的,但是应该可以这么想:因为之前head=1,所以 q[head]=0,不影响,
        //当head后面开始递增,说明距离已经拉大 ,就需要再加上d
        //理解为:前面没加,后面距离变大,开始加 

        while(head<=tail&&q[tail]>=f[i]) tail--;  //head<=tail,说明是有元素的,并且尾部元素大于f[i]说明,尾部元素不可能是最小的,出队
        q[++tail] = f[i],p[tail] = i;   //f[i]入队
        while(head<=tail&&p[head]<i-k) head++;  //如果队首的位置太远,需要满足小于k
    }
    for(R int i=n-k; i<=n; ++i) maxx(ans,1LL*tot-1LL*f[i]); //找到最后k个f[i]元素中最小的,即是答案
    printf("%lld",ans);
    return 0;
}

LL youngsc = yg();
int main(){;}





Florentino
1个月前

单调队列有两个性质
1、队列中的元素其对应在原来的列表中的顺序必须是单调递增的。
2、队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以)。

8 3
1 3 -1 -3 5 3 6 7
下文中我们用q来表示单调队列,p来表示其所对应的在原列表里的序号。

由于此时队中没有一个元素,我们直接令1进队。此时,q={1},p={1}。

现在3面临着抉择。下面基于这样一个思想:假如把3放进去,如果后面2个数都比它大,那么3在其有生之年就有可能成为最小的。此时,q={1,3},p={1,2}

下面出现了-1。队尾元素3比-1大,那么意味着只要-1进队,那么3在其有生之年必定成为不了最小值,原因很明显:因为当下面3被框起来,那么-1也一定被框起来,所以3永远不能当最小值。所以,3从队尾出队。同理,1从队尾出队。最后-1进队,此时q={-1},p={3}

出现-3,同上面分析,-1>-3,-1从队尾出队,-3从队尾进队。q={-3},p={4}。

出现5,因为5>-3,同第二条分析,5在有生之年还是有希望的,所以5进队。此时,q={-3,5},p={4,5}

出现3。3先与队尾的5比较,3<5,按照第3条的分析,5从队尾出队。3再与-3比较,同第二条分析,3进队。此时,q={-3,3},p={4,6}

出现6。6与3比较,因为3<6,所以3不必出队。由于3以前元素都<3,所以不必再比较,6进队。因为-3此时已经在滑动窗口之外,所以-3从队首出队。此时,q={3,6},p={6,7}

出现7。队尾元素6小于7,7进队。此时,q={3,6,7},p={6,7,8}。

那么,我们对单调队列的基本操作已经分析完毕。因为单调队列中元素大小单调递*(增/减/自定义比较),因此,队首元素必定是最值。按题意输出即可。

#include<cstdio>
#include<cstring>
using namespace std;
struct Monotone_queue
{
    static const int maxn = 1000001;
    int n, k, a[maxn];
    int q[maxn], head, tail, p[maxn];//同题目叙述一样,q是单调队列,p是对应编号。
    void read(){
        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
    }//读入不必说了
    void monotone_max()//单调最大值
    {
        head = 1;
        tail = 0;
        for (int i = 1; i <= n; ++i)
        {
            while (head <= tail && q[tail] <= a[i])
                tail--;
            q[++tail] = a[i];
            p[tail] = i;
            while (p[head] <= i - k)
                head++;
            if (i >= k)printf("%d ", q[head]);
        }
        printf("\n");
    }
    void monotone_min(){
        head = 1;
        tail = 0;
        //为啥要这样呢?因为head要严格对应首元素,tail要严格对应尾元素,
        //所以当tail>=head时,说明有元素。而一开始队列为空,说一要这样赋值。其实这跟普通队列一样。
        for (int i = 1; i <= n; ++i) {
            //a[i]表示当前要处理的值
            while (head <= tail && q[tail] >= a[i]) {
                tail--; //只要队列里有元素,并且尾元素比待处理值大
                //即表示尾元素已经不可能出场,所以出队。直到尾元素小于待处理值,满足"单调"。
            }       
            q[++tail] = a[i];   //待处理值入队
            p[tail] = i;        //同时存下其编号
            while (p[head] <= i - k)
                head++;       //如果队首元素已经"过时",出队。
            if (i >= k)printf("%d ", q[head]);
            //输出最值,即队首元素。i>=k表示该输出,至于why就自己看题目。
        }
        printf("\n");
    }
}worker;
int main()
{
    worker.read();
    worker.monotone_min();
    worker.monotone_max();
    return 0;
}