Alice and Recoloring 1
有一个很牛逼的转化，考虑一个点 \(i,j\) 是否被以此为端点进行区间覆盖，只需考虑 \((i+1,j)\)，\((i,j+1)\)，\((i+1,j+1)\) 是为 \(B\) 的个数,如果个数为偶数，则此点不许操作，否则则需操作。设原序列 \(a_{i,j}=[s_{i,j}='B']\) , \(c_{i,j}=a_{i+1,j} \bigoplus a_{i,j+1} \bigoplus a_{i+1,j+1} \bigoplus a_{i,j}\)，所以将 \(a\) 清空其实就是将 \(c\) 清空，而且还有一个比较好的地方就是进行操作一其实就是修改一个点，而进行操作四就是修改四个点形如:\((x+1,y+1)\) \(\rightarrow\) \((x,y)\)，\((x,m)\)，\((n,y)\)，\((n,m)\)，再考虑，操作 \(2,3\)就是在搞笑，完全可以被两次操作一代替，还有两次操作四可以被六次操作一代替，所以操作四最多进行一次，然后直接枚举那一次选在哪里就可以。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
char s[N];
int c[N][N];
int a[N][N];
int sum[N][N];
signed main(){
int n,m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;j++){
if(s[j]=='B') c[i][j]=1;
else c[i][j]=0;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=(c[i][j]^c[i+1][j]^c[i][j+1]^c[i+1][j+1]);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
sum[i][j]+=a[i][j];
}
}
int ans=sum[n][m];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int w;
w=a[n][m]+a[i-1][j-1]+a[n][j-1]+a[i-1][m];
ans=min(ans,3+sum[n][m]-w+4-w);
}
}
printf("%lld",ans);
}