[题解] 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();
}
