专栏首页一Wa哇一天C. NEKO's Maze Game

C. NEKO's Maze Game

题目链接: C. NEKO’s Maze Game

time limit per test:1.5 seconds memory limit per test:256 megabytes inputstandard input outputstandard output

NEKO#ΦωΦ has just got a new maze game on her PC!

The game’s main puzzle is a maze, in the forms of a 2×n rectangle grid. NEKO’s task is to lead a Nekomimi girl from cell (1,1) to the gate at (2,n) and escape the maze. The girl can only move between cells sharing a common side.

However, at some moments during the game, some cells may change their state: either from normal ground to lava (which forbids movement into that cell), or vice versa (which makes that cell passable again). Initially all cells are of the ground type.

After hours of streaming, NEKO finally figured out there are only q such moments: the i-th moment toggles the state of cell (ri,ci) (either from ground to lava or vice versa).

Knowing this, NEKO wonders, after each of the q moments, whether it is still possible to move from cell (1,1) to cell (2,n) without going through any lava cells.

Although NEKO is a great streamer and gamer, she still can’t get through quizzes and problems requiring large amount of Brain Power. Can you help her?

Input The first line contains integers n, q (2≤n≤10^5^, 1≤q≤10^5^).

The i-th of q following lines contains two integers ri, ci (1≤ri≤2, 1≤ci≤n), denoting the coordinates of the cell to be flipped at the i-th moment.

It is guaranteed that cells (1,1) and (2,n) never appear in the query list.

Output For each moment, if it is possible to travel from cell (1,1) to cell (2,n), print “Yes”, otherwise print “No”. There should be exactly q answers, one after every update. You can print the words in any case (either lowercase, uppercase or mixed).

input

5 5
2 3
1 4
2 4
2 3
1 4

output

Yes
No
No
No
Yes

Note We’ll crack down the example test here:

After the first query, the girl still able to reach the goal. One of the shortest path ways should be: (1,1)→(1,2)→(1,3)→(1,4)→(1,5)→(2,5). After the second query, it’s impossible to move to the goal, since the farthest cell she could reach is (1,3). After the fourth query, the (2,3) is not blocked, but now all the 4-th column is blocked, so she still can’t reach the goal. After the fifth query, the column barrier has been lifted, thus she can go to the final goal again.

题目大意

给你一个2xN的表格,一共有q次查询,每次查询前会有一个表格变成岩浆不能走,或者从岩浆变回了可以总,问你能否从1 1这个表格走到2 n这个位置,可以的话就输出“Yse”,否则就是“No”;

解题思路

表格的变换我们可以用位运算 异或 来处理,问题是我们怎么判断这次变化后是否可行呢?经过画图的多次尝试,我们发现如果这次不行,那么肯定至少有一列都是岩浆或者至少有一个对角线的位置是岩浆,因此我们可以运用类似前缀和的思想,每次统计以变化位置为中心的连着三个对立位置如果该位置是岩浆,就统计对面三个位置有几个熔浆,如果是可以走,那就减去前面位置有几块熔浆如果结果为零那说明可以走,因为没有一块岩浆,如果不唯一就不行,这里为什么呢?你想呀,如果你这个位置查询的时候是0,可以走的说明什么?说明之前他是1不能走,既然之前不能走,那之前的ans肯定包含不能走时的转态,如果上一次这三个位置都是0,ans加的是0,这次减得也是零对结果没影响,如果上次这三个位置是1呢?说明上次ans加了三个1,这次刚好减去这里很巧妙的运用了位运算和前缀和的思想,真的太巧了,膜拜大神们呀!

代码

#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+10;
int a[2][mx];

int main()
{
    int q,ans=0,n;
    cin>>n>>q;
    int x,y;
    while(q--)
    {
        cin>>x>>y;
        x--;//x--,方便以后的 ^ 运算 
        a[x][y]^=1;//改变这个位置的状态 
        int m=a[x][y]*2-1;//如果是 0 就是可以走,那结果就要减,1的话加 
        ans+=m*(a[x^1][y-1]+a[x^1][y]+a[x^1][y+1]);//进行ans的累加 
        if(ans==0)
        cout<<"Yes"<<'\n';
        else cout<<"No"<<'\n';
    }
    return 0;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • D. Shortest and Longest LIS

    time limit per test3 seconds memory limit per test256 megabytes inputstandard in...

    某些人
  • 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)-G.Projection

    Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged...

    某些人
  • POJ-2585-Window Pains

    Window PainsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 2915 ...

    某些人
  • RFC2616-HTTP1.1-Header Field Definitions(头字段规定部分—单词注释版)

    zaking
  • InfoGAN、GAN训练不稳定因素分析

    Many people have recommended me the infoGAN paper, but I hadn't taken the time t...

    用户1908973
  • RND 笔记

    RND: https://blog.openai.com/reinforcement-learning-with-prediction-based-reward...

    用户1908973
  • Best Practices for Speeding Up Your Web Site(网站优化)

    80% of the end-user response time is spent on the front-end. Most of this time i...

    阿dai学长
  • Create a natural language classifier that identifies spam

    With the advent of cognitive computing and smart machines, machine learning and ...

    首席架构师智库
  • What are x509 certificates? RFC? ASN.1? DER?

    So, RFC means Request For Comments and they are a bunch of text files that descr...

    战神伽罗
  • AMD Zen-2 物理设计总结

    Last year AMD introduced the Zen 2 microarchitecture, the company’s second major...

    白山头

扫码关注云+社区

领取腾讯云代金券