## level 0 Happy New Year！

```#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 加法和乘法

```#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 糖果

```#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 数字串

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 序列的美观度

```#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 匹配串

（由于刚开始读错题了，没有看到“每个字符串至少包含一个井号”，所以写了个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 内卷

```#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 模数的世界

(p-1)(p-a)=p(p-a-1)+a

```#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 重力坠击

```#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;
}```