题解：P16010 [CCO 2016 Day 2] O Canada 哦！加拿大

DGFLSzfd · 2026-05-08 19:44:25 · 题解

题意

给定 G 个 N \times N 的红白网格。每次操作可以反转任意一个 2 \times 2 子网格的颜色。求这 G 个网格中，共有多少对网格可以通过若干次操作变得完全相同。

思路

遇到“从一个状态变到另一个状态”的题，我们的第一反应肯定是搜索，但计算复杂度后，易知这样的方式不可行。

分别思考操作和操作的自由度：

• 操作：无关先后，只有一个方块翻过和没翻过的区别。符合交换律，具有自反性。

• 自由度：网格大小是 N \times N，一共有 N^2 个格子。
  但是，一个 2 \times 2 的方块，它的左上角只能放在前 N-1 行和前 N-1 列里。所以，我们总共只有 (N-1)^2 种不同的翻转操作。
  格子总数 N^2 减去操作总数 (N-1)^2，得到剩余信息数为 N^2-(N-1)^2=2N-1 也就是说，总有 2N-1 个格子的状态无法通过操作随意改变。

做法呼之欲出：与其去判断 A 能不能变成 B，不如把每个网格都用同样的方法处理，把左上角的 (N-1)\times (N-1) 区域强行改成白色，再判断剩下的部分是否一样。

具体来说，我们从左上到右下扫描前 N-1 行和前 N-1 列。如果当前格子是红色，就翻转以它为左上角的 2 \times 2 方块。这样当前格子一定会变成白色，并且之后的操作不会再影响它。

经过这套操作后，左上角的 (N-1)\times (N-1) 区域都会变成白色，只剩下最后一行和最后一列需要判断。它们的格子数正好是 2N-1。

受自由度的限制，如果两张网格最初是相似的，经过这套操作后，它们最后剩下的残局必须完全一样。

对于剩下的残局，利用状态压缩，变成一个数即可快速计算答案。

代码

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

const int N=15;
char s[N][N];

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n,g;cin>>n>>g;

    vector<int>v;

    while(g--)
    {
        for(int i=0;i<n;i++)
            cin>>s[i];

        for(int i=0;i<n-1;i++)
        {
            for(int j=0;j<n-1;j++)
            {
                if(s[i][j]=='R')
                {
                    s[i][j] ^= 'R' ^ 'W';
                    s[i + 1][j] ^= 'R' ^ 'W';
                    s[i][j + 1] ^= 'R' ^ 'W';
                    s[i + 1][j + 1] ^= 'R' ^ 'W';
                }
            }
        }

        int sta=0;//计算特征码
        for(int i=0;i<n;i++)
            if(s[i][n-1]=='R')sta|=(1<<i);
        for(int j=0;j<n-1;j++)
            if(s[n-1][j]=='R')sta|=(1<<(n+j));
        v.push_back(sta);
    }

    sort(v.begin(),v.end());

    v.push_back(-1);//哨兵
    long long ans=0;
    int cnt=1;
    for(int i=1;i<(int)v.size();i++)
    {
        if(v[i]==v[i-1])
            cnt++;
        else
        {
            ans+=1ll*cnt*(cnt-1)/2;
            cnt=1;
        }
    }

    cout<<ans;

    return 0;
}

启示：寻找等价类的标准型

对于满足交换律与自反性的操作模型，状态图的连通性本质上是等价类划分问题，穷举转移路径是低效且冗余的。

通过分析操作矩阵的自由度，我们可以利用贪心消元策略，将所有受控变量强制统一为零状态基底。

降维后剩余的不可控区域即为该等价类唯一的标准型，直接比对该特征掩码即可严格判定初始状态的同构关系。