Codeforces Round 925 (Div. 3)（A~E）

题目暂时是AC，现在是Hack阶段，代码仅供参考。

A. Recovering a Small String

题目给出的n都可以由字母来组成，比如4可以是a+a+b，字母里面排第一个和第二个，即1+1+2=4。但是会歧义，比如a+b+a为1+2+1=4，也是4，答案就不唯一，输出字典序最小的那三个字母。

直接枚举。

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;int n;void solve(){cin>>n;per(i,'a','z'){per(j,'a','z'){per(k,'a','z'){int ti=i-'a'+1;int tj=j-'a'+1;int tk=k-'a'+1;if(ti+tj+tk==n){cout<<(char)i<<(char)j<<(char)k<<endl;return;}}}}
}void init(){}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t;cin>>t;while(t--)solve(),init();return 0;
}

B. Make Equal

你可以任选序列中的两个数 i < j，让 a[i] 减去 1~a[i] 的任意值 加到 a[j] 上面，这个操作可以无限执行，问是否可以让序列的每个数都相等。（也可以不执行操作）

关键要想到每个数都要相等的话，那么每个数都要变成序列的平均值，然后模拟就行了。

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;
const int N=2e5+5;int n,a[N],sum;void no(){cout<<"NO"<<endl;
}void yes(){cout<<"YES"<<endl;
}void solve(){cin>>n;per(i,1,n)cin>>a[i],sum+=a[i];if(sum%n!=0)return no();sum/=n;//每一个都要是sum的平均值int nowtake=0;per(i,1,n){if(a[i]==sum)continue;else if(a[i]<sum){if(nowtake>=sum-a[i]){nowtake-=sum-a[i];}else return no();}else if(a[i]>sum){nowtake+=a[i]-sum;}}if(nowtake)return no();else return yes();
}void init(){sum=0;
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t;cin>>t;while(t--)solve(),init();return 0;
}

C. Make Equal Again

给你一个序列A，你可以选择任意一个连续区间，全部变成任意一个数，比如[2,2,9,10]，选择3~4，全部变成2，就会变成[2,2,2,2]，这个操作你只能执行一次，问你将序列A中的每个数都相等至少要改变几个数。

从答案入手，最大范围是 l=1，r=n，就是全部修改，然后看看 l 和 r 能不能往里面变，让答案更小。

显然可以分类讨论。

如果a[l] == a[r]，那就是要改中间的部分。

如果a[l] != a[r]，那就是要改左边或者右边更短的那一截。

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;
const int N=2e5+5;int n,a[N];void solve(){cin>>n;per(i,1,n)cin>>a[i];int l=1,r=n;if(a[l]!=a[r]){while(a[l]==a[1])l++;while(a[r]==a[n])r--;cout<<min(n-l+1,r)<<endl;}else{while(a[l]==a[1])l++;while(a[r]==a[n])r--;if(l<=r)cout<<r-l+1<<endl;else cout<<0<<endl;}
}void init(){per(i,1,n)a[i]=0;
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t;cin>>t;while(t--)solve(),init();return 0;
}

补题：D. Divisible Pairs

对于序列中 i < j 的两个数，如果有 (a[i]+a[j])%x==0 并且 (a[i]-a[j])%y==0 那么称之为一个漂亮对，问你有几个漂亮对。

朴素算法很容易写出来，但是这道题的范围要求复杂度小于等于nlogn。

n^2过不了。

per(i,1,n){per(j,i+1,n){if((a[i]+a[j])%x==0 and (a[i]-a[j])%y==0){ans++;}}}

循环显然没有可以改进的空间了，所以我们需要对判断条件入手。

(a[i]+a[j])%x==0 and (a[i]-a[j])%y==0

也就是（箭头根据模运算律展开）

1、(a[i]+a[j])%x==0  ->  (a[i]%x+a[j]%x)%x==02、(a[i]-a[j])%y==0  ->  (a[i]%y-a[j]%y)%y==0

最终可以得到下面两个条件

1、a[i]%x + a[j]%x == x 或者 a[i]%x + a[j]%x == 02、a[i]%y 和 a[j]%y 的余数相等

所以只需要把每个数对x和y取余之后保留下来，再去匹配条件就可以了。

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;
const int N=2e5+5;int n,x,y,tmp,ans;map<pair<int,int>,int>f;void solve(){cin>>n>>x>>y;per(i,1,n){cin>>tmp;int l=tmp%x,r=tmp%y;ans+=f[{x-l,r}];if(l==0)ans+=f[{0,r}];f[{l,r}]++;}cout<<ans<<endl;
}void init(){f.clear();ans=0;
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t;cin>>t;while(t--)solve(),init();return 0;
}

E. Anna and the Valentine's Day Gift

博弈论，主要难度在于读题和代码细节。

Anna和Sasha在玩游戏，Anna先手开始第一回合。

Anna回合的操作：选择一个数，翻转。如：255变成552。250变成52（去掉开头的0）

Sasha回合的操作：选择两个数拼接成一个数，方向任意。如：255,10变成25510或者10255

如果轮到Sasha的时候无法找出两个数，那么游戏结束。

若最后留下来的那一个数>=10^m，那么Sasha胜利，否则Anna胜利。

问两个人都执行他们的最优操作，最后谁会胜利。

对于Anna来说最优的操作是让结尾0最多的数翻转，才会减少最终拼接数的位数。

对于Sasha来说拼接的意义就是让结尾0最多的数，不能被翻转。

那么处理一下输入，保留一下总位数和结尾0的数量，排个序，模拟。

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;
const int N=2e5+5,M=2e6+5;int n,tmp,m;
vector<pair<int,int>>v;//几位数,结尾几个0void solve(){cin>>n>>m;per(i,1,n){cin>>tmp;int cnt=0,cntz=0;bool flag=true;while(tmp){int bit=tmp%10;if(bit!=0)flag=false;if(flag)cntz++;//记录结尾0的数量cnt++;//记录位数tmp/=10;}v.push_back({cnt,cntz});}sort(v.begin(),v.end(),[](pair<int,int>a,pair<int,int>b){return a.se>b.se;});//根据结尾0的数量降序排序,每次都对结尾0最多的进行操作int all=0;//算一下最后总位数会剩下多少,用来和10^m的m比较bool Anna=true;per(i,0,v.size()-1){if(Anna){Anna=false;v[i].fr-=v[i].se;//总位数减去结尾0的数量}else {Anna=true;//Sasha回合保护一个结尾，所以不用变}all+=v[i].fr;//累计总位数}if(all>=m+1){//m是1后面有几个0，总位数是m+1cout<<"Sasha"<<endl;}else cout<<"Anna"<<endl;
}void init(){v.clear();
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t;cin>>t;while(t--)solve(),init();return 0;
}