题目给你蓝,红问你哪种大的更多一些?首先我们比较大小肯定会考虑最高位,然后考虑次高位,但是这些又有什么用呢,直接比较蓝红的数量就行了.

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+500;
int w[N];
char s1[N],s2[N];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        scanf("%s",s1+1);
        scanf("%s",s2+1);
        int num1=0,num2=0;
        for(int i=1;i<=n;i++) 
        {
            if(s1[i]>s2[i])    num1++;
            else if(s1[i]<s2[i])    num2++;
        }
        if(num1>num2)    puts("RED");
        else if(num1==num2)    puts("EQUAL");
        else                puts("BLUE");
    }
    return 0;
}


考虑合法的情况,就是按题意说的,每次你选择一次上下,下次只能选择左右,你选择一次左右,那么下次只能选择左右.所以可知上下的数量和左右数量的绝对值不会超过1,所以我们就知道,假如给你次操作,左右的操作和是的,上下的操作和为的,那么我们不妨枚举左的操作次数,和上的操作次数,这样,右的操作次数和下的操作次数就已知了.如此即可解决此问题,我们这里为了简单,用set记录点的数量.

#include <bits/stdc++.h>
using namespace std;
set<pair<int,int> >ans;
int main()
{
    int n;cin>>n;
    int x=n/2,y=n-x;
    for(int i=0;i<=x;i++)//上 
    {
        for(int j=0;j<=y;j++)//右 
        {
            int down=(x-i);int left=(y-j);
            ans.insert({j-left,i-down});
        }
    }swap(x,y);
    for(int i=0;i<=x;i++)//上 
    {
        for(int j=0;j<=y;j++)//右 
        {
            int down=(x-i);int left=(y-j);
            ans.insert({j-left,i-down});
        }
    }cout<<ans.size()<<endl;
    return 0;
}


考虑gcd的辗转相除法公式有,如此推至n项即是
然后我们每次都是给区间加上一个确定的数,我们可以观察2-n项会发现,他们的gcd是不变的,我们可以求出2-n项的gcd,然后每次改变的值即可求得答案了,注意相减是有负数产生排序一下即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N];
int main()
{
    ll ans=0;
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)    scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    for(int i=2;i<=n;i++)    ans=__gcd(ans,a[i]-a[i-1]);
    while(m--)
    {
        ll x;
        scanf("%lld",&x);
        printf("%lld ",__gcd(ans,a[1]+x));
    }puts("");
    return 0;
}


考虑dp,令表示.到了第i个,选了j个,填了多少容量.一个很显然的想法是拿背包写,没错,就是背包,你拿背包填就完事,最后的价值是不可能超过容量的2倍的,因为我扩大了1倍.也就是不会超过容量的一倍的.

#include <bits/stdc++.h>
using namespace std;
const int N=105;
int a[N],b[N];
int f[N][N][N*N];//到了第i个,选了j个,填了多少容量. 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
    }int sum=0;
    memset(f,-0x3f,sizeof(f)),f[0][0][0]=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i];
        for(int j=0;j<=i;j++)
        {
            for(int k=0;k<=sum;k++)
            {
                if(j&&k>=a[i])    f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-a[i]]+2*b[i]);
                f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+b[i]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        int ans=0;
        for(int j=0;j<=sum;j++)
        {
            ans=max(ans,min(2*j,f[n][i][j]));
        }
        printf("%.10f ",(double)ans/(2.0));
    }puts("");
    return 0;
}


这题了解下I,C的操作就挺简单的了.然后就是开个x[]数组记录下偏移值.

#include <bits/stdc++.h>
using namespace std;
const int N=1005,M=3;
int a[N*N][M];
int ans[N][N];
int p[3],x[3];//置换后的id,i,j,k的增值.
char s[N*N];
int n,m;
void del(int &u)
{
    u--;if(u<0)    u+=n;    
}

void add(int &u)
{
    u++;if(u>=n) u-=n;
}

void solve()
{
    for(int i=0;i<3;i++)    x[i]=0,p[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(s[i]=='R')    add(x[p[1]]);
        if(s[i]=='L')    del(x[p[1]]);
        if(s[i]=='D')    add(x[p[0]]);
        if(s[i]=='U')    del(x[p[0]]);
        if(s[i]=='I')    swap(p[1],p[2]);
        if(s[i]=='C')    swap(p[0],p[2]);
    }
    for(int i=1;i<=n*n;i++)
    {
        for(int j=0;j<3;j++)
        {
            a[i][j]=(a[i][j]+x[j]-1)%n+1;
        }ans[a[i][p[0]]][a[i][p[1]]]=a[i][p[2]];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%d ",ans[i][j]);
        }puts("");
    }
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&a[(i-1)*n+j][2]);
                a[(i-1)*n+j][0]=i;a[(i-1)*n+j][1]=j;
            }
        scanf("%s",s+1);
        solve();
    }
    return 0;
}


这题你把题目给定的01串转化成图,我们对于表示建图,反之,它给定的操作其实就是告诉你,它是个无向图.然后我们尽量往前走就ok,注意要走完n步.难点在于想到转化.

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+500;
char s[N];
int ep[N];//记录i->i+1有几条边. 
void solve()
{
    scanf("%s",s+1);int n=strlen(s+1);int id=n;
    for(int i=1;i<=n;i++)//一共会运行n次. 
    {
        if(s[i]-'0')    ep[id++]++;
        else            ep[--id]++;
    }id=n;
    for(int i=1;i<=n;i++)
    {
        if(ep[id-1]&&(!ep[id]||ep[id-1]>1))
        {
            ep[--id]--;
            printf("0");
        }
        else
        {
            ep[id++]--;
            printf("1");
        }
    }puts("");
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)    
        solve();
    return 0;
}