题解 P3164 【[CQOI2014]和谐矩阵】

Holy_Push · 2019-10-18 09:46:11 · 题解

本来只是试试水的，结果发现过了???于是你可以发现这片题解就是一种乱搞做法。不需要高斯消元，只需要dfs。

考虑m≤20的时候可以怎么做。其实我们可以直接枚举第一行的01状态。然后接下来每一行的状态都可以由上一行推出来。

如果我们已经知道第i行的01情况，现在我们想知道i+1行的01情况怎么办?

其实很简单。比如说我们想知道第i行第j列是0还是1，由于第i-1行第j列的相邻位置有偶数个1（其实就是异或和为0），所以a[i-1][j],a[i-1][j-1],a[i-1][j+1],a[i-2][j],a[i][j]这五个数的异或和为0，进而可以推出a[i][j]=a[i-1][j] xor a[i-1][j-1] xor a[i-1][j+1] xor a[i-2][j]。

于是我们可以通过枚举第一行的状态，进而推出全部的状态。时间复杂度为O(2^mnm)，显然n,m≤40时难以通过。

但是打表发现，通过上述方法枚举出来的方案都是左右对称的。也就是说，我们可以只枚举第一行的左半边，然后对称一下放到右半边即可。这样的时间复杂度就是O(2^\frac{m}{2}nm)，吸口氧就过了。

#include<bits/stdc++.h>
using namespace std;
const int N=100;

int n,m;
int a[N][N];

void pd()
{
    for (int i=m;i>(m+1)/2;i--) a[1][i]=a[1][m+1-i];
    for (int i=2;i<=n;i++)
        for (int j=1;j<=m;j++)
            a[i][j]=a[i-1][j]^a[i-1][j-1]^a[i-1][j+1]^a[i-2][j];
    for (int i=1;i<=m;i++)
        if (a[n][i]^a[n][i-1]^a[n][i+1]^a[n-1][i]) return;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
            putchar(a[i][j]+48),putchar(' ');
        putchar('\n');
    }
    exit(0);
}

void dfs(int x)
{
    if (x>(m+1)/2) {pd();return;}
    a[1][x]=1;dfs(x+1);//防止出现全0，所以先放1
    a[1][x]=0;dfs(x+1);
}

int main()
{
    cin>>n>>m;
    dfs(1);
}