level 0 Happy New Year!

对标cf难度:900
知识点:模拟
直接从n往后遍历即可,找到第一个数字和相等的break。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int f(int x){
    int cnt=0;
    while(x){
        cnt+=x%10,x/=10;
    }
    return cnt;
}
int main(){
    ll n,t,i,j,k;
    cin>>n;
    for(i=n+1;i<=1e5;i++){
        if(f(i)==f(n))break;
    }
    cout<<i;
}

level 1 加法和乘法

对标cf难度:1300
知识点:博弈
如果只有一个数,那么这个数是奇数则牛牛赢,否则牛妹赢。
如果不止一个数,那么假设有奇数个数,显然是牛妹赢。因为剩余2个数的时候,牛妹做最后一次操作,无论什么情况一定都能生成两个偶数(如果剩两个奇数就做加法,如果存在偶数就做乘法)。
假设有偶数个数,牛妹要做的就是让最后剩余2个偶数即可。牛牛每次最多可以消除一个偶数,牛妹每次最多可以生成一个偶数。所以如果初始状态的偶数不小于2个,则牛妹赢;否则牛牛赢。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
    ll n,x=0,y=0,i,j,k;

    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>k;
        if(k%2) x++;
        else y++;
    }
    if(n==1&&k%2){cout<<"NiuNiu";return 0;}
    if(n%2||y>1) cout<<"NiuMei";
    else cout<<"NiuNiu";
    return 0;
}

level 1 糖果

对标cf难度:1400
知识点:并查集
互为朋友的人拿到的糖果数量应该一样,且为这个并查集size的最大值。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll fa[1000100];
ll a[1000100];
int f(int x){
    if(x==fa[x])return x;
    return fa[x]=f(fa[x]);
}

int main(){
    ll n,m,i;
    cin>>n>>m;
    for(i=1;i<=n;i++)cin>>a[i],fa[i]=i;
    for(i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        int p=f(x),q=f(y);
        fa[p]=q;
        a[p]=a[q]=max(a[p],a[q]);
    }
    ll res=0;
    for(i=1;i<=n;i++)res+=a[f(i)];
    cout<<res;
}

level 1 数字串

对标cf难度:1400
知识点:字符串、模拟、贪心
我们不妨这样想,先将给定的字母串转化为数字串,然后用两种不同的贪心方法:

  1. 优先一一对应的转化(不使用10以上的数字)
  2. 优先使用两位数
    这样如果两种方案构造出的字母串相等,则无解。否则一定有解,输出和初始串不等的任意字符串即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
    ll n,i,j,k,t;
    string s;
    cin>>s;
    string temp1="",temp2="";
    for(i=0;i<s.length();i++){
        int t=(s[i]-'a')+1;
        if(t/10>0&&t%10!=0){
            temp1+=t/10+'a'-1;
            temp1+=t%10+'a'-1;
        }
        else temp1+=s[i];
    }
    if(temp1!=s){cout<<temp1;return 0;}
    for(i=0;i<s.length()-1;i++){
        int t1=(s[i]-'a')+1,t2=(s[i+1]-'a')+1,p=t1*10+t2;
        if(t2<10&&p<=26){
            temp2+=p+'a'-1;
            i++;
        }
        else temp2+=s[i];
    }
    if(i==s.length()-1)temp2+=s[i];
    if(temp2!=s)cout<<temp2;
    else cout<<-1;
}

level 2 序列的美观度

对标cf难度:1700
知识点:dp
我是这样做的:先预处理每个数出现在哪些角标,数值为的角标放入vector:里,并开一个temp数组,用来记录数值为的数遍历到了中的位置。
为前个数删掉部分数后能达到的最大美观度。
然后就可以得dp方程:

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll a[1000100],tong[1000100];
vector<ll>g[1000100];
ll dp[1000100],temp[1000100];
int main(){
    ll n,m,i,cnt=0;
    cin>>n;
    for(i=1;i<=n;i++)scanf("%lld",&a[i]),g[a[i]].push_back(i);
 //   cout<<g[1][0]<<" "<<g[1][1]<<endl;
    for(i=1;i<=n;i++){
        if(temp[a[i]]==0){
            temp[a[i]]++;
            dp[i]=dp[i-1];
            continue;
        }
        dp[i]=max(dp[i-1],dp[g[a[i]][temp[a[i]]-1]]+1);
       // cout<<i<<" "<<a[i]<<" "<<g[a[i]][temp[a[i]]-1]<<endl;
        temp[a[i]]++;
    }
    cout<<dp[n];
}

level 2 匹配串

