1293C - NEKO‘s Maze Game（分块、贡献）

桃扇骨 2021-07-16 18:43 221阅读 0赞

[题目][Link 1]

思路：可以知道每一个点要想造成一个不能通过的结果，需要它的正对面 左对面 右对面 ，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;
    	}
    }

[Link 1]: https://codeforces.ml/problemset/problem/1293/C

发表评论取消回复

表情：

评论列表（有 0 条评论，221人围观）

还没有评论，来说两句吧...

相关阅读

相关分块算法

1. 简介存储系统的重复数据删除过程一般是这样的：首先将数据文件分割成一组数据块，为每个数据块计算指纹，然后以指纹为关键字进行Hash查找，匹配则表示该数据块为重复数据块，

以你之姓@/ 2024年02月19日 19:20/ 0 赞/ 36 阅读

相关 Stone Game（C++石子游戏）

解题思路：（1）贪心算法 class Solution { public: bool stoneGame(vector<int>& pil

旧城等待，/ 2023年01月07日 03:58/ 0 赞/ 119 阅读

相关分块查找

一概述分块查找又称作索引顺序查找，它吸取了顺序查找和折半查找各自的有点，既有动态结构，又适于快速查找。二分块查找的基本思想将查找表分为若干子块，块内的元

绝地灬酷狼/ 2022年12月07日 00:40/ 0 赞/ 234 阅读

相关 Jump Game（C++跳跃游戏）

（1）贪心算法 class Solution { public: bool canJump(vector<int>& nums) {

末蓝、/ 2022年10月11日 00:53/ 0 赞/ 176 阅读

相关 The Maze 1, 2

[https://blog.csdn.net/zshouyi/article/details/72974347][https_blog.csdn.net_zshouyi_art

冷不防/ 2022年05月13日 01:58/ 0 赞/ 128 阅读

相关 Codeforces Round #554 Div.2 C - Neko does Maths

数论 gcd 看到这个题其实知道应该是和(a+k)(b+k)/gcd(a+k,b+k)有关，但是之后推了半天，思路全无。然而。。有一个引理: gcd(a, b

Bertha 。/ 2022年01月07日 05:19/ 0 赞/ 129 阅读

相关分块

　　晚上脑子涨涨的，就总结一下最近写的分块入门9题吧。以下全是个人浅薄理解。　　分块，一般就是把一组数据分成sqrt(n)块，然后根据题目要求，对其进行维护。基本要写的就是

淩亂°似流年/ 2021年12月07日 14:11/ 0 赞/ 312 阅读

相关整除分块（数论分块）

转载自[此博客][Link 1] 整除分块：给定n，求（Σd=1n ⌊n /d⌋）%998244353，n<=1e14 直接枚举会爆考虑优化：我们发现

绝地灬酷狼/ 2021年11月01日 03:40/ 0 赞/ 361 阅读

相关 1293C - NEKO‘s Maze Game（分块、贡献）

[题目][Link 1] 思路：可以知道每一个点要想造成一个不能通过的结果，需要它的正对面左对面右对面，1岩浆0空地故我们将其贡献算为，如果当前为x,y为1->0

桃扇骨/ 2021年07月16日 18:43/ 0 赞/ 222 阅读

相关 C. Floor and Mod (分块整除)

[题目][Link 1] a/b=i, a%b=i -> a=i\(b+1)，(对于一个b可以配出几个i就可以产生几个贡献)可以知道对于给出的x,y 取任意1<=b<=y

系统管理员/ 2021年07月16日 12:00/ 0 赞/ 372 阅读