A
略，具体见 C。
B
这题卡了我一会，写起来又花了挺长一段时间的，水平还是不够！
贪心一下，优先取贡献为 \(2\) 的，其次取贡献为 \(1\) 的，看上去就很对。
Code:
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 100100
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
std::vector<int>v[4][4][4];
int n,ans,ord[5000500][4];
char s[N];
const char h[]={'w','i','n'};
IL void work()
{
n=read();
for(reg int a=4,b,c;a--;)for(b=4;b--;)for(c=4;c--;)v[a][b][c].clear();
for(reg int i=1,a,b,c;i<=n;++i)
{
scanf("%s",s),a=b=c=0;
if(s[0]=='w')++a; else if(s[0]=='i')++b; else ++c;
if(s[1]=='w')++a; else if(s[1]=='i')++b; else ++c;
if(s[2]=='w')++a; else if(s[2]=='i')++b; else ++c;
v[a][b][c].push_back(i);
}
ans=0;
while(1)
{
reg bool flag=0;
for(reg int a=4,b,c;a--;)for(b=4;b--;)for(c=4;c--;)if((a!=b||b!=c)&&!v[a][b][c].empty())flag=1;
if(!flag)break;
for(reg int a=4,b,c,aa,bb,cc,x,y;a--;)for(b=4-a;b--;)if(v[a][b][c=3-a-b].size()&&(!a||!b||!c))
for(aa=4;aa--;)for(bb=4-aa;bb--;)if(v[aa][bb][cc=3-aa-bb].size())
{
if(a==aa&&b==bb&&c==cc)continue;
x=v[a][b][c].back(),y=v[aa][bb][cc].back(),v[a][b][c].pop_back(),v[aa][bb][cc].pop_back();
if(!a&&aa>1&&b>1&&!bb)
{
++ans,ord[ans][0]=x,ord[ans][1]=0,ord[ans][2]=y,ord[ans][3]=1;
v[a+1][b-1][c].push_back(x),v[aa-1][bb+1][cc].push_back(y);
goto skip;
}
if(!a&&aa>1&&c>1&&!cc)
{
++ans,ord[ans][0]=x,ord[ans][1]=0,ord[ans][2]=y,ord[ans][3]=2;
v[a+1][b][c-1].push_back(x),v[aa-1][bb][cc+1].push_back(y);
goto skip;
}
if(!b&&bb>1&&c>1&&!cc)
{
++ans,ord[ans][0]=x,ord[ans][1]=1,ord[ans][2]=y,ord[ans][3]=2;
v[a][b+1][c-1].push_back(x),v[aa][bb-1][cc+1].push_back(y);
goto skip;
}
v[a][b][c].push_back(x),v[aa][bb][cc].push_back(y);
}
for(reg int a=4,b,c,aa,bb,cc,x,y;a--;)for(b=4-a;b--;)if(v[a][b][c=3-a-b].size()&&(!a||!b||!c))
for(aa=4;aa--;)for(bb=4-aa;bb--;)if(v[aa][bb][cc=3-aa-bb].size()&&(!aa||!bb||!cc))
{
if(a==aa&&b==bb&&c==cc)continue;
x=v[a][b][c].back(),y=v[aa][bb][cc].back(),v[a][b][c].pop_back(),v[aa][bb][cc].pop_back();
if(aa&&b&&(!a&&b>1||!bb&&aa>1))
{
++ans,ord[ans][0]=x,ord[ans][1]=0,ord[ans][2]=y,ord[ans][3]=1;
v[a+1][b-1][c].push_back(x),v[aa-1][bb+1][cc].push_back(y);
goto skip;
}
if(aa&&c&&(!a&&c>1||!cc&&aa>1))
{
++ans,ord[ans][0]=x,ord[ans][1]=0,ord[ans][2]=y,ord[ans][3]=2;
v[a+1][b][c-1].push_back(x),v[aa-1][bb][cc+1].push_back(y);
goto skip;
}
if(bb&&c&&(!b&&c>1||!cc&&bb>1))
{
++ans,ord[ans][0]=x,ord[ans][1]=1,ord[ans][2]=y,ord[ans][3]=2;
v[a][b+1][c-1].push_back(x),v[aa][bb-1][cc+1].push_back(y);
goto skip;
}
v[a][b][c].push_back(x),v[aa][bb][cc].push_back(y);
}
skip:;
}
printf("%d\n",ans);
for(reg int i=1;i<=ans;++i)printf("%d %c %d %c\n",ord[i][0],h[ord[i][3]],ord[i][2],h[ord[i][1]]);
}
main()
{
for(reg int t=read();t--;work());
}
C
“给你们展示一下，什么是教科书一般的亵渎。”
这场先开的这题，状态没起来，WA 了好多发，罚时直接起飞了！
首先考虑最小次数怎么求，有一个简单贪心。
去维护一下哪些怪是用于凑亵渎的等差数列的，可以增量算出全局打几。
在值域上维护比较方便。
Code:
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define int long long
#define N 200200
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int n,all,ans,cnt,x[N];
#define ls (o<<1)
#define rs (o<<1|1)
#define mid (l[o]+r[o]>>1)
int l[N<<2],r[N<<2],tag[N<<2],mn[N<<2],pos[N<<2];
IL void upd(reg int o,reg int k){mn[o]+=k,tag[o]+=k;}
IL void pushup(reg int o){if(mn[ls]<=mn[rs])pos[o]=pos[ls],mn[o]=mn[ls]; else pos[o]=pos[rs],mn[o]=mn[rs];}
IL void pushdown(reg int o){if(tag[o])upd(ls,tag[o]),upd(rs,tag[o]),tag[o]=0;}
void build(reg int o,reg int L,reg int R)
{
l[o]=L,r[o]=R,mn[o]=pos[o]=L,tag[o]=0;
if(L<R)build(ls,L,mid),build(rs,mid+1,R);
}
void modify(reg int o,reg int L,reg int R,reg int k)
{
if(L<=l[o]&&r[o]<=R)return upd(o,k);
if(L>r[o]||l[o]>R)return;
pushdown(o),modify(ls,L,R,k),modify(rs,L,R,k),pushup(o);
}
IL void work()
{
n=read(),all=ans=cnt=0,build(1,1,n);
for(reg int i=1;i<=n;++i)x[i]=read();
for(reg int i=1,p;i<=n;++i)
{
all+=x[i],modify(1,x[i],n,-1);
if(mn[1]<0)p=pos[1],modify(1,p,n,1),ans+=p; else ++cnt;
printf("%lld ",all-ans-cnt*(cnt+1)/2);
}
puts("");
}
main()
{
for(reg int t=read();t--;work());
}
D
这场除了 A 以外最简单的题。
考虑最终的对决一定是 \(1\ x(x\neq 1)\)，那么有 \(1\) 所在的那棵子树的所有 \(2^{n-1}\) 个位置都不会有 Wooden Spoon。
继续考虑其他位置，则会有一个递归的不断删一半位置的操作。
直接进行 dp 就可以了。
Code:
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define mod 998244353
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
IL int Add(reg int x,reg int y){return x+y<mod?x+y:x+y-mod;}
IL void Pls(reg int &x,reg int y){x=Add(x,y);}
IL int Mul(reg int x,reg int y){reg long long r=1ll*x*y; return r<mod?r:r%mod;}
int n,f[1<<20|5][22],ans[1<<20|5],fac[1<<20|5],full;
main()
{
n=read(),full=1<<n,f[0][0]=fac[0]=1;
for(reg int i=1;i<=full;++i)fac[i]=Mul(fac[i-1],i);
for(reg int i=0,j,w,x;i<full;++i)for(j=0;j<=n;++j)if(w=f[i][j])
{
x=1<<n-j,Pls(f[i+1][j],Mul(w,full-x-i));
if(j==n)Pls(ans[i+1],Mul(w,Mul(x,fac[full-i-1]))); else Pls(f[i+1][j+1],Mul(w,x));
}
for(reg int i=1;i<=full;++i)printf("%d\n",ans[i]);
}
E
赛时常数没写好，优化过状态数的代码都过不去，好气啊！
考虑 dp of dp。
维护 \(\emptyset,\left\{a\right\},\left\{b\right\},\left\{ab\right\}\) 走到的状态以及 Alice 与 Bob 的获胜局数之差。统计答案的时候有一个基环森林。
这样的状态数量是 \(9\times 10^5\) 级别的，好像说是直接可以过了。
但可以再优化，观察到 \(\left\{a\right\},\left\{b\right\}\) 不会同时出现在最终的基环森林中 \(\emptyset\) 所在的那个基环数上。
可以进一步地压缩状态数。这个优化看起来非常强，但实际的效果并不显著，仅将状态数优化到了 \(511752\)。（但以我的答辩常数仍旧无法通过）
Code（赛时被卡常版本）：
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define mod 998244353
#define N 220
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
IL int Add(reg int x,reg int y){return x+y<mod?x+y:x+y-mod;}
IL int Sub(reg int x,reg int y){return x<y?x-y+mod:x-y;}
IL void Pls(reg int &x,reg int y){x=Add(x,y);}
IL void Dec(reg int &x,reg int y){x=Sub(x,y);}
IL int Mul(reg int x,reg int y){reg long long r=1ll*x*y; return r<mod?r:r%mod;}
int n;
char s[N];
bool ban[4];
#define ull unsigned long long
const ull B1=533,B2=20;
struct Node{int x[4],y[4];}p,q;
std::unordered_map<ull,int>f[2];
IL Node back(reg ull h)
{
reg Node tp;
for(reg int i=4;i--;)if(!ban[i])tp.y[i]=h%B1-n,h/=B1;
for(reg int i=4;i--;)if(!ban[i])tp.x[i]=h%B2,h/=B2;
return tp;
}
IL ull hash(reg Node &p)
{
reg ull h=0;
for(reg int i=0;i<4;++i)if(!ban[i])h=h*B2+p.x[i];
for(reg int i=0;i<4;++i)if(!ban[i])h=h*B1+n+p.y[i];
return h;
}
int ch[4][2],de[4][2],ans1,ans2,ans3;
bool vis[4];
IL void clear(reg std::unordered_map<ull,int>&a){reg std::unordered_map<ull,int>b; std::swap(a,b);}
main()
{
scanf("%s",s+1),n=strlen(s+1);
ch[0][0]=1,ch[0][1]=2,de[1][0]=1,ch[1][1]=3,ch[2][0]=3,de[2][1]=-1,de[3][0]=1,de[3][1]=-1;
reg int a=0,b=1;
for(reg int i=4;i--;)p.x[i]=i,p.y[i]=0; ban[1]=1;
f[a][hash(p)]=1;
for(reg int i=1,j,w;i<=n;++i,a^=1,b^=1)
{
clear(f[b]);
for(reg auto t:f[a])
{
p=back(t.first),w=t.second;
if(!w)continue;
if(s[i]!='b')
{
for(j=4;j--;)q.x[j]=ch[p.x[j]][0],q.y[j]=p.y[j]+de[p.x[j]][0];
Pls(f[b][hash(q)],w);
}
if(s[i]!='a')
{
for(j=4;j--;)q.x[j]=ch[p.x[j]][1],q.y[j]=p.y[j]+de[p.x[j]][1];
Pls(f[b][hash(q)],w);
}
}
}
for(reg auto t:f[a])
{
p=back(t.first),memset(vis,0,sizeof(vis));
reg int u=0,s=0,k=0;
while(!vis[u])vis[u]=1,s+=p.y[u],u=p.x[u]; if(vis[1])continue;
vis[u]=0,k=p.y[u],u=p.x[u];
while(vis[u])k+=p.y[u],u=p.x[u];
if(k>0)Pls(ans1,t.second);
else if(k<0)Pls(ans3,t.second);
else Pls(ans2,t.second);
}
clear(f[a]),ban[1]=0;
for(reg int i=4;i--;)p.x[i]=i,p.y[i]=0; ban[2]=1;
f[a][hash(p)]=1;
for(reg int i=1,j,w;i<=n;++i,a^=1,b^=1)
{
clear(f[b]);
for(reg auto t:f[a])
{
p=back(t.first),w=t.second;
if(!w)continue;
if(s[i]!='b')
{
for(j=4;j--;)q.x[j]=ch[p.x[j]][0],q.y[j]=p.y[j]+de[p.x[j]][0];
Pls(f[b][hash(q)],w);
}
if(s[i]!='a')
{
for(j=4;j--;)q.x[j]=ch[p.x[j]][1],q.y[j]=p.y[j]+de[p.x[j]][1];
Pls(f[b][hash(q)],w);
}
}
}
for(reg auto t:f[a])
{
p=back(t.first),memset(vis,0,sizeof(vis));
reg int u=0,s=0,k=0;
while(!vis[u])vis[u]=1,s+=p.y[u],u=p.x[u]; if(vis[2])continue;
vis[u]=0,k=p.y[u],u=p.x[u];
while(vis[u])k+=p.y[u],u=p.x[u];
if(k>0)Pls(ans1,t.second);
else if(k<0)Pls(ans3,t.second);
else Pls(ans2,t.second);
}
clear(f[a]),ban[2]=0;
for(reg int i=4;i--;)p.x[i]=i,p.y[i]=0; ban[1]=ban[2]=1;
f[a][hash(p)]=1;
for(reg int i=1,j,w;i<=n;++i,a^=1,b^=1)
{
clear(f[b]);
for(reg auto t:f[a])
{
p=back(t.first),w=t.second;
if(!w)continue;
if(s[i]!='b')
{
for(j=4;j--;)q.x[j]=ch[p.x[j]][0],q.y[j]=p.y[j]+de[p.x[j]][0];
Pls(f[b][hash(q)],w);
}
if(s[i]!='a')
{
for(j=4;j--;)q.x[j]=ch[p.x[j]][1],q.y[j]=p.y[j]+de[p.x[j]][1];
Pls(f[b][hash(q)],w);
}
}
}
for(reg auto t:f[a])
{
p=back(t.first),memset(vis,0,sizeof(vis));
reg int u=0,s=0,k=0;
while(!vis[u])vis[u]=1,s+=p.y[u],u=p.x[u]; if(vis[1])continue;
vis[u]=0,k=p.y[u],u=p.x[u];
while(vis[u])k+=p.y[u],u=p.x[u];
if(k>0)Dec(ans1,t.second);
else if(k<0)Dec(ans3,t.second);
else Dec(ans2,t.second);
}
printf("%d\n%d\n%d\n",ans1,ans2,ans3);
}
F
咕咕咕。
标签：CF1785,aa,bb,&&,ans,ord,reg From： https://www.cnblogs.com/Nesraychan/p/17095712.html