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\) ?？梢宰C明這樣貪心是最優的 。
時間復雜度\(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();}

推薦閱讀