题解：P11975 [KTSC 2021] 翻牌游戏 / card

· · 题解

题目传送门

题目大意 作者看了好久才弄明白

给定一个初始全为 X 的 N \times N 网格，目标是通过翻转操作使其变成给定的目标图案 P。

翻转操作规则：

每次选择一行或一列，并选择一个整数 k（0 \leq k < M）。
如果选择行 i，则翻转该行中所有满足 j \equiv k \pmod{M} 的位置 (i,j)。
如果选择列 j，则翻转该列中所有满足 i \equiv k \pmod{M} 的位置 (i,j)。

发现翻转操作具有模 M 的周期性，因此可以将网格划分为若干个 M \times M 的独立子网格。

每个子网格 (a,b)（0 \leq a,b < M）包含所有满足 i \equiv b \pmod{M} 的行和 j \equiv a \pmod{M} 的列的交点。

对于每个子网格 (a,b)，选定一个基准点 (i_0,j_0)。

其他点 (i,j) 的值必须满足：P[i][j] = P[i_0][j_0] \oplus P[i_0][j] \oplus P[i][j_0]

其中 \oplus 表示异或（即 X 为 0，O 为 1）。

若不满足该条件，则无法通过翻转操作得到目标图案。

遍历所有可能的余数对 (a,b)（0 \leq a,b < M）。

对于每个 (a,b)，收集所有行 i \equiv b \pmod{M} 和列 j \equiv a \pmod{M}。

检查该子网格是否满足基准点约束，若任意子网格不满足，则直接返回 false。

可以直接以步长 M 遍历行和列，避免无效检查。在检查过程中，一旦发现不满足条件的点，立即终止并返回 false。

代码

#include <bits/stdc++.h>
using namespace std;

bool reversal(int N,int M,vector<string> P){
    for (int a = 0;a < M;a++){
        for (int b = 0;b < M;b++){
            vector<int> r;
            for (int i = b;i < N;i += M) r.push_back(i);
            if (r.empty()) continue;
            vector<int> c;
            for (int j = a;j < N;j += M) c.push_back(j);
            if (c.empty()) continue;
            int ii = r[0],jj = c[0];
            int ba = (P[ii][jj] == 'O');
            for (int i : r){
                for (int j : c){
                    int rv = (P[ii][j] == 'O');
                    int cv = (P[i][jj] == 'O');
                    if ((P[i][j] == 'O') != ba ^ rv ^ cv) return false;
                }
            }
        }
    }
    return true;
}

// int main()
// {
//     int n,m;
//     string str;
//     vector<string> p;
//     cin >> n >> m;
//     for (int i = 1;i <= n;i++){
//         cin >> str;
//         p.push_back(str);
//     }
//     cout << reversal(n,m,p) << endl;
//     system("pause");

//     return 0;
// }

怎么这道题都那么久了还没有人写题解？