跨域 java class 主从复制 jquery oracle get upload UIkit 建造师报考条件 vue状态管理 android开发项目 android项目实战 cmd查看mysql版本 matlab图像识别 oracle取第一条数据 less比较级 matlab网页版 centos定时任务 python中的map函数 python中pop函数 javafinally java中数据类型 java接口怎么写 java获取url java绝对值 linux安装 linux远程 linux启动 php开发实例 用流量打电话的软件 python爬虫代码 vue路由跳转 pmbok第六版 安卓adb pr书写效果 劳动节称号 快剪辑去水印 搜狗拼音输入法安装包 wps宏的使用教程 ai投影
当前位置: 首页 > 学习教程  > 编程语言

纪中暑假集训 2020.08.10【NOIP提高组】模拟 T3:玩诈欺的小杉

2020/8/11 19:09:12 文章标签:

玩诈欺的小杉

Description

是这样的,在小杉的面前有一个N行M列的棋盘,棋盘上有NMN*M个有黑白棋的棋子(一面为黑,一面为白),一开始都是白面朝上。
  小杉可以对任意一个格子进行至多一次的操作(最多进行NMN*M个操作),该操作使得与该格同列的上下各2个格子以及与该格同行的左右各1个格子以及该格子本身翻面。
  例如,对于一个5*5的棋盘,仅对第三行第三列的格子进行该操作,得到如下棋盘(0表示白面向上,1表示黑面向上)。

00100
00100
01110
00100
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
0010
0111
0010

0010
0110
0111
0010

Sample Output

1
1

Hint

【样例解释】
对于输入的数据,两个目标棋盘各有一种解法
1:
0000
0000
0010
0000
2:
1011
1101
0111
1011
其中1表示对该格进行操作,0表示不操作

反思&题解

比赛思路: 懵……暴力都懒得打(听说直接输出1有50分!)
正解思路: 我们考虑枚举每一列的每个数,分析题目,发现如果一个点它的左边时1,自己也是1时,就需要进行翻转,我们可以枚举一个第0列的状态,于是便有了一个O(mnT2n)O(mnT*2^n)的算法,理论上可能过得了,但是常数有点大。
我们考虑优化,很显然0101的东西很容易想到位运算,于是我们就可以将每一列的状态记录到一个二进制数里面,再用位运算转移,时间复杂度便可以少一个n

CODE

#include<bits/stdc++.h>
using namespace std;
int n,m,t,a[25][25],zt[25],ztt[25],ans;
int main()
{
	scanf("%d%d%d",&n,&m,&t);
	while (t--)
	{
		char ch=getchar();
		int i,j;
		for (i=1;i<=n;i++)
		{
			for (j=1;j<=m;j++)
			{
				ch=getchar();
				if (ch=='0') a[i][j]=0;
				else a[i][j]=1;
			}
			ch=getchar();
		}
		memset(zt,0,sizeof(zt));
		for (i=1;i<=m;i++)
		{
			int num=1;
			for (j=n;j>=1;j--)
			{
				if (a[j][i]==1) zt[i]+=num;
				num*=2;	
			}
		}
		ans=0;
		int s;
		for (s=0;s<=(1<<n)-1;s++)
		{
			zt[0]=s;
			for (i=1;i<=m;i++)
				ztt[i]=zt[i];
			for (i=1;i<=m;i++)
			{
				zt[i]=(zt[i]^(zt[i-1]<<1)^(zt[i-1]<<2)^(zt[i-1]>>2)^(zt[i-1]>>1)^zt[i-1])&(1<<n)-1;
				zt[i+1]=(zt[i+1]^zt[i-1])&(1<<n)-1;
			}
			if (zt[m]==0) ans++;
			for (i=1;i<=m;i++)
				zt[i]=ztt[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_100077.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?