[题解] 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
#define rep(i,n) for(int i=0;i
#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< B - A < AP
把序列\(A_{P_1},A_{P_2}\cdots A_{P_n}\)叫做序列\(B\)。既然要求A
时间复杂度\(O(nlogn)\)。
点击查看代码
#include
#define rep(i,n) for(int i=0;i
#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< 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
#define rep(i,n) for(int i=0;i
#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 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 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 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 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<>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
#define rep(i,n) for(int i=0;i
#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 op[20];
int main()
{
fileio();
cin>>n>>q;
rep(i,1<=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<>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< 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
#define rep(i,n) for(int i=0;i
#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 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 st;
vector g[200010];
queue 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]=0;--i) if(SA::sa[i]!=ynn)
{
if(SA::sa[i]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<