喵~ 主人，欢迎来到我的题解小站 nya~

今天我们要解决的是一道关于矩阵变换的可爱问题，Li Hua and Pattern！这道题需要我们动动小脑筋，想一想怎样才能用刚刚好的操作次数，把一个图案变得中心对称。别担心，跟着我的思路一步步来，很快就能明白的喵！

题目大意

我们有一个 n x n 大小的图案，上面的每个格子要么是蓝色（用 0 表示）要么是红色（用 1 表示）。我们有不多不少，正好 k 次操作机会。每一次操作，我们可以选择任意一个格子，把它变成相反的颜色（蓝变红，红变蓝）。

问题是：我们能不能在用完恰好 k 次操作之后，让这个图案变成一个“中心对称”的图案呢？

中心对称是什么意思呢？就是一个图案旋转 180 度之后，看起来和原来一模一样。就像我倒立着看主人，主人还是那么帅气一样喵~

解题思路

要解决这个问题，我们需要分两步走，就像猫猫捕猎一样，先观察，再出击！

第一步：需要多少次操作才能让图案对称？

一个图案要实现中心对称，对于任意一个位于 (i, j) 的格子，它的颜色必须和它对称位置 (n-1-i, n-1-j) 的格子颜色相同。

所以，我们首先要做的，就是找出最少需要多少次操作才能满足这个条件。我们可以遍历整个矩阵，比较每一对对称格子 grid[i][j] 和 grid[n-1-i][n-1-j] 的颜色。

如果它们的颜色不一样，那我们就必须修改其中一个，这就需要 1 次操作。我们把所有颜色不同的对称格子对找出来，这个数量就是我们最少需要的操作次数，我们叫它 min_ops 吧。

怎么计算 min_ops 呢？ 我们可以设置一个计数器 mismatches。遍历整个 n x n 的格子，如果 grid[i][j] != grid[n-1-i][n-1-j]，就给 mismatches 加一。 遍历完后，我们会发现每一对不匹配的格子 (i, j) 和 (n-1-i, n-1-j) 都被我们数了两次（一次在 (i, j)，一次在 (n-1-i, n-1-j)）。所以，真正需要修改的“格子对”的数量就是 mismatches / 2。 因此，min_ops = mismatches / 2。

第二步：剩下的 k - min_ops 次操作怎么办？

现在我们知道了最少需要 min_ops 次操作。

1. 如果给定的 k 比 min_ops 还小，那我们连最基本的要求都达不到，肯定是不可能完成任务的。所以，如果 k < min_ops，直接回答 "NO" 就好啦。

2. 如果 k >= min_ops，说明我们有足够的操作次数。在用掉了 min_ops 次操作之后，图案已经变得中心对称了。但我们手上还剩下 remaining_ops = k - min_ops 次操作，题目要求我们必须恰好用完 k 次，所以这些剩下的操作也得用掉！

那么，我们怎么才能在不破坏对称性的前提下，用掉这些 remaining_ops 次操作呢？

• 如果 remaining_ops 是偶数： 这太简单了喵！我们可以找一个格子，把它变色，再变回来。这样就用掉了 2 次操作，图案没变，对称性也没被破坏。或者，我们可以找一对本来就颜色相同的对称格子，把它们两个同时变色，也用掉了 2 次操作，图案依然对称。所以，只要剩下的操作是偶数次，我们总能成对地消耗掉它们。这种情况，答案是 "YES"。

• 如果 remaining_ops 是奇数： 这就有点麻烦了。成对消耗的方法行不通了，我们需要一种只用 1 次操作，还不破坏对称性的方法。 想一想，什么情况下翻转一个格子，对称性不会被破坏呢？只有当这个格子和它对称的格子是同一个格子的时候！ 也就是 (i, j) 和 (n-1-i, n-1-j) 是同一个点。这要求 i = n-1-i 且 j = n-1-j，解出来就是 2i = n-1 和 2j = n-1。 这个方程要有整数解，n-1 必须是偶数，也就是说 n 必须是奇数！ 当 n 是奇数时，矩阵正中央的那个格子 (n/2, n/2) 就是它自己的对称点。我们可以翻转它一次，消耗 1 次操作，并且图案仍然保持中心对称。 所以，如果 remaining_ops 是奇数，只有当 n 也是奇数时，我们才能消耗掉这多出来的 1 次操作。否则，如果 n 是偶数，就不存在中心点，我们无法消耗奇数次操作，答案就是 "NO"。

总结一下逻辑喵：

1. 计算出最少需要修改的次数 min_ops。
2. 如果 k < min_ops，输出 "NO"。
3. 否则，计算剩余操作 remaining_ops = k - min_ops。
4. 如果 remaining_ops 是偶数，输出 "YES"。
5. 如果 remaining_ops 是奇数，当且仅当 n 是奇数时，输出 "YES"，否则输出 "NO"。

这个逻辑可以合并成一个判断：k >= min_ops 并且 ((k - min_ops) % 2 == 0 或者 n % 2 == 1)。

题解代码

这是我的 C++ 实现，加了一些可爱的注释，希望能帮到主人喔~ nya!

#include <iostream>
#include <vector>
#include <numeric>

void solve() {
    int n;
    long long k;
    std::cin >> n >> k;
    std::vector<std::vector<int>> grid(n, std::vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> grid[i][j];
        }
    }

    // 一个图案中心对称，意味着 (i, j) 和 (n-1-i, n-1-j) 的颜色总是一样的喵
    // 我们来数一数有多少个格子的颜色和它对称位置的格子颜色不一样
    int mismatches = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] != grid[n - 1 - i][n - 1 - j]) {
                mismatches++;
            }
        }
    }

    // 每一对不匹配的格子都被我们数了两次，所以需要修复的“格子对”数量是 mismatches / 2
    // 修复一对格子只需要 1 次操作，所以最少操作数就是 mismatches / 2
    int min_ops = mismatches / 2;

    // 如果 k 都没达到最低要求，那肯定不行啦
    if (k < min_ops) {
        std::cout << "NO\n";
        return;
    }

    // 计算用完最少操作数后，还剩下多少次操作
    long long remaining_ops = k - min_ops;

    // 如果 n 是奇数，那么矩阵正中间有一个点，我们可以用它来消耗奇数次操作
    // 如果剩下的操作是偶数次，我们总能成对地消耗掉它们，比如翻转一个格子再翻转回来
    // 所以，只要满足 n 是奇数，或者剩余操作是偶数，就一定有办法用完所有操作
    if (n % 2 == 1 || remaining_ops % 2 == 0) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍

这道题虽然简单，但也涉及了一些在算法竞赛中很有用的思想，我来给主人梳理一下喵~

1. 中心对称 (Centrosymmetry) 这是一个几何概念，在矩阵问题中也很常见。对于一个 n x n 的矩阵 A，如果它满足 A[i][j] = A[n-1-i][n-1-j]，我们就称它为中心对称矩阵。理解这个性质是解决本题的第一步。

2. 奇偶性分析 (Parity Analysis) 这是本题的核心！问题的关键不在于具体的操作，而在于操作次数的奇偶性。我们发现，在满足基本要求后，多余的操作能否被消耗掉，完全取决于剩余操作次数 k - min_ops 的奇偶性，以及矩阵大小 n 的奇偶性。这种“不关心具体值，只关心奇偶性”的思维方式在很多构造题和博弈论题目中都非常重要，是解决问题的利器！

好啦，今天的题解就到这里啦！希望我的讲解对主人有帮助喵~ 如果还有不懂的地方，随时可以再来问我喔！拜拜~