自动搬运

查看原文

来自洛谷，原作者为

	Confringo > 最后在线时间：2025年8月22日17时27分 < 由 exOIso 发送激光

搬运于2025-08-24 23:11:48，当前版本为作者最后更新于2025-04-01 17:37:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

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

给定一个初始全为 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;
// }

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