Alice and Recoloring 1题解

1.前言

差分大法好

---

2.题解

如果 (i,j) 这一位置是 black，令 a[i][j] = 1，否则 a[i][j] = 0。

Hint 0:

不会对同一个位置使用多次同一种操作（应该很好证明，略）。

---

Hint 1:

操作 2 和操作 3 没有用。

对 (x, y) 使用操作 2 可以通过对 (n, y), (x - 1, y) 使用操作 3 来替换，操作 3 的替换方法类似，只会赚取费用而不会亏损费用。

操作 4 只能用 4 费用代替：对 (n, m), (x - 1, m), (n, y - 1), (x - 1, y - 1) 使用操作 1，可以赚 1 费用。

但是如果两次使用操作 4，我们就没有必要操作两次 (n, m) 了，这样操作费用就都为 6 费用了。

所以用操作 1 替换操作 4 的相差费用周期是: -1, 0, -1, 0…。不妨可以看作是只使用一次操作 4。

---

Hint 2:

我们先排开操作 4.

d[i][j] = 1表示对 (i, j) 要进行操作 1，d[i][j] = 0 表示不对 (i, j) 进行操作 1。

那么 a[i][j] 的含义就是 (i,j) 的 后缀操作 1 的和 模 2（当然也等价于异或和）。

$$a[i][j]=(\sum _{x=i}^n\sum _{y=j}^{m}d[i][j])\mathrm{m}\mathrm{o}\mathrm{d}2$$

那么我们可以通过这个式子反推 a[i][j]。

这个式子是一个典型的后缀和式子，马上可得

$$d[i][j]=(a[i][j]-a[i+1][j]-a[i][j+1]+a[i+1][j+1])\mathrm{m}\mathrm{o}\mathrm{d}2$$

所以不考虑操作 4 的答案是

$$\sum _{i=1}^n\sum _{j=1}^{m}d[i][j]$$

再来考虑操作 4 用在哪里。由 Hint 1 可知，它可以代替对 (n, m), (x - 1, m), (n, y - 1), (x - 1, y - 1) 使用操作 1，并节省 1 费用，所以说判断

$$p:\exists x,[d[n][m]=1]\wedge [d[x-1][m]=1]\wedge [d[n][y-1]=1]\wedge [d[x-1][y-1]=1]$$

如果是个真命题，那么答案就需要减去 1。否则就不变。

---

参考代码