[題解] 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_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(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_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(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_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(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();
}
D – Binary Representations and Queries
將輸入的數組稱為\(a\)，輸出的數組稱為\(b\)。顯然b是a的一個線性組合，也就是每個\(b_i\)都\(=\sum_{j=0}^{n-1}coef_j\cdot a_j\)，其中coef是係數。\(a_j\to b_i\)的係數取決於什麼呢？其實係數等於輸入的q個操作存在多少個子集，滿足對j依次進行子集中的操作後，j變成了i。操作指的是對某一位的翻轉，比如輸入\(16 \ 0\)就表示如果一個數的第16位是0，就把他變成1。觀察發現，對每一位的操作都是獨立的、互不影響的，所以可以先把對第\(n-1\)位的操作都做完，再做第\(n-2,n-3\)位的操作…… 但是注意對於同一位的操作，順序是不能換的。這樣這題都好做了，我們可以在trie樹上從上往下，依次進行每一位的所有操作。每一層的係數可以統一計算。
時間複雜度\(O(nlogn+q)\)。
點擊查看程式碼
#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 <LL,LL>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(0);
}
using namespace std;
const LL MOD=998244353;
LL n,q,a[1000010];
vector <LL> op[20];
int main()
{
fileio();
cin>>n>>q;
rep(i,1<<n) scanf("%lld",&a[i]);
LL x,y;
rep(i,q)
{
scanf("%lld%lld",&x,&y);
op[x].pb(y);
}
for(int i=n-1;i>=0;--i)
{
pii vx=mpr(1,0),vy=mpr(0,1);
rep(j,op[i].size())
{
if(op[i][j]==0) (vy.fi+=vx.fi)%=MOD,(vy.se+=vx.se)%=MOD;
else (vx.fi+=vy.fi)%=MOD,(vx.se+=vy.se)%=MOD;
}
int full=1<<(i+1);
for(int st=0;st<(1<<n);st+=full)
{
int mid=st+(full>>1);
rep(j,full>>1)
{
LL vl=a[st+j],vr=a[mid+j];
a[st+j]=(vx.fi*vl+vx.se*vr)%MOD;
a[mid+j]=(vy.fi*vl+vy.se*vr)%MOD;
}
}
}
rep(i,1<<n) cout<<a[i]<<' ';
termin();
}
E – Keep Being Substring
如果X中有一些位置，它們一直沒有被刪除，並保留到了Y中，那麼這些位置一定形成一個連續段。有這種位置的情況，操作次數一定比沒有的少，因為沒有這種位置的情況，X中所有元素都要被刪除，Y中所有元素都是手動加上的。
先看能不能在X中有位置不被刪除的情況下完成目標，枚舉X中被保留的子段的開頭位置i，把X和Y放到一起跑後綴數組+算出LCP數組。我們的目標是找到j，滿足X中以i開頭的後綴，與Y中以j開頭的後綴的LCP最長。通過在LCP數組上two-pointers可以輕鬆找到這樣的j。
然後就是X中全被刪光的情況了。題目要求修改過程中時刻是A的子串，所以我們應該先把X刪得只剩下一個字元，然後”跑”到A中某一個Y出現的地方，因為只有一個字元好跑路，多出來的都是累贅，最後肯定都是要刪掉的，這些多出來的字元可能導致不是A的子串。用哈希找出Y在A中出現的所有位置，把這些位置的值\(A_i\)標記為目標值，只要我們達到了其中一個目標值就可以還原出整個Y。把X中的所有值\(X_i\)標記為起始值，從這些起始值開始跑bfs，兩個值之間有邊當且僅當它們在A中的某個地方相鄰。這樣就通過bfs找到了從”X的一個字元”到”Y的一個字元”的最少操作次數。
時間複雜度\(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 ull unsigned long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(0);
}
using namespace std;
int n;
vector <int> s;
namespace SA
{
int sa[500010],lcp[500010],rk[1000010],cnt[500010],tmp[500010],add,cur;
void rsort()
{
cur=0;
for(int i=s.size()-1;i>=s.size()-add;--i) tmp[cur++]=i;
rep(i,s.size()) if(sa[i]-add>=0) tmp[cur++]=sa[i]-add;
int bd=max(n+3,(int)s.size()+3);
rep(i,bd+3) cnt[i]=0;
rep(i,s.size()) ++cnt[rk[i]];
repn(i,bd+3) cnt[i]+=cnt[i-1];
cur=0;
for(int i=s.size()-1;i>=0;--i) sa[--cnt[rk[tmp[i]]]]=tmp[i];
}
int cmp(int x,int y){return (int)(rk[x]!=rk[y]||rk[x+add]!=rk[y+add]);}
void getSA()
{
rep(i,s.size()+s.size()+3) rk[i]=0;
rep(i,s.size()) rk[i]=s[i],sa[i]=i;
int m=0;
for(int msk=0;m<s.size();++msk)
{
add=(msk==0 ? 0:(1<<(msk-1)));
rsort();
tmp[sa[0]]=1;
repn(i,s.size()-1) tmp[sa[i]]=tmp[sa[i-1]]+cmp(sa[i-1],sa[i]);
m=tmp[sa[s.size()-1]];
rep(i,s.size()) rk[i]=tmp[i];
}
}
void getLCP()
{
rep(i,s.size()) --rk[i];
lcp[0]=0;
rep(i,s.size())
{
if(rk[i]==0) continue;
int lst=(i==0 ? 0:max(0,lcp[rk[i-1]]-1));
while(i+lst<s.size()&&sa[rk[i]-1]+lst<s.size()&&s[i+lst]==s[sa[rk[i]-1]+lst]) ++lst;
lcp[rk[i]]=lst;
}
}
}
int a[200010],xnn,ynn,x[200010],y[200010],ans=1e9,sum[200010],isTarg[200010],dist[200010];
ull h[200010],H=11451419,HH,pw[200010];
multiset <int> st;
vector <int> g[200010];
queue <int> q;
ull getHash(int lb,int ub){return h[ub+1]-h[lb]*pw[ub-lb+1];}
int main()
{
fileio();
cin>>n;rep(i,n) scanf("%d",&a[i]);
cin>>xnn;rep(i,xnn) scanf("%d",&x[i]);
cin>>ynn;rep(i,ynn) scanf("%d",&y[i]);
rep(i,ynn) s.pb(y[i]);s.pb(n+2);rep(i,xnn) s.pb(x[i]);
SA::getSA();SA::getLCP();
bool hvy=false;
int mxc=0;
rep(i,s.size()-1)
{
if(SA::sa[i]<ynn)//是y
{
hvy=true;
st.clear();
}
else
{
st.insert(SA::lcp[i]);
if(hvy) mxc=max(mxc,*st.begin());
}
}
st.clear();
hvy=false;
for(int i=s.size()-2;i>=0;--i) if(SA::sa[i]!=ynn)
{
if(SA::sa[i]<ynn)
{
hvy=true;
st.clear();st.insert(SA::lcp[i]);
}
else
{
if(hvy) mxc=max(mxc,*st.begin());
st.insert(SA::lcp[i]);
}
}
if(mxc>0) ans=(xnn-mxc)+(ynn-mxc);
rep(i,ynn) HH=HH*H+y[i];
rep(i,n) h[i+1]=h[i]*H+a[i];
pw[0]=1;repn(i,n+3) pw[i]=pw[i-1]*H;
rep(i,n-ynn+1)
{
ull hv=getHash(i,i+ynn-1);
if(hv==HH) ++sum[i],--sum[i+ynn];
}
rep(i,n)
{
sum[i+1]+=sum[i];
if(sum[i]>0) isTarg[a[i]]=1;
}
rep(i,n-1) g[a[i]].pb(a[i+1]),g[a[i+1]].pb(a[i]);
rep(i,n+3) dist[i]=1e8;
rep(i,xnn) if(dist[x[i]]==1e8)
{
dist[x[i]]=0;
q.push(x[i]);
}
while(!q.empty())
{
int f=q.front();q.pop();
rep(i,g[f].size()) if(dist[g[f][i]]==1e8)
{
dist[g[f][i]]=dist[f]+1;
q.push(g[f][i]);
}
}
int add=xnn-1+ynn-1;
repn(i,n) if(isTarg[i]) ans=min(ans,dist[i]*2+add);
cout<<ans<<endl;
termin();
}
