dp+观察，CF 1864 D. Matrix Cascade

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

https://codeforces.com/problemset/problem/1864/D

---

二、解题报告

1、思路分析

经过观察，我们操作一个格子，受影响的应该是以该格子为直角向下延伸出的一个等腰直角三角形

那么同理，上面能够影响到本格子的区域是以该格子为直角顶点向上延伸出的一个等腰直角三角形

我们只关注D被操作次数的奇偶性

我们定义f(i, j) 为 格子 (i, j) 为直角顶点的上三角区域的总操作次数的奇偶性

那么 f(d) = d(a) ^ f(b)

为什么不计算C？

因为C被累加两次，异或偶数次的贡献不计

如果奇偶性 和 当前格子的值不同，那么需要额外操作一次，所以 f(D) ^= 1

具体实现，我们滚动数组优化f(i, j)，然后用diag1[] 和 diag2[] 分别代表主对角线和副对角线的异或次数奇偶性，这样用三个一维数组就能完成求解

2、复杂度

时间复杂度： O(N^2)空间复杂度：O(N)

3、代码详解

 ​

#include <bits/stdc++.h>
// #include <ranges>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 1'000'000'007;
constexpr int inf32 = 1E9 + 7;void solve() {int n;std::cin >> n;std::vector<std::string> g(n);for (int i = 0; i < n; ++ i) std::cin >> g[i];std::vector<int> f(n), diag1(2 * n), diag2(2 * n);int res = 0;for (int i = 0; i < n; ++ i) {for (int j = 0; j < n; ++ j) {f[j] ^= diag1[i - j + n] ^ diag2[i + j];if (f[j] != (g[i][j] & 1)) {++ res;f[j] ^= 1;diag1[i - j + n] ^= 1;diag2[i + j] ^= 1;}}}std::cout << res << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) {solve();}return 0;
}