对标cf难度:1600
知识点:字符串、贪心
由于每个字符串都包含井号,所以最终答案要么是0,要么是无穷大。因为井号可以代替任何串。
最终答案是0的充要条件是:存在某个串的前缀包含所有串前缀,存在某个串的后缀包含所有串后缀。注意这里“前后缀”的定义是直到第一次遇到井号位置的全部子串。
(由于刚开始读错题了,没有看到“每个字符串至少包含一个井号”,所以写了个kmp,大家忽略就好)
(假设存在不包含井号的字符串,这道题的难度直接上升到2100+)
(不过读错题也并不是没有好处,至少让我把不熟的kmp又练习了一遍ww)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//只关心前缀和后缀
string s[1000100];
int nex[1000100];
vector<string>v,qz,hz;
void get(string a){
    int k=-1,i;
    nex[0]=-1;
    for(i=0;i<a.length();){
        if(k==-1||a[i]==a[k]){
            i++,k++;
            nex[i]=k;
        }
        else k=nex[k];
    }
}
int jud(string a,string b){
  //  cout<<a<<" "<<b<<endl;
    string s,t;
    int i,j=0,k=b.length()-1;
    for(i=0;i<a.length()&&a[i]!='#';i++){
        if(a[i]!=b[j])return 0;
        j++;
    }
    for(i=a.length()-1;i>=j&&k>=j&&a[i]!='#';i--){
        if(a[i]!=b[k])return 0;
        k--;
    }
    int op=j,ed=i;
 //   cout<<op<<" "<<ed<<" "<<k<<endl;
    //在op和ed之间找子串
    int ek=op;
    for(i=op;i<ed;i=j){
        while(i<ed&&a[i]=='#')i++;
        if(i>=ed)break;
     //   cout<<i<<" "<<j<<endl;
        string temp="";
        for(j=i;j<ed&&a[j]!='#';j++)temp+=a[j];
        memset(nex,0,sizeof(int)*(temp.length()+10));
     //   cout<<temp;
        get(temp);
    //    for(int z=0;z<temp.length();z++)cout<<nex[z]<<" ";
        int tempi=0;
     //   cout<<tempi<<" "<<temp.length()<<" "<<ek<<" "<<k<<endl;
        while(tempi<(int)(temp.length())&&ek<=k){
          //  cout<<"!"<<endl;
           // if(tempi!=-1)cout<<"!"<<tempi<<" "<<ek<<" "<<temp[tempi]<<" "<<b[ek]<<endl;

            if(tempi==-1||temp[tempi]==b[ek]){

                tempi++,ek++;
            }
            else tempi=nex[tempi];
          //  cout<<"debug:"<<tempi<<" "<<temp.length()<<" "<<ek<<" "<<k<<endl;
        }
   //     cout<<"jj:"<<tempi<<" "<<temp.length()<<" "<<ek<<" "<<k<<endl;
    //    cout<<tempi<<" "<<ek<<" "<<k<<endl;
        if(tempi<(int)(temp.length()))return 0;
    }
//    cout<<i<<" "<<ed<<endl;
    return i>=ed;
}
int main(){
    ll n,i,j,k,t;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>s[i];
        for(j=0;j<s[i].length();j++){
            if(s[i][j]=='#')break;
        }
        if(j==s[i].length())v.push_back(s[i]);
    }

    if(v.size()!=0){    //假设存在至少一个无#串
        for(i=0;i<v.size()-1;i++){
            if(v[i]!=v[i+1]){
                cout<<0;
                return 0;
            }
        }
        string temp=v[0];
        //cout<<temp<<endl;
      //  get(temp);
      //  for(i=0;i<temp.length();i++)cout<<nex[i]<<" ";
      //  cout<<endl;
        //cout<<"!"<<endl;
        for(i=0;i<n;i++){    //每个串井号之间必须是temp的子序列
            if(!jud(s[i],temp)){
                cout<<0;
                return 0;
            }
        }
        cout<<1;
    }
    else{//判断所有前后缀是否全部匹配
        string ma1="",ma2="";
        for(i=0;i<n;i++){
            for(j=0;j<s[i].length();j++){
                if(s[i][j]=='#')break;
                if(j==ma1.length())ma1+=s[i][j];
            }
            for(j=s[i].length()-1;j>=0;j--){
                if(s[i][j]=='#')break; 
                if(s[i].length()-1-j==ma2.length())ma2+=s[i][j];

            }
        }
  //      cout<<ma1<<endl<<ma2<<endl;
        for(i=0;i<n;i++){
            for(j=0;j<s[i].length()&&s[i][j]!='#';j++){
                if(j==ma1.length()||s[i][j]!=ma1[j]){
                  //  cout<<s[i][j]<<endl;
                    cout<<0;return 0;
                }
            }
            int tt=0;
            for(j=s[i].length()-1;j>=0&&s[i][j]!='#';j--,tt++){
                if(tt<0||s[i][j]!=ma2[tt]){
                 //   cout<<s[i][j]<<" "<<ma2[tt]<<endl;
                    cout<<0;return 0;
                }
            }
        }
        cout<<-1;
    }


}

