CF1592F2 Alice and Recoloring 2 解题报告。
不一定更好的阅读体验。
摘自我的 构造题目选做 例题 IV。
CF 2800 的构造就这？/cf/cf/cf（
首先，操作 2 和操作 3 都是没有用的，因为都可以表示成两次操作 1 的形式，而且花费都不比两次操作 1 要优。
考虑将字符 B 看成 \(1\)，字符 W 看成 0，那么目标就是要将给定的矩阵通过翻转变成全 \(0\) 矩阵。
但是矩形的翻转是不好做的，自然的想法是通过二维差分转成单点修改。即我们令 \(c_{i,j}=(a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1})\bmod 2\)，那么令 \(A\) 每一项变成 \(0\) 其实就是令 \(C\) 每一项变成 \(0\)。
考虑操作的影响。以 \((x,y)\) 为右下角进行操作 1，实际上只会改变 \(c_{x,y}\) 的奇偶性；以 \((x,y)\) 为左上角进行操作 2，实际上只会改变 \(c_{x-1,y-1}\)，\(c_{x-1,m}\)，\(c_{n,y-1}\)，\(c_{n,m}\) 这四项的奇偶性。
这里先讲一下 F1 的做法，如果对 \((x,y)\) 进行操作 \(2\)，必须要满足上述四个点的 \(c\) 都为 \(1\)。原因很简单，如果有至少一个为 \(0\)，那么反转之后还需要再进行一次操作 \(1\) 反转回来，总花费为 \(3+1=4\)，实际上只需要 \(3\) 次 \(1\) 操作就可以搞定，花费为 \(3\)。注意到每次都会翻转 \((n,m)\) 这个点，所以说操作 4 只会进行一次。那么我们只要枚举一下是否有能够进行操作 4 的 \((x,y)\) 即可。时间复杂度 \(O(n^2)\)，可以通过本题。
接下来讲得是 F2 的做法，注意到操作 \(4\) 的花费变成 \(2\)，显然是操作的四个点中可以存在一个 \(0\)，那么我们就不用管 \((n,m)\) 这个点的取值了，因为每次都会更改它，最后一个 \(1\) 操作改回来就行，所以剩下那三个点必须都为 \(1\)，且操作 4 是可以进行多次的。考虑 \((x,y)\)，\((x,m)\)，\((n,y)\) 这三个点有什么性质，如果我们对 \((x,y)\) 这个点翻转了，那么就意味着 \(x\) 这一行再也不能对任何一个点进行操作，因为 \((x,m)\) 被翻转成了 \(0\)，同理，\(y\) 这一列也不能对任何一点进行操作。这不就很网络流了吗，每一行，每一列，每一个点都只能选一次，所以将 \(x\to y\) 连一条流量为 \(1\) 的边，\(S\le x\) 连一条流量为 \(1\) 的边，\(y\to T\) 连一条流量为 \(1\) 的边，跑 dinic 即可，其实本质上就是一个二分图最大匹配。最坏情况边数为 \(O(n^2)\)，点数为 \(O(n)\)，所以复杂度 \(O(n^2\sqrt{n})\)，可以通过本题。
int main()
{
n=read(),m=read();
rep(i,1,n)
{
scanf("%s",s+1);
rep(j,1,m) if(s[j]=='B') a[i][j]=true;
}
rep(i,1,n) rep(j,1,m) a[i][j]=a[i][j] xor a[i+1][j] xor a[i][j+1] xor a[i+1][j+1];
S=0,T=n+m+1;
rep(i,1,n-1) add_edge(S,i,1);
rep(i,1,m-1) add_edge(i+n,T,1);
rep(i,1,n-1) rep(j,1,m-1) if(a[i][j]&&a[i][m]&&a[n][j]) add_edge(i,j+n,1);
int ans=0;
while(bfs()) ans-=dfs(S,INF);
if(ans&1) a[n][m]^=1;
rep(i,1,n) rep(j,1,m) if(a[i][j]) ++ans;
printf("%d\n",ans);
return 0;
}