首页 > 其他分享 >题解:P10543 [THUPC 2024 决赛] 黑白

题解:P10543 [THUPC 2024 决赛] 黑白

时间:2024-08-07 10:51:53浏览次数:15  
标签:P10543 THUPC int 题解 奇偶性 && 1010

好题。

题意

\(n\times m\) 的网格图初始每个格子有黑有白,两人轮流操作,每次选择一个白格染黑。操作后不能存在一条 \((1,1)\) 到 \((n,m)\) 的路径,否则本次操作者输,另一人赢。

思路

首先判断是否一上来就输了。

易发现到最后一定会操作到只剩一条道路,设路径长度为 \(s\),那么 \(s\) 的奇偶性一定和 \(n+m-1\) 奇偶性一样,而我们只要知道 \(s\) 的奇偶性就可求出答案。

AC Code

#include<bits/stdc++.h>
using namespace std;
int t,n,m,s;
string c;
bitset <1010>v[1010],w[1010];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void dfs(int x,int y){
	w[x][y]=1;
	for(int i=0;i<4;i++){
		int xa=dx[i]+x,ya=dy[i]+y;
		if(xa>0&&ya>0&&xa<=n&&ya<=m&&v[xa][ya]&&!w[xa][ya])dfs(xa,ya);
	}
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		s=0;
		for(int i=1;i<=n;i++){
			w[i].reset();
			cin>>c;
			for(int j=1;j<=m;j++)v[i][j]=c[j-1]=='W',s+=v[i][j];
		}
		dfs(1,1);
		if(!w[n][m]){cout<<"J\n";continue;}
		if((s-n-m)&1)cout<<"J";
		else cout<<"I";
		puts("");
	}
	return 0;
}

标签:P10543,THUPC,int,题解,奇偶性,&&,1010
From: https://www.cnblogs.com/AUBSwords/p/18346592

相关文章

  • 题解:UVA11181 条件概率 Probability|Given
    主要思路:概率期望。首先可以发现\(n\)的数据极小。然后我们设\(a\)为为每个人买东西的情况,\(b\)为当有\(b\)个人去时的情况。大家都应该知道条件概率式子为\(P(a|b)=\frac{P(ab)}{P(b)}\)。然后暴力搜索\(P(ab)\)和\(P(b)\)。其实这道题有复杂度更低的dp做法,但......
  • 题解:CF1896G Pepe Racing
    主要思路:构造。思路方法一一个一个的找,分别查询\([1,n],[n+1,2n],\dots,[n(n-1)+1,n^{2}]\)中最快的人,再把\(n\)个人合起来查询,不过很明显的是,这个方法很蠢,并不能切掉此题。方法二找第二快的人,只有最快的人在的一组需重新询问,剩下答案无需改变。需排除的人的一组用不是现......
  • 2024牛客暑期多校训练营7 C Array Sorting 题解
    乱搞非正解写法。分类讨论各种情况。降序排序对应交换即可数组个数小直接考虑相邻的交换其他都看做随机数据考虑结合前面情况,很容易想到,先把数组变成一个尽量有序的数组(每个元素和自己正确的位置相差不大)。最后再多次相邻交换,使得每个元素都在正确位置。把数组变成......
  • 洛谷 P4910题解
    题目大意现在穿T次手串,每根手串的长度分别为不同的n,有木和金两种珠子,相邻两颗珠子必须有一个是金。题目思路分析我们现在设穿到第n个珠子时用金的方案数为f[1][n],用木的方案数为f[0][n]如果第n个珠子为金,那么前一颗珠子是什么都可以,因此f[1][n]=f[1][n-1]+f[0][n-1]而如果......
  • CF573E Bear and Bowling 题解
    Description给定一个长度为\(n\)的序列\(a_{1\dotsn}\)。你要求一个\(a\)的子序列\(b_{1\dotsm}\)(可以为空),使得\(\sum_{i=1}^mib_i\)的值最大。\(n\le10^5\),\(|a_i|\le10^7\)。Solution有一个显然的dp是设\(f_{i,j}\)表示前\(i\)个数,选\(j\)个数的......
  • CF1920D题解
    题面这里不再赘述了,直接搬个链接。InLuoguInCodeforces思路存储一共两种操作:要么在末尾加一个数xxx,要么把整一段复制......
  • NSSCTF靶场题解(6)
    站在小白的视角上,写了在写题目的wp方面更多是想体现题目思考的逻辑和细节,更多是写给同样新手小白的内容,解题方面为什么从这一步到下一步的,很助于培养思考题目的逻辑思维,尽我所能把细节阐释到位,有些地方可能理解说辞不是特别到位,如果有问题就麻烦各位大佬师傅指点~这次题解库收......
  • 题解:CF257C View Angle
    题目传送门题意平面上有\(n\)个点。从原点引出两条射线,将平面分成两个部分,使其中一个部分覆盖所有的点。求这个部分与原点所夹的角的最小度数。思路既然一个部分覆盖了所有的点,那么另一个部分就一个点都没覆盖,那么要让这个部分最优,这两条射线一定经过两个中间没有任何点的点......
  • 【题解】暑假集训CSP提高模拟14
    目录Rank&挂分A.BA题目内容部分分10pts10+20pts正解思路代码B.BB题目内容部分分5pts正解思路代码C.BCD.BDRank&挂分T4暴搜后来改了记搜,不知道哪里锅了,挂5pts。A.BA题目内容现在有\(m\)块烙板,\(n\)张饼,第\(i\)张饼需要烙\(a_i\)个单位时间,一张饼一个单位时刻只能......
  • 2024MX-MF-DAY1-text题解
    T1【题目描述】有\(n\)个人按编号从\(1\)到\(n\)坐成一圈,即第\(i\in[1,n]\)个人右边是\(i+1\),第\(n\)个人右边的人是\(1\)。初始,每个人手上有\(m\)个球。随后,\(n\)个人按编号从小到大的顺序依次执行如下操作:把自己手中的球分成数量相同且尽可能多的三份,......