浙江龙网

  1. 首页 > 生活百科 > >

[题解] 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)\) 。
点击查看代码【[题解] Atcoder Regular Contest ARC 151 A B C D E 题解】#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开始)：
  • \(sa: 0\1\ 1\ 1\ 1\ \cdots\)
  • \(di:0\ 0\ 0\ 0\ 0\ \cdots\)
  • \(si:0\ 1\ 2\ 3\ 4\ \cdots\)
  • \(no:0\ 1\ 0\ 1\ 0\ 1\ \cdots\)
规律很明显了吧 。
时间复杂度\(O(m)\) 。
点击查看代码#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 sa[100010],di[100010],si[100010],no[100010];int dfsdi(int i);int dfssi(int i);int dfssa(int i){if(sa[i]>-1) return sa[i];if(i==0) return sa[i]=0;map <int,int> mp;repn(j,i-2) mp[dfssa(j)^dfssa(i-1-j)]=1;rep(j,i) mp[dfsdi(j)^dfsdi(i-1-j)]=1;rep(j,500) if(mp.find(j)==mp.end()) return sa[i]=j;return sa[i]=0;}int dfsdi(int i){if(di[i]>-1) return di[i];if(i==0) return di[i]=0;map <int,int> mp;rep(j,i-1) mp[dfsdi(j)^dfssa(i-j-1)]=1;rep(j,500) if(mp.find(j)==mp.end()) return di[i]=j;return di[i]=0;}int dfssi(int i){if(si[i]>-1) return si[i];if(i==0) return si[i]=0;map <int,int> mp;rep(j,i){mp[dfssi(j)^dfsdi(i-j-1)]=1;if(i-j-1>0) mp[dfssi(j)^dfssa(i-j-1)]=1;}rep(j,500) if(mp.find(j)==mp.end()) return si[i]=j;return si[i]=0;}int dfsno(int i){if(no[i]>-1) return no[i];if(i==0) return no[i]=0;map <int,int> mp;rep(j,i){mp[dfssi(j)^dfssi(i-j-1)]=1;}rep(j,500) if(mp.find(j)==mp.end()) return no[i]=j;return no[i]=0;}LL n,m,x[200010],y[200010];int main(){fileio();/*rep(i,100005) sa[i]=di[i]=si[i]=no[i]=-1;rep(i,100) dfssa(i),dfsdi(i),dfssi(i),dfsno(i);rep(i,20) cout<<sa[i]<<' ';cout<<endl;rep(i,20) cout<<di[i]<<' ';cout<<endl;rep(i,20) cout<<si[i]<<' ';cout<<endl;rep(i,20) cout<<no[i]<<' ';*/cin>>n>>m;rep(i,m) scanf("%lld%lld",&x[i],&y[i]);if(m==0){puts(n%2==0 ? "Aoki":"Takahashi");termin();}LL ans=0;rep(i,m-1) if(y[i]==y[i+1]) ans^=1;ans^=(x[0]-1);ans^=(n-x[m-1]);puts(ans ? "Takahashi":"Aoki");termin();}

推荐阅读


上一篇：RMarkdown进阶操作

下一篇：AKS Azure Kubernetes部署及查看应用资源