JZOJ2020年8月10日提高组T3 玩诈欺的小杉

题目

Description

是这样的，在小杉的面前有一个N行M列的棋盘，棋盘上有\(N*M\)个有黑白棋的棋子（一面为黑，一面为白），一开始都是白面朝上。

小杉可以对任意一个格子进行至多一次的操作（最多进行\(N*M\)个操作），该操作使得与该格同列的上下各2个格子以及与该格同行的左右各1个格子以及该格子本身翻面。

例如，对于一个\(5*5\)的棋盘，仅对第三行第三列的格子进行该操作，得到如下棋盘（0表示白面向上，1表示黑面向上）。

00100

01110

00100

对一个棋盘进行适当的操作，使得初始棋盘（都是白面朝上）变成已给出的目标棋盘的操作集合称作一个解法。

小杉的任务是对给出的目标棋盘求出所有解法的总数。

Input

每组测试数据的第一行有3个正整数，分别是N和M和T(1<=N,M<=20,1<=T<=5)

接下来T个目标棋盘，每个目标棋盘N行，每行M个整数之前没有空格且非0即1，表示目标棋盘（0表示白面朝上，1表示黑面朝上）

两个目标棋盘之间有一个空行。

特别地，对于30%的数据，有1<=N,M<=15

Output

对每组数据输出T行，每行一个整数，表示能使初始棋盘达到目标棋盘的解法总数

Sample Input

4 4 2

0010

0111

0010

0110

0111

0010

Sample Output

Hint

对于输入的数据，两个目标棋盘各有一种解法

0000

0010

0000

1011

1101

0111

1011

其中1表示对该格进行操作，0表示不操作

题解

题意

给出一个矩阵，问经过多少次操作使得原矩阵（全0）转换成目标矩阵

每次操作将会翻转当前格子和左右各一个及上下各两个的颜色

分析

题目转一下：多少操作使得目标变成全0

很容易想到状压\(DP\)（今天第3道）

发现，上一列的情况会影响当前这列的选择

看：

现在我们做到了第3列

那么第3列第3行这个位置就必须要翻转

因为到了第4列就无法影响到第2列的那个1了

所以说我们可以构造第0列的01情况

然后根据每列的01情况选取位置进行翻转

最后看一下第\(m\)列是否为全0即可

时间复杂度\(O(2^n*n^3)\)

思考优化

发现翻转和异或十分相似

看一下样例1

第2行和第3行异或

把第2行的状态往下一位，再异或第3行

同理就可以搞定第3列

那么第4列再和第2列异或

搞定

优化至\(O(2^n*n^2)\)

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,t,mx,i,j,ans,er,a[25][25],map[25],c[25];

char ch;

int main()

{

    scanf("%d%d%d",&n,&m,&t);

    mx=(1<<n)-1;

    while (t--)

    {

        ans=0;

        memset(map,0,sizeof(map));

        for (i=1;i<=n;i++)

        {

            j=1;

            ch=getchar();

            while (ch!='0'&&ch!='1') ch=getchar();

            while (ch=='0'||ch=='1')

            {

                a[i][j]=ch-'0';

                ch=getchar();

                j++;

            }

        }

        for (j=1;j<=m;j++)

        {

            er=1;

            for (i=1;i<=n;i++)

            {

                map[j]+=a[i][j]*er;

                er*=2;

            }

        }

        for (map[0]=0;map[0]<=mx;map[0]++)

        {

            for (i=0;i<=m;i++)

                c[i]=map[i];

            for (i=1;i<=m;i++)

            {

                c[i]=(c[i]^c[i-1]^(c[i-1]*2)^(c[i-1]*4)^(c[i-1]/2)^(c[i-1]/4))&mx;

                c[i+1]=(c[i+1]^c[i-1])&mx;

            }

            if ((c[m]&mx)==0) ans++;

        }

        printf("%d\n",ans);

    }

    return 0;

}

JZOJ2020年8月10日提高组T3 玩诈欺的小杉

JZOJ2020年8月10日提高组T3 玩诈欺的小杉

题目

Description

Input

Output

Sample Input

Sample Output

Hint

题解

题意

分析