1293C - NEKO‘s Maze Game(分块、贡献)

题目

思路:可以知道每一个点要想造成一个不能通过的结果,需要它的正对面 左对面 右对面 ,1岩浆0空地 故我们将其贡献算为,如果当前为x,y为1->0,则贡献减少lst[3-x][y]+lst[3-x][y-1]+lst[3-x][y+1],如果为0->1则减少,另y=1或n时特殊判断。

Code:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<vector>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e6 + 5;
int lst[3][Max];

int main()
{
   
	int n, q;cin >> n >> q;
	int sum = 0;
	for (int i = 1;i <= q;i++)
	{
   
		int x, y;cin >> x >> y;
		if (lst[x][y])
		{
   
			if (y == 1)  sum -= lst[3 - x][y] + lst[3 - x][y + 1];
			else if (y == n)  sum -= lst[3 - x][y] + lst[3 - x][y - 1];
			else sum -= lst[3 - x][y - 1] + lst[3 - x][y] + lst[3 - x][y + 1];
		}
		else
		{
   
			if (y == 1)  sum += lst[3 - x][y] + lst[3 - x][y + 1];
			else if (y == n)  sum += lst[3 - x][y] + lst[3 - x][y - 1];
			else sum += lst[3 - x][y - 1] + lst[3 - x][y] + lst[3 - x][y + 1];
		}
		lst[x][y] ^= 1;
		if (sum)cout << "No" << endl;
		else cout << "Yes" << endl;
	}
}

全部评论

相关推荐

这一集&nbsp;硕士输的很惨
找工作ing10:就是这样不是硕士不愿意脱下长衫,是人家觉得屈才了
点赞 评论 收藏
分享
06-06 03:40
已编辑
电子科技大学 Java
在秋招的小白菜很想养修勾:一眼 苍穹外卖+谷粒商城,项目换一换吧,可以找一些付费知识星球博主带带,避免烂大街。多投投大厂,背背八股,你这学历乱杀了,等实习经验到位,到时候大厂闭眼选
投递美团等公司8个岗位
点赞 评论 收藏
分享
每晚夜里独自颤抖:这个在牛客不是老熟人了吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务