ARC151
A
直接看\(S,T\)不同的位置,然后贪心填就行了
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n;
char S[MAXN];
char T[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
scanf("%s",S+1);
scanf("%s",T+1);
int Cnt=0;
for(int i=1;i<=n;i++)
{
if(S[i]!=T[i])
{
++Cnt;
}
}
if(Cnt&1)
{
printf("-1");
return 0;
}
int Rs=Cnt/2,Rt=Cnt/2;
for(int i=1;i<=n;i++)
{
if(S[i]==T[i])
{
printf("0");
}
else
{
if(S[i]=='0')
{
if(Rs)
{
Rs--;
printf("0");
}
else
{
printf("1");
}
}
else
{
if(Rt)
{
Rt--;
printf("0");
}
else
{
printf("1");
}
}
}
}
}
B
直接枚举第一个不等的位置,前面相等的用斌茶几维护一下连通块个数即可,联通块除了枚举的点之间互不影响
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=2e5+5;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int n,m;
int p[MAXN];
int fa[MAXN];
int find(int x)
{
if(fa[x]==x)
{
return fa[x];
}
fa[x]=find(fa[x]);
return fa[x];
}
int Cnt;
void unionn(int i,int j)
{
int ex=find(i);
int ey=find(j);
if(ex!=ey)
{
fa[find(i)]=find(j);
Cnt--;
}
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&m);
Cnt=n;
int inv2=(MOD-MOD/2);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
fa[i]=i;
}
int Res=0;
for(int i=1;i<=n;i++)
{
if(find(i)!=find(p[i]))
{
if(Cnt>1)
{
int Ni=Pow(m,Cnt-2,MOD);
Ni=((long long)Ni*m)%MOD;
Ni=((long long)Ni*(m-1))%MOD;
Ni=((long long)Ni*inv2)%MOD;
Res=((long long)Res+Ni)%MOD;
}
}
unionn(i,p[i]);
}
printf("%d\n",Res);
}
C
直接套\(sg\)
已经填的两个数\(x,y\)之间\(sg=[x=y]\)，手完一下就出来了
两边的空的\(k\), \(sg=k-1/(n-k)\)
// #include<bits/stdc++.h>
// using namespace std;
// int Sg[105][2][2];
// int main()
// {
// // freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
// Sg[0][1][1]=Sg[0][0][0]=1;
// for(int i=1;i<=10;i++)
// {
// for(int l=0;l<=1;l++)
// {
// for(int r=0;r<=1;r++)
// {
// vector<int>V;
// for(int k=1;k<=i;k++)
// {
// V.push_back(Sg[k-1][l][0]^Sg[i-k][0][r]);
// V.push_back(Sg[k-1][l][1]^Sg[i-k][1][r]);
// }
// sort(V.begin(),V.end());
// unique(V.begin(),V.end());
// int Mex=V.size();
// for(int k=0;k<V.size();k++)
// {
// if(V[k]!=k)
// {
// Mex=k;
// break;
// }
// }
// Sg[i][l][r]=Mex;
// printf("%d %d %d %d\n",i,l,r,Mex);
// }
// }
// }
// }
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
long long n;
int m;
long long x;
int y;
pair<long long,int>V[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%lld %d",&n,&m);
if(m==0)
{
if(n&1)
{
printf("Takahashi");
}
else
{
printf("Aoki");
}
return 0;
}
for(int i=1;i<=m;i++)
{
scanf("%lld %d",&x,&y);
V[i]=make_pair(x,y);
}
long long sg=0;
for(int i=1;i<m;i++)
{
if(V[i].second==V[i+1].second)
{
sg^=1;
}
}
sg^=(V[1].first-1);
sg^=(n-V[m].first);
if(sg)
{
printf("Takahashi");
}
else
{
printf("Aoki");
}
}
D
酱汁了/kk
首先不同位之间的操作互不影响,这个性质很关键
证明的话手完一下就可以了,你会发现建出来的图对应路径是一定的
然后相同位的顺序不能换,但我们就可以直接维护\(f_{op1,op2}\)表示\(op1\)中\(op2\)的系数
然后就完了??
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
const int MOD=998244353;
int n;
int a[MAXN];
int b[MAXN];
int q;
int x,y;
vector<int>Rec[35];
int f[2][2];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&q);
for(int i=0;i<(1<<n);i++)
{
scanf("%d",&a[i]);
}
while(q--)
{
scanf("%d %d",&x,&y);
Rec[x].push_back(y);
}
for(int i=0;i<n;i++)
{
f[0][0]=1;
f[1][1]=1;
f[0][1]=0;
f[1][0]=0;
for(int j=0;j<Rec[i].size();j++)
{
int op=Rec[i][j];
f[op^1][op]=((long long)f[op^1][op]+f[op][op])%MOD;
f[op^1][op^1]=((long long)f[op^1][op^1]+f[op][op^1])%MOD;
}
for(int j=0;j<(1<<n);j++)
{
int op=((j>>i)&1);
b[j]=((long long)a[j]*f[op][op])%MOD;
b[j]=((long long)b[j]+((long long)a[j^(1<<i)]*f[op][op^1]))%MOD;
}
for(int j=0;j<(1<<n);j++)
{
a[j]=b[j];
}
}
for(int i=0;i<(1<<n);i++)
{
printf("%d ",a[i]);
}
}
E
经典E比D简单
不难看出就是找个最长公共子串,这个\(Hash\)一下就好了
但如果没有的情况有点麻烦,我最开始觉得得用\(KMP\)枚举每个位置再线段树维护一下
不过似乎直接建\(a_i\rightarrow a_{i+1}\)跑多元最短路即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,p,q;
int a[MAXN];
int b[MAXN];
int c[MAXN];
const unsigned long long p1=998244353;
const unsigned long long p2=1e9+7;
map<unsigned long long,int>vis1,vis2;
unsigned long long Mul1[MAXN];
unsigned long long Mul2[MAXN];
unsigned long long Hashb1[MAXN];
unsigned long long Hashb2[MAXN];
unsigned long long Hashc1[MAXN];
unsigned long long Hashc2[MAXN];
unsigned long long Getb1(int l,int r)
{
return Hashb1[r]-Hashb1[l-1]*Mul1[r-l+1];
}
unsigned long long Getc1(int l,int r)
{
return Hashc1[r]-Hashc1[l-1]*Mul1[r-l+1];
}
unsigned long long Getb2(int l,int r)
{
return Hashb2[r]-Hashb2[l-1]*Mul2[r-l+1];
}
unsigned long long Getc2(int l,int r)
{
return Hashc2[r]-Hashc2[l-1]*Mul2[r-l+1];
}
bool check(int mid)
{
vis1.clear();
vis2.clear();
for(int i=1;i+mid-1<=p;i++)
{
int l=i;
int r=i+mid-1;
vis1[Getb1(l,r)]=1;
vis2[Getb2(l,r)]=1;
}
for(int i=1;i+mid-1<=q;i++)
{
int l=i;
int r=i+mid-1;
if(vis1[Getc1(l,r)]&&vis2[Getc2(l,r)])
{
return 1;
}
}
return 0;
}
int Vis[MAXN];
int dis[MAXN];
vector<int>g[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
Mul1[0]=Mul2[0]=1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
Mul1[i]=Mul1[i-1]*p1;
Mul2[i]=Mul2[i-1]*p2;
}
scanf("%d",&p);
for(int i=1;i<=p;i++)
{
scanf("%d",&b[i]);
Hashb1[i]=Hashb1[i-1]*p1+b[i];
Hashb2[i]=Hashb2[i-1]*p2+b[i];
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d",&c[i]);
Hashc1[i]=Hashc1[i-1]*p1+c[i];
Hashc2[i]=Hashc2[i-1]*p2+c[i];
}
int l=1;
int r=min(p,q);
int Key=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
l=mid+1;
Key=mid;
}
else
{
r=mid-1;
}
}
if(Key!=-1)
{
printf("%d\n",p+q-2*Key);
}
else
{
for(int i=1;i<=n;i++)
{
if(i<n)
{
g[a[i]].push_back(a[i+1]);
g[a[i+1]].push_back(a[i]);
}
dis[i]=0x3f3f3f3f;
}
queue<int>Q;
for(int i=1;i<=p;i++)
{
Q.push(b[i]);
dis[b[i]]=0;
}
while(Q.size())
{
int temp=Q.front();
Q.pop();
for(int i=0;i<g[temp].size();i++)
{
int v=g[temp][i];
if(dis[v]!=0x3f3f3f3f)
{
continue;
}
dis[v]=dis[temp]+1;
Q.push(v);
}
}
int Mini=0x3f3f3f3f;
for(int i=1;i<=q;i++)
{
Mini=min(Mini,dis[c[i]]);
}
printf("%d\n",2*Mini+p-1+q-1);
}
}