首页 > 其他分享 >P8933 [JRKSJ R7] 技巧性的块速递推 题解

P8933 [JRKSJ R7] 技巧性的块速递推 题解

时间:2023-06-08 10:13:17浏览次数:64  
标签:10 R7 return P8933 int 题解 sum2 颜色 棋盘

题目传送门

题意:

  • 简单来说就是一个涂色游戏。

  • 有一个 n×m 的棋盘需要涂色。

  • 每格只能涂黑色或白色两种颜色。

  • 横、竖、斜连续 3 格颜色不能相同。

  • 横、竖、斜连续 4 格颜色不能有 3 个相同颜色,即只能是 2 个黑和 2 个白。

  • 最后让你统计出所有符合条件的涂色方式的方案数,并对于 998244353 取模。

思路:

  • 因为连续四个格子一定是 2 黑 2 白,所以如果确定了 (i,j) 点任意方向上与其连续的三个点的颜色,就可以推出 (i,j)(即确定的三个中较少的那种颜色)。例如:

上图中第一行,由于前三个格子已经确定,要想符合条件,第四个只能是较少的黑色。

竖和斜也是同理,图有点丑,就不放了

  • 利用上一个条件我们还可以知道一件事,$(i-4,j)$ 格点与 $(i,j)$ 格点的颜色一定相同。因为根据三个连续格点的颜色就能确定与其相邻的第四个点的颜色,由于这两个点中间三个点是一定的,所以确定的第四个点的颜色也是一定的,所以这两个点的颜色一定一样的。因此这个棋盘其实是由一个 4×4 的小棋盘循环构成的。

  • 利用上面的条件就可以扩展出整个棋盘,不过在斜方向上可能会出问题,我们知道,所有斜行出问题的情况最多只会到 7×7 的范围,因此当 n 或者 m 超过 7 时,可以转化为 7。例如:n=5,m=20 的情况就相当于 n=5,m=7 的情况。

  • 利用这几个条件就可以开始搜索了:

  1. 搜索的简单框架还是很好想的:每次搜一个点,枚举是黑是白,然后接着搜下一个点,当整个棋盘搜索完之后,再去 check 一下,符合的话方案数就加 1。

  2. 接下来还要加一个剪枝:因为上面推出的第二个条件,所以当一个点的横坐标 ≥4 时(即存在 (i-3,j)),就可以直接根据 (i-3,j) 点一直到 (i,j) 点间的点求出 $(i,j)$ 点的颜色,没必要再枚举。

  3. 不过不能问一次搜一次,因为 T≤10^5,会时超。这时可以先预处理出 7×7 范围所有大小的方阵答案,询问时直接输出,就不会时超了。

代码:

请勿抄袭。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;//矩阵的长宽,方案数 
int a[10][10];//矩阵,1表示黑,0表示白 
int p[10][10];//预处理数组,记录答案 
inline bool check()//判断当前填法是否合法 
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i+2<=n)//横向3个颜色不能一样 
			{
				if(a[i][j]==a[i+1][j]&&a[i][j]==a[i+2][j]) return 0;
			}
			if(j+2<=m)//竖向3个颜色不能一样  
			{
				if(a[i][j]==a[i][j+1]&&a[i][j]==a[i][j+2]) return 0;
			}
			if(i+2<=n&&j+2<=m)//右下斜线向3个颜色不能一样 
			{
				if(a[i][j]==a[i+1][j+1]&&a[i][j]==a[i+2][j+2]) return 0;
			}
			if(i-2>=1&&j+2<=m)//右上斜线向3个颜色不能一样  
			{
				if(a[i][j]==a[i-1][j+1]&&a[i][j]==a[i-2][j+2]) return 0;
			}
			/*上面四个条件之所以不判断前面的方向,是因为在前面的循环已经判断过了,向后判断即可*/
			if(i+3<=n)//横向4个不能有3个一样 
			{
				int sum1=0,sum2=0;//黑与白的个数 
				for(int k=i;k<=i+3;k++)
				{
					if(a[k][j]) sum1++;
					else sum2++;
				} 
				if(sum1>=3||sum2>=3) return 0; 
			}
			if(j+3<=m)//同上 
			{
				int sum1=0,sum2=0;
				for(int k=j;k<=j+3;k++)
				{
					if(a[i][k]) sum1++;
					else sum2++;
				} 
				if(sum1>=3||sum2>=3) return 0; 
			}
			if(i+3<=n&&j+3<=m)
			{
				int sum1=0,sum2=0;
				for(int k=0;k<=3;k++)
				{
					if(a[i+k][j+k]) sum1++;
					else sum2++;
				} 
				if(sum1>=3||sum2>=3) return 0;
			}
			if(i-3>=1&&j+3<=m)
			{
				int sum1=0,sum2=0;
				for(int k=0;k<=3;k++)
				{
					if(a[i-k][j+k]) sum1++;
					else sum2++;
				} 
				if(sum1>=3||sum2>=3) return 0;
			}
		}
	}
	return 1;//前面都没return说明合法 
}
inline void dfs(int x,int y)//搜索,x和y表示当前搜索的点 
{
	if(y>m) y=1,x++;//搜完一行则换行 
	if(x>n)//说明全搜完了 
	{
		if(check()) ans++;//合法则方案数加1 
		return;
	}
	if(y>=4)//剪枝,≥4则可以直接确定 
	{
		int sum1=0,sum2=0;
		for(int i=y-3;i<=y-1;i++)//统计颜色 
		{
			if(a[x][i]) sum1++;
			else sum2++;
		}
		if(!sum1||!sum2) return;//如果不合法,则没有搜的必要,直接return 
		if(sum1==1) a[x][y]=1;
		if(sum2==1) a[x][y]=0;
		//取少的作为当前点的颜色 
		dfs(x,y+1);//继续搜索 
		return;
	}
	a[x][y]=1;dfs(x,y+1);
	//涂黑 
	a[x][y]=0;dfs(x,y+1);
	//涂白 
}
int main()
{
	for(int i=1;i<=7;i++)
	{
		for(int j=1;j<=7;j++)
		{
			n=i,m=j;
			ans=0;
			dfs(1,1);
			p[i][j]=ans%998244353;
		}
	}//预处理 
	int T;
	cin>>T;
	while(T--)//询问 
	{
		scanf("%d%d",&n,&m);
		if(n>7) n=7;
		if(m>7) m=7;
		//>7 时可以转化为7的情况 
		printf("%d\n",p[n][m]);
	}
	return 0;
} 

