To_Heart—题解——CF1592F1

题目链接

Link.

题解

神仙题啊神仙题。

首先，这道题目的操作是反转，而反转两次就等价于没反转。所以从初始状态转换到目标状态等价于从目标状态转换到初始状态。

为了方便，这里把 ‘W’ 看成 $0$，把 ‘B’ 看成 $1$，每次反转就是将矩形 $A$ 的每一个数异或 $1$。所求就是把所有数变成 $0$。

可以发现，做一次操作 $2$ 或操作 $3$ 等价于做两次操作 $1$，以操作 $2$ 为例，如果我想反转矩形 $(1,i)$ 到 $(2,m)$，我可以先反转 $(1,1)$ 到 $(2,i-1)$，然后反转 $(1,1)$ 到 $(2,m)$。因为两次操作 $1$ 的代价不高于一次操作 $2$ 或 $3$，所以操作 $2$ 和 $3$ 是没有用的。

现在我们可以反转的矩形只有两种：

1. 以 $(1,1)$ 为左上角
2. 以 $(n,m)$ 为右下角

因为操作 $1$ 的代价最小，所以我们先只考虑操作 $1$：

对于一个点，我们怎么考虑它是否需要反转呢？

如果它自己是 $1$，那么它是需要反转的，但是如果它左边、下边、左下的点有 $1$ 个或是 $3$ 个需要反转，那么它自己就不用反转了，因为其它三个点一次或三次的反转一定都包含了这个点，那么这个点自然就被反转了。否则这个点一定要消耗 $1$ 的代价反转。

同理也可以推出这个点是 0 的情况下是否需要反转。

总结一下，对于一个点，如果它与它左边、下边、左下的点异或的值为 $1$，那么这个点需要反转，为 $0$ 就不需要反转。

定义一个新的矩形 $B$，$B_{,j}=A_{i,j}\oplus A_{i+1,j}\oplus A_{i,j+1}\oplus A_{i+1,j+1}$ ，操作 $1$ 就相当于反转 $B_{i,j}$

那么答案就是 $$ans=\sum _{i=1}^n\sum _{j=1}^m{B}_{i,j}$$

但是因为还有一个操作 $4$，考虑操作 $4$ 的作用。可以发现操作 $4$ 就是将 $B_{i,j},B_{i,m},B_{n,j},B_{n,m}$ 同时反转。

看起来操作 $4$ 比操作 $1$ 更优，但是因为不停的反转 $B_{n,m}$，所以只有进行第一次操作 $4$ 的时候才会取得更小的代价，特判即可。

code

int n,m;
char s[505][505];
int a[505][505];
int ans=0;

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>(s[i]+1);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=s[i][j]!='W';
	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];
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans+=a[i][j];
	for(int i=1;i<n;i++) for(int j=1;j<m;j++) if(a[i][j]&&a[n][j]&&a[i][m]&&a[n][m]){ ans--;goto Thanks; }
	Thanks:;
	cout<<ans<<endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17