题目直接找链接

题意：

　　有一个2*n大的平面，有的格子不能走，有的格子可以走，最初状态所有格子都可以走，有q个操作，每个操作都把某个格子变化一下：能走变不能走，不能走变能走，输出每次操作之后能否从1，1到

2，n。合法的走法：有共同边的格子可以相互到达。

solve：

　　思维题，考虑一下有什么特殊的性质吧：怎样快速的判断能不能到达呢，其实很简单：只要有一个“卡死”的就过不去，没有“卡死”的就可以过去，什么叫“卡死”呢，想一想，只要有对角线相邻的或者上下相邻的不能走的格子，就“卡死”了。

　　ps:我们学OI的可不能有一个卡死的就过不去了，我们要学会转换，解决问题，“跳一跳”把“卡死”的格子跳过去，就算都是“卡死”的，我们也要努力通过，正如：不拼一把，怎么知道自己有多优秀，我们OIer要有“所向隔山海，山海皆可平”的信念，要有“明知山有虎，偏向虎山行”的勇气，要有“舍我其谁”的信心。这才是OI该有的样子嘛，想这种有一个对角线卡住就过不去了，不是我们的性格。

　　说多了。。。，回到题目：那我们要做什么呢？记录有多少卡死的，然后判断，如果有卡死的，那么它肯定过不去，如果没有卡死的，那么就能过去。怎么记录呢？方法可能很多，我随便举一种：记录每个格子的状态，每改变一个格子，就看可能构成死路的格子的状态，然后再进行判断，更新一共有多少个卡死的数目，更新完之后，判断一下有没有卡死的就可以了。

　　还有一个小小的问题：1，1or2，n是不能通过的格子怎么办呢，仔细研读一下原题，这样应该也是不可以的，所以我们再加一个特判就可以了。

　　ps：翻译的时候要注意，你粘贴到翻译器上的10⁵很有可能变成105，这个还好，算法想对了影响不大，有的数据10⁹（算上加和很有可能超int）变成了109，于是你的用的int，于是就。。。

#include <cstdio>

const int maxn=1e5+;

bool zt[maxn][];

int x[]={-,-,,,,};//算是一个小技巧吧，大家应该都会。

int y[]={-,,-,,-,};

int main(){

    int dd=;

    int n,q;

    scanf("%d%d",&n,&q);

    int js1,js2;

    for(int i=;i<=q;i++){

        scanf("%d%d",&js2,&js1);

        zt[js1][js2]=!zt[js1][js2];

        if(zt[js1][js2])

            for(int i=;i<;i++)

                if(js1+x[i]>=&&js1+x[i]<=n&&js2+y[i]>=&&js2+y[i]<=)

                    if(zt[js1+x[i]][js2+y[i]])

                        dd++;

        if(!zt[js1][js2])

            for(int i=;i<;i++)

                if(js1+x[i]>=&&js1+x[i]<=n&&js2+y[i]>=&&js2+y[i]<=)

                    if(zt[js1+x[i]][js2+y[i]])

                        dd--;//这两个循环应该是可以合并的，不过我感觉这样写可能更好理解一些

        if(!dd&&!zt[][]&&!zt[n][])

            printf("Yes\n");

        else

            printf("No\n");

    }

    return ;

}

巴特西

洛谷CF1292A NEKO's Maze Game，还是思维。。。

题目直接找链接

题意：

solve：

最新文章

热门文章