level 3 内卷

对标cf难度:1800
知识点:贪心
不妨让所有人最开始都取E等,然后能改变max-min的值的唯一方法显然是让最小成绩的那个人取到D。然后继续找当前最小成绩,不断重复这个过程,直到A等的人即将超过k;或者某个人的A等都是所有人最小为止。
可以用优先队列(最小堆)维护这一过程。

#include<bits/stdc++.h>
using namespace std;
struct node{
    int id,i,val;
    node(int id,int i,int val){this->id=id,this->i=i,this->val=val;}
    bool operator < (const node &b)const
    {
        return val>b.val;
    }
};
priority_queue<node>q;
int a[100010][5];
int main(){
    int n,k,i,j,cnt=0,ma=0;
    cin>>n>>k;
    for(i=0;i<n;i++){
        for(j=0;j<5;j++)scanf("%d",&a[i][j]);
        node temp(i,4,a[i][4]);
        q.push(temp);
        ma=max(ma,a[i][4]);
    }
    int res=ma-q.top().val;
    while(1){
        node temp=q.top();
       // cout<<temp.id<<" "<<temp.i<<" "<<temp.val<<endl;
        q.pop();
        if(temp.i==0)break;
        node ne(temp.id,temp.i-1,a[temp.id][temp.i-1]);
        q.push(ne);
        ma=max(ma,a[temp.id][temp.i-1]);
        if(temp.i==1)k--;
        if(k<0)break;
        res=min(res,ma-q.top().val);
    }
    cout<<res;
}

level 3 模数的世界

对标cf难度:1900
知识点:数学
如果a,b都是0,那么显然答案为0。
否则一定能构造出gcd为p-1的结果。构造方法如下:
(p-1)(p-a)=p(p-a-1)+a
但是,直接输出(p-1)(p-a)和(p-1)(p-b)有可能造成gcd大于p-1的情况,对p取模后反而小于p-1。
我的方法是不断加p*(p-1),直到找到第一个gcd为p-1为止(有可能被叉掉,这个方法复杂度没有上限)
不过数据不是很强所以还是卡过去了ww(这道题给了3s,我跑了600ms,说明出题人没特地卡这种做法)

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,i,j,k,t;
    scanf("%d",&t);
    while(t--){
        int a,b,p;
        scanf("%d%d%d",&a,&b,&p);
        if(a==0&&b==0)
            printf("0 0 0\n");
        else{
            long long x=(p-1-a)*p+a,y=(p-1-b)*p+b;
            while(__gcd(x,y)!=p-1)x+=p*p-p;
            printf("%d %lld %lld\n",p-1,x,y);
        }
    }
}

level 3 重力坠击

对标cf难度:1900
知识点:搜索
观察到数据很小,所以直接搜索即可。
我的方法是:
首先预处理出每个点能击杀不同敌人的方案数,并状压去重:假设某种方案能击杀1号、3号和7号敌人,那么计该方案的状压值为
下一步,对去重之后的方案直接dfs搜索。维护所有情况的最大值(两个方案一起选,带来的状压值应该是位或运算,例如第一种方案击杀1、3、7,第二种方案击杀2、7,那么两个一起选则是击杀1、2、3、7)。

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,r;
};
node a[11];
set<int>s;
vector<int>v;
int ma=0,kk;
int gao(int x){
    int cnt=0;
    while(x)cnt+=x%2,x/=2;
    return cnt;
}
void dfs(int i,int temp,int x){
    if(temp==kk){
        ma=max(ma,gao(x));
        return;
    }
    if(i==v.size())return;
    dfs(i+1,temp+1,x|v[i]);
    dfs(i+1,temp,x);
}
int main(){
    int n,i,j,k,r;
    cin>>n>>kk>>r;
    for(i=0;i<n;i++){
        cin>>a[i].x>>a[i].y>>a[i].r;
    }
    for(i=-17;i<=17;i++){
        for(j=-17;j<=17;j++){
            int temp=0;
            for(k=0;k<n;k++){
                if((a[k].x-i)*(a[k].x-i)+(a[k].y-j)*(a[k].y-j)<=(r+a[k].r)*(r+a[k].r)){
                    temp+=1<<k;
                }
            }
            s.insert(temp);
        }
    }

    for(set<int>::iterator it=s.begin();it!=s.end();it++)v.push_back(*it);
    dfs(0,0,0);
    cout<<ma;
}

level 4 买礼物

对标cf难度:2000
这道题没做出来,数据结构还是太弱了。。
贴一下我队友的题解吧:
图片说明

图片说明
数据结构题我就不补了,抱队友大腿图片说明