[题解] Atcoder Regular Contest ARC 151 A B C D E 题解 _生活百科

【[题解] Atcoder Regular Contest ARC 151 A B C D E 题解】点我看题
昨天刚打的ARC，题目质量还是不错的。
A - Equal Hamming Distances对于一个位置i，如果\(S_i=T_i\)，那么不管\(U\)的这个位置填什么，对到\(S\)和\(T\)的海明距离增量都是相同的，所以这种位置一定填\(0\)更好；否则，这个位置填\(0\)或\(1\)分别可以给到\(S\)或到\(T\)的海明距离增加1，所以满足\(S_i=T_i\)的i的个数必须是偶数，否则一定无解。令这样的i的个数为x 。从左到右遍历所有这样的i，尽量把\(U_i\)填成0，除非填0会导致到S或T的海明距离\(>\frac x2\) 。可以证明这样贪心是最优的。
时间复杂度\(O(n)\) 。

点击查看代码

#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;++i)#define repn(i,n) for(int i=1;i<=n;++i)#define LL long long#define pii pair <int,int>#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){#ifdef LGSfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif}void termin(){#ifdef LGSstd::cout<<"\n\nPROGRAM TERMINATED";#endifexit(0);}using namespace std;int n;string s,t,ans="";int main(){fileio();ios::sync_with_stdio(false);cin>>n>>s>>t;int cc=0;rep(i,s.size()) if(s[i]!=t[i]) ++cc;if(cc%2==1){cout<<-1<<endl;termin();}cc/=2;int c0=0,c1=0;rep(i,s.size()){if(s[i]==t[i]) ans.pb('0');else{int a0=(s[i]=='1' ? 0:1);if((a0==0&&c0<cc)||(a0==1&&c1<cc)){ans.pb('0');if(a0==0) ++c0;else ++c1;}else{ans.pb('1');if(a0==0) ++c1;else ++c0;}}}cout<<ans<<endl;termin();}

B - A < AP把序列\(A_{P_1},A_{P_2}\cdots A_{P_n}\)叫做序列\(B\) 。既然要求A<B，那不如枚举A第一个比B小的位置\(i\)(之前的位置都相等) 。如果\(i=P_i\)，那\(A_i=B_i\)，这个位置是不可能分出胜负的，所以跳过。对于i之前的每一个位置j，如果\(j\ne P_j\)，那么必须满足\(A_j=A_{P_j}\)，所以可以把\(j\)和\(P_j\)两个位置用并查集连起来，变成同一个"连通块"，每个连通块内的位置取值必须相同。再回到i，如果\(i\)和\(P_i\)已经在同一个连通块内，那也必须跳过i 。否则只要保证\(i\)和\(P_i\)所在的连通块满足一定大小关系就行了。
时间复杂度\(O(nlogn)\) 。

点击查看代码

#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;++i)#define repn(i,n) for(int i=1;i<=n;++i)#define LL long long#define pii pair <int,int>#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){#ifdef LGSfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif}void termin(){#ifdef LGSstd::cout<<"\n\nPROGRAM TERMINATED";#endifexit(0);}using namespace std;const LL MOD=998244353;LL n,m,p[200010],fa[200010],pwm[200010];LL Find(LL x){if(fa[x]!=x) fa[x]=Find(fa[x]);return fa[x];}int main(){fileio();cin>>n>>m;pwm[0]=1;repn(i,n+3) pwm[i]=pwm[i-1]*m%MOD;repn(i,n) scanf("%lld",&p[i]),fa[i]=i;LL ans=0,con=n;repn(i,n){if(p[i]==i) continue;if(Find(i)==Find(p[i])) continue;LL val=m*(m-1)/2%MOD;(val*=pwm[con-2])%=MOD;(ans+=val)%=MOD;fa[Find(i)]=Find(p[i]);--con;}cout<<ans<<endl;termin();}

C - 01 Game两个选手都可以画0、画1，那么这个游戏就是一个公平有向图游戏，可以用SG函数求解。这题的SG值看起来很有规律，可以打表观察一下(这竟然是我第一道打表找规律做出的题) 。令\(sa_i\)表示一段长为i的空隙，两边的数相同(这里0和1对称)时，这个子游戏的SG函数值；\(di_i\)表示长度为i的空隙，两边数字不同的SG值；\(si_i\)表示长度为i的空隙，只有一端有数的SG值；\(no_i\)表示长度为i的空隙，两边都没有数(空序列)的SG值。打表的代码在下面程序的注释里。打出来发现(以下数组下标从0开始)：