X操作
100分以下做法:我也不知道怎么写
100分做法:
首先,判断的第一条件是m>=abs(x-y),表示操作次数大于两数的差,因为如果操作次数小于两数的差了,那么x一定时无法变成y的,其次,如果操作abs(x-y)次后使x变成了y,这时如果操作次数是奇数,那么就无法达成,是偶数,我们可以通过反复加减的方式来使得x==y。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll x,y,m;
        scanf("%d%d%d",&x,&y,&m);
        ll s=abs(x-y);
        if(m>=s&&(s&1)==(m&1)) printf("Yes\n");
        else printf("No\n");
    }
}

填数
100分以下做法:我也不知道怎么写
100分做法:
首先,对于没有限制的,显然我们填1即可,对于限制1,贪心的使得a[i]==a[i-1],对于限制2,贪心的使得a[i]==a[i-1]+1,这样贪心下去,然后判断最终得到的总和是否小于等于m即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int b[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        bool flag=true;
        int pre=0,sum=0;
        for(int i=1;i<=n;i++)
        {
            if(b[i]==0) sum++,pre=1;
            else if(b[i]==1) sum+=pre;
            else sum+=pre+1,pre++;
            if(sum>m) {flag=false;break;}
        }
        printf(flag?"Yes\n":"No\n");
    }
}

区间中最多的数
10分做法:暴力枚举
100分做法:1<=a[i]<=100,用前缀和维护1100每个数出现的次数,就可以O(1)的查询某个数在区间里出现的次数了,然后对于一次查询,只需要O(100)的暴力去统计即可,时间复杂度O(100q+100n)
50分做法:在100分做法的基础上,用数据结构去维护1
100每个数出现的次数,咋们就可以TLE了,时间复杂度O(100qlog2(n)+100nlog2(n))。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,a[N],sum[N][105];
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=100;j++)
        sum[i][j]=sum[i-1][j]+(a[i]==j);
    while(q--)
    {
        int l,r,mx=0,ans;
        scanf("%d%d",&l,&r);
        for(int i=1;i<=100;i++)
            if(sum[r][i]-sum[l-1][i]>=mx) ans=i,mx=sum[r][i]-sum[l-1][i];
        printf("%d\n",ans);
    }
}

子段和
100分以下做法:我也不知道怎么写
100分做法:
1.f[i][j]表示[i,j]这段区间的和,开一个vis数组保存每个和出现的次数,如果之星操作1,我们只需要删除n个区间的值,执行操作2,只需要假如n个区间的值,时间复杂度O(nm)。
2.记录前缀和和一个vis数组,vis数组里保存某个前缀和出现的次数,对于每次查询O(n)的去跑所有前缀和,判断sum-x这个前缀和是否存在即可,时间复杂度最坏O(nm)。
3.由于数据水,时间复杂度O(n^2 m)的算法也被放过了,很遗憾我的数据这么水。
做法1:

#include<bits/stdc++.h>
using namespace std;
const int N=255;
int n,m,a[N],sum[N],vis[N*100000];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i],vis[sum[i]]++;
    vis[0]=1;
    while(m--)
    {
        int opt,x;
        scanf("%d",&opt);
        if(opt!=1) scanf("%d",&x);
        if(opt==1)
            vis[sum[n]]--,n--;
        else if(opt==2) a[++n]=x,sum[n]=sum[n-1]+a[n],vis[sum[n]]++;
        else
        {
            bool flag=false;
            for(int i=n;i>=1;i--)
                if(sum[i]>=x&&vis[sum[i]-x])
                    flag=true;
            printf(flag?"Yes\n":"No\n");
        }
    }
}

做法2:

#include<bits/stdc++.h>
using namespace std;
const int N=255;
int n,m,a[N],f[N][N],vis[N*100000];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
    {
        if(i==j) f[i][j]=a[i];
        else f[i][j]=f[i][j-1]+a[j];
        vis[f[i][j]]++;
    }
    while(m--)
    {
        int opt,x;
        scanf("%d",&opt);
        if(opt!=1) scanf("%d",&x);
        if(opt==1)
        {
            for(int i=1;i<=n;i++)
                vis[f[i][n]]--;
            n--;
        }
        else if(opt==2)
        {
            a[++n]=x;
            for(int i=1;i<=n;i++)
            {
                if(i==n) f[i][n]=a[n];
                else f[i][n]=f[i][n-1]+a[n];
                vis[f[i][n]]++;
            }
        }
        else
            printf(vis[x]?"Yes\n":"No\n");
    }
}

做法3:

#include<bits/stdc++.h>
using namespace std;
const int N=255;
int n,m,a[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    while(m--)
    {
        int opt,x;
        scanf("%d",&opt);
        if(opt!=1) scanf("%d",&x);
        if(opt==1)
            n--;
        else if(opt==2) a[++n]=x;
        else
        {
            bool flag=false;
            for(int i=1;i<=n;i++)
            {
                int t=0;
                for(int j=i;j<=n;j++)
                {
                    t+=a[j];
                    if(t==x) flag=true;
                }
            }
            printf(flag?"Yes\n":"No\n");
        }
    }
}