写题解不易,点个赞呗。

标签:10,R7,return,P8933,int,题解,sum2,颜色,棋盘
From: https://www.cnblogs.com/zhangxiao666qwq/p/luogu-P8933.html

相关文章

  • P1751 贪吃虫 题解
    题意:题目传送门在一棵n个结点的树上,有k个贪吃虫去吃食物。每个贪吃虫都走到达食物的唯一路径。当一条贪吃虫通向食物的道路上有另一条贪吃虫,则较远的那只停止移动。多条贪吃虫要进入同一节点时,编号最小的才能进入,其他的停止移动。贪吃虫的移动速度皆为1。一只贪吃虫吃......
  • 【题解】 P2221 [HAOI2012]高速公路
    传送门输入时将\(r\)先减1。发现收费之和为$$ans=\sum\limits_{i=l}^{r}a_i\times(r-l+1)\times(i-l+1)$$化简得\[ans=\sum\limits_{i=l}^{r}a_i\times(-i^2+i\times(r+l)+(r-r\timesl-l+1))\]发现可以用线段树来维护:\(s......
  • Codeforces Round 876 (Div. 2) 题解 A - D
    A.TheGoodArray题目大意给定两个整数\(n\)和\(k\),规定一个\(01\)数列为好的的条件是,对于\(1\simn\)中任意的\(i\),都有:\(a\)的前\(i\)个元素中至少有\(\lceil\frac{i}k\rceil\)个都是\(1\)。\(a\)的后\(i\)个元素中至少有\(\lceil\frac{i}k\rceil\)个都是......
  • 题解:【ARC142D】 Deterministic Placing
    题目链接大佬讲解的太精简了,做点蒟蒻视角的思考补充。下面记摆放棋子的点为黑点,没有摆放棋子的为白点。因为进行无数次操作后,占据节点集合总是唯一,所以黑点一定是在反复横跳;每个位置上只能存在一个黑点,所以每次把移动黑点经过的边拿出来,得到的是若干条不相交的链,并且这些链一定......
  • ABC300F 题解
    前两天忘发出来了,补一下QAQ题目链接题意简述给定一个长度为\(n\)且只包含\(\texttt{o}\)和\(\texttt{x}\)的字符串\(s\)以及正整数\(n\)\(m\)\(k\),令字符串\(T=s^{m}\),求将\(T\)中的\(k\)个\(\texttt{x}\)变成\(\texttt{o}\)之后,\(T\)中连续\(\texttt{o}......
  • P3392 涂国旗 题解
    题目大意题目真的是不说人话......有一个国家的国旗是由一个N*M的方格组成的。如果想要这面国旗合法,就必须满足要求:国旗从上到下必须是白色、蓝色和红色,顺序不能改变。每一种颜色都至少有一行。小a这时候捡到了一块破布,希望你通过涂颜色的方式,把破布成合法的国旗,并且要......
  • 题解 P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
    传送门如题目所言,这就是个线段树合并的板子题。题目大意题目描述首先村落里的一共有\(n\)座房屋,并形成一个树状结构。然后救济粮分\(m\)次发放,每次选择两个房屋\((x,y)\),然后对于\(x\)到\(y\)的路径上(含\(x\)和\(y\))每座房子里发放一袋\(z\)类型的救济粮。然......
  • 【每日一题】LeetCode 786. 第K个最小的素数分数(待补全题解思路)
    题目给你一个按递增顺序排序的数组arr和一个整数k。数组arr由1和若干素数组成,且其中所有整数互不相同。对于每对满足0<i<j<arr.length的i和j,可以得到分数arr[i]/arr[j]。那么第k个最小的分数是多少呢?以长度为2的整数数组返回你的答案,这里answer......
  • 2023上半年(下午)网络工程师试题解析
    2023上半年(下午)网络工程师试题解析试题一(20分)某企业办公楼网络拓扑如图1-1所示。该网络中交换机Switch1-Switch4均是二层设备,分布在办公楼的各层,上联采用千兆光纤。核心交换机、防火墙、服务器部署在数据机房,其中核心交换机实现冗余配置。图1-1问题1(4分)该企业办公网络采用172.16.1......
  • CF1559D2 Mocha and Diana (Hard Version) 题解
    Luogu|Codeforces题意给定两个森林\(A\)和\(B\),均有编号\(1\)到\(n\)的节点,边数分别为\(m_1,m_2\)。现在进行加边操作,但是有两个要求:如果在第一个森林加一条\((u,v)\)的边,第二个森林也要进行同样的操作。反之同理。加边后两个森林依旧是森林。一棵树也是森林。......