CF1592F2 解题报告

· · 题解

管理辛苦了！

反复发现性质，然后逐步转化的普通题，但是我为什么不会？？？

一个很容易看到的事情是，(n,1) 操作和 (1,m) 操作都是可以使用两次 (1,1) 操作解决的。

那么我们只需要考虑 (1,1) 操作和 (n,m) 操作即可。

将前者记为操作一，后者为操作二。

使用操作题的常规考虑手段：考察每次操作中的不变量。

如果让输入的字符串记为 s，a_{i,j}=[s_{i,j}=\texttt{W}]，不难想到记录 b_{i,j}=a_{i,j}\operatorname{xor} a_{i+1,j}\operatorname{xor}a_{i+1,j}\operatorname{xor} a_{i+1,j+1}。

那么操作一相当于使一个 b_{i,j} 取反，操作二相当于使 b_{i,j},b_{i,m},b_{n,j},b_{n,m} 取反。

目标便是让 b 全为 0。

贪心地，考虑充分利用操作二。

但是还不能直接贪心。

考虑如果对 (x,y_1),(x,y_2) 分别使用了一次操作二，此时花费了 4，但是只改变了 4 个点，弗若直接对四个点分别操作一，所以操作二更优的必要条件是每一行使用的操作二不超过一次。

每一列同理。

所以我们得出一个结论：对每行/列至多执行一次操作二。

这里已经隐隐有点最大匹配的影子了。

但是还没结束。

我们发现：如果 b_{x,y}+b_{n,m}+b_{n,y}+b_{m,x}\le 2，操作二不执行也罢。

所以操作二执行的另一必要条件是 b_{x,y}+b_{n,y}+b_{m,x}=3。

所以只需要对符合上述条件的点对 (x,y) 连边，以行为左部，列为右部跑最大匹配即可。

最后记得处理 b_{n,m} 的状态。

细节看代码：

const int N=503,NN=N<<1;
int n,m,mc[NN],vis[NN],res,ans;
bool a[N][N];
sd vector<int>G[NN];
bool dfs(int u,int tg)
{
  if(vis[u]==tg) return false;
    vis[u]=tg;
    for(int v:G[u]) if(!mc[v]||dfs(mc[v],tg)) return mc[v]=u,true;
    return false;
}
void Solve()
{
  rd(n,m);
  for(int i=1;i<=n;++i)
  {
    char s[N];
    rd(s);
    for(int j=0;j<m;++j) a[i][j+1]=s[j]=='B';
  }
  for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j]^=a[i+1][j]^a[i][j+1]^a[i+1][j+1],ans+=a[i][j];
  for(int i=1;i<n;++i) for(int j=1;j<m;++j) if(a[i][j]&&a[i][m]&&a[n][j]) G[i].push_back(j+n);
  for(int i=1;i<=n;++i) res+=dfs(i,i);
  ans-=a[n][m],wrt(ans-res+(a[n][m]^res&1));
  return;
}

\color{green}{\checkmark}。