C.Errich-Tac-Toe
题目描述
解法
先考虑 ( t easyspace version)，针对 (lfloorfrac{k}{3}
floor) 来构造，可以把整张图三染色，一定有一种颜色满足格子 X 的数量不超过 (lfloorfrac{k}{3}
floor)，把这种颜色的X全部改成O即可。
对于 ( t hardspace version)，还是沿用染色的思路，我们让任意相邻的三个格子出现X和O，也就是把某种颜色全部改成X，某种颜色全部改成O，那么我们让出现次数最多的颜色不变，这样剩下不超过 (frac{2k}{3}) 的格子，XO或OX一定有一种能让改变的格子不超过 (frac{1}{2})（因为XX和OO的贡献是 (1)；XO和OX对某一个贡献是 (2)，对另一个没有贡献），所以改变的总格子数不超过 (lfloorfrac{k}{3}
floor)
实现的时候讨论每种修改方案，看哪种满足条件即可。
总结
限制出现在相邻格子上，染色是很好的解决方案。
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 305;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n;char a[M][M],b[M][M];
int check(string s)
{
int c1=0,c2=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
b[i][j]=a[i][j];
if(a[i][j]!='.' && s[(i+j)%3]!='.')
b[i][j]=s[(i+j)%3];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]!='.')
c1++,c2+=(a[i][j]!=b[i][j]);
return c2<=c1/3;
}
void print()
{
for(int i=1;i<=n;i++,puts(""))
for(int j=1;j<=n;j++)
printf("%c",b[i][j]);
}
void work()
{
n=read();
for(int i=1;i<=n;i++)
scanf("%s",a[i]+1);
if(check(".XO")) print();
else if(check(".OX")) print();
else if(check("X.O")) print();
else if(check("O.X")) print();
else if(check("OX.")) print();
else if(check("XO.")) print();
}
signed main()
{
T=read();
while(T--) work();
}
D. Rating Compression
题目描述
解法
很接近正解了，我们先考虑 (1) 要么出现在最前面要么出现在最后面。
这样就会出现一个子问题，我们考虑了 (i) 之后移动左右端点，(i+1) 同样满足上述限制，从后往前推即可。
但是 (k=1) 的情况不能这样算，因为还没有取最小值，所以对权值的出现位置没有强烈的限制。
#include <cstdio>
const int M = 300005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,l,r,k,a[M],b[M],ans[M],cnt[M];
void work()
{
n=read();l=1;r=n;k=0;
for(int i=1;i<=n;i++) cnt[i]=ans[i]=0;
for(int i=1;i<=n;i++)
{
a[i]=read();b[a[i]]=i;
cnt[a[i]]++;
if(a[i]==1) ans[n]=1;
}
for(int i=1;i<=n;i++) k+=(cnt[i]>0);
if(k==n) ans[1]=1;
for(int i=n;i>=2;i--)
{
if(!ans[n]) break;
int p=n-i+1;
ans[i]=1;
if(--cnt[p]==0 && cnt[p+1] && (l==b[p] || r==b[p]))
{
if(l==b[p]) l++;
if(r==b[p]) r--;
continue;
}
break;
}
for(int i=1;i<=n;i++)
printf("%d",ans[i]);
puts("");
}
signed main()
{
T=read();
while(T--) work();
}
E. Capitalism
题目描述
解法
差分约束板题，这样建图：
- 如果 (c=1)，(a_jleq a_i+1)，(a_ileq a_j-1)
- 如果 (c=0)，(a_jleq a_i+1)，(a_ileq a_j+1)
然后枚举起点跑最短路，如果出现负环或者奇环就无解，否则按照题目更新答案即可。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 2005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,ans,pos,g[M][M],a[M],b[M];
signed main()
{
n=read();m=read();
memset(g,0x3f,sizeof g);
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),c=read();
a[i]=u;b[i]=v;g[u][v]=1;
if(c==1) g[v][u]=-1;
else g[v][u]=1;
}
for(int i=1;i<=n;i++)
g[i][i]=0;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
ans=-1;
for(int i=1;i<=n;i++)
{
if(g[i][i]<0)
{
puts("NO");
return 0;
}
int mx=-n,mi=n;
for(int j=1;j<=n;j++)
{
mx=max(mx,g[i][j]);
mi=min(mi,g[i][j]);
}
for(int j=1;j<=m;j++)
if(g[i][a[j]]==g[i][b[j]])
mx=-n;
if(ans<mx-mi)
{
ans=mx-mi;
pos=i;
}
}
if(ans==-1) puts("NO");
else
{
printf("YES
%d
",ans);
for(int i=1;i<=n;i++)
printf("%d ",g[pos][i]+n);
}
}
G. Communism
题目描述
解法
设 (l[s]) 表示字符集 (s) 出现的左端点，(r[s]) 表示右端点，(cnt[s]) 表示出现次数。
首先观察性质：字符 (x) 替换成 (y) 的时候必须要保证至少存在一个 (y)，而且替换时都是整体替换，那么可以知道每个字符最多完成一次替换；字符集大小为 (20)，这提示我们可以状压。
根据第一个性质，如果 (y) 替换成 (z)，那么我们把 (y,z) 连一条有向边，如果最后能归到某个字符 (x)，那么我们能得到一棵以 (x) 为根的有向树。考虑一棵以 (u) 为根的子树，如果归于一个字符，还能变化的充要条件是 (u) 子树内所有字符构成的集合 (s) 满足 (kcdot (r[s]-l[s]+1)leq cnt[s])
现在设计 (dp)，设 (dp[s]) 表示字符集 (s) 是否能够变化成 (s) 以外的字符，最后如果能变成字符 (x) 那么满足 (dp[Uoplus x]=1)，转移：
- 枚举 (s) 的子集 (s_1)，如果 (dp[s_1]=dp[soplus s_1]=1)，那么 (dp[s]=1)
- 枚举一个字符 (x)，把所有字符都转成 (x)，如果 (dp[soplus x]=1) 并且满足 (kcdot (r[s]-l[s]+1)leq cnt[s])，那么 (dp[s]=1)
复杂度瓶颈在于第一种转移需要 (O(3^m)) 的子集枚举，但是理想复杂度是 (O(2^m)) 左右。
优化可以考虑有效转移，设 (s_1) 和 (s_2) 为 (s) 拆分成两个子集，那么考虑这种转移什么时候无效：
(cnt[s]=cnt[s_1]+cnt[s_2]geq k(r[s_1]-l[s_1]+1)+k(r[s_2]-l[s_2]+1)geq k(r[s]-l[s]+1))
在 (s_1) 和 (s_2) 在原字符串上的出现范围有交的时候，最后一个不等号成立，这时候使用第二种转移一定比第一种转移好，所以此种情况第一种转移是无效转移。那么就有一个限制：拆分出的子集在原字符串上不交，可以把所有字符按出现左端点排序，那么子集拆分就只能选取一段前缀，时间复杂度 (O(m2^m))（(m=20)）
(2021/10/14) 补充：为什么最后只需要选取一个前缀，因为当我们把相交的段通过第一种转移绑定之后，剩下的段在原序列上不交。比如段从左到右为 (1,2,3,4)，那么把 (1,3/2,4) 绑定再合并之后一定比 (1,2/3,4) 差，所以绑定的只会是一个连续段，枚举前缀足够了。
总结
本题体现了：性质->图论->dp 的思维过程，这三者缺一不可。
针对复杂度瓶颈优化转移，本题考虑有效转移来减少第一种转移的使用。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 1<<20;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,ka,kb,id[30],dp[M],cnt[M],l[M],r[M];
char s[5005],ans[30],t[30];
signed main()
{
n=read();ka=read();kb=read();
scanf("%s",s+1);
memset(id,-1,sizeof id);
memset(l,0x3f,sizeof l);
for(int i=1;i<=n;i++)
{
int c=s[i]-'a';
if(id[c]==-1) t[m]=s[i],id[c]=m++;
cnt[1<<id[c]]++;
l[1<<id[c]]=min(l[1<<id[c]],i);
r[1<<id[c]]=i;
}
dp[0]=1;
for(int s=1;s<(1<<m);s++)
{
for(int i=0,s1=0;i<m;i++)
{
if(!(s&(1<<i))) continue;
s1|=(1<<i);
dp[s]|=(dp[s^s1]&&dp[s1]);
l[s]=min(l[s^s1],l[s1]);
r[s]=max(r[s^s1],r[s1]);
cnt[s]=cnt[s^s1]+cnt[s1];
}
for(int j=0;j<m;j++)
if((s>>j&1) && dp[s^(1<<j)]
&& ka*(r[s]-l[s]+1)<=kb*cnt[s])
dp[s]=1;
}
int s=(1<<m)-1;
for(int i=0;i<m;i++)
if(dp[s^(1<<i)])
ans[++k]=t[i];
printf("%d",k);
sort(ans+1,ans+k+1);
for(int i=1;i<=k;i++)
printf(" %c",ans[i]);
}
H.Multithreading
题目描述
解法
首先考虑没有问号的情况怎么计算答案，设 (b_o,b_e) 分别表示奇数位置和偶数位置上 (b) 颜色的个数，(w_o,w_e) 类似，其实贪心都可以猜出结论：(f(c)=frac{1}{2}|b_o-b_e|)，设 (|b_o-b_e|=2k)，证明：
- 首先证明 (f(c)leq k)，可以通过构造一组有 (k) 个异色交点的解来完成，我们先把相邻两个位置奇偶性不同的同色点连接起来，这时候一定不会产生异色交点。剩下的点满足 (b_o=2k,w_e=2k)，那么我们按照 (bwbw...bwbw) 这样相邻的同色点连接，发现会产生 (k) 个交点。
- 然后证明 (f(c)geq k)，我们声明最优解中不存在同色交点，因为如果存在可以通过调整使之不交，并且异色交点个数不增。所以就可以假设不存在同色交点，因为 (|b_o-b_e|=2k)，所以必然会有 (k) 条连接奇偶性相同位置的边，并且这些边会把原图分成两部分满足点数都为奇数，那么必然存在交点，由于不是同色交点，那么一定是异色交点，所以 (f(c)geq k)
这个结论可以用于计数，设 (F) 为?的个数，(F_o) 为偶数位置?的个数，我们枚举?中有 (i) 个位置，如果是偶数位置染色为 (b)，否则染色成 (w)，其他位置用相反的方法染色。设 (i) 中染色 (b) 的个数为 (a)，那么 (b) 颜色在偶数位置的个数是 (b_e+a)，在奇数位置的个数是 (b_o+F_o-i+a)（因为 (i-a) 是奇数位置用掉的?个数），所以：
设 (x=b_o+F_o-b_e=frac{n}{2}-w_o-b_e)，所以 (f(c)=frac{1}{2}|x-i|)，(i) 对应的方案数有 ({Fchoose i}) 种，所以答案是：
从 ( t easyspace version) 继续，暂且忽略 (frac{1}{2^F}) 这个系数，我们把绝对值拆掉（默认 (i=xmod 2)）：
首先我们把组合数前面的系数拿掉，对于 (x{Fchoose i}) 直接提到前面去，(i{Fchoose i}=F{F-1choose i-1})，把 (F) 拿到前面去。
还要解决 (i=xmod 2) 的问题，因为 ({Fchoose i}={F-1choose i}+{F-1choose i-1}) 可以直接转成前缀和的形式，组合数前缀和是很容易修改的，只需要使用这个恒等式：
总结
一般这种题都有结论来支持计数，要大胆猜结论。
推式子的时候注意绝对值可以拆掉，如果式子的主体是组合数，可以尝试把他变成组合数前缀和的形式。
#include <cstdio>
const int M = 200005;
const int MOD = 998244353;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,x,F,ans,inv[M],fac[M];char s[M];
int Abs(int x)
{
return x>0?x:-x;
}
void init()
{
inv[0]=inv[1]=fac[0]=1;
for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
}
int C(int n,int m)
{
return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
signed main()
{
n=read();m=read();
init();
scanf("%s",s+1);
x=n/2;
for(int i=1;i<=n;i++)
{
F+=(s[i]=='?');
if(i%2 && s[i]=='w') x--;
if(i%2==0 && s[i]=='b') x--;
}
for(int i=0;i<=F;i++)
if(i%2==(x%2+2)%2)
ans=(ans+Abs(x-i)*C(F,i))%MOD;
for(int i=1;i<=F;i++)
ans=ans*inv[2]%MOD;
printf("%lld
",ans);
}