P7589 黑白棋(2021 CoE-II B)


传送门

简化题意

有很多条线,每条线上都有两人的棋,靠近对方的棋叫前进,远离叫后退,后退有次数的距离限制,而前进没有,先走走不了的一方输。

情况分析

后退不需考虑:一方只要后退,对方就可以前进相同的距离。

那么,现在只用考虑前进了,当两人的棋挨在一起的时候,本条线就走不了了。

因为两人足够聪明,所以当他们发现情况不利时,会尽量打破这种可能,举个例子:

—-A——B—-(A:Alice B:Bob)

如果只有一条线,Alice 的棋会直接对到 Bob 的棋的前面,取得胜利;但是如果还有一条两人的棋没有对到一起的情况,Alice 就不会这么做,但她可以对到 Bob 的棋的前一个格处。

———A-B—-(A:Alice B:Bob)

这样另一条线的 Bob 的棋不会直接对上,为了这种解决情况,他也会在另一条线上,对在 Alice 的棋的前面的一格,而这种情况,Alice 会必输。

所以聪明的 Alice 在一开始,为了后面有路可走,可能会如下:

——-A—B—-(A:Alice B:Bob)

而 Bob 也会随机应变……

因为两方都非常聪明,就可能会出现每个人的棋就会一步一步向前走。

异或处理

我们就可以统计两人的间距和来判断谁先无路可走,我们可以在这里用异或快速处理。

例如:

—-A—-B—-

—-A—-B—-

两人一步一步走,可以想象 Alice 只走上面,Bob 只走下面,会发现两人走的次数相同,异或一下就抵消了。

代码

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<map>
#include<utility>
using namespace std;
int r_r(){//快读 
  int x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
int t;//多测 
int b_b;//判断输赢 
int main(){
  t=r_r();
  while(t--){
    int n=r_r(),k=r_r(),d=r_r();
    b_b=0;//多测清空 
    while(n--){
      int y=r_r(),b=r_r(),w=r_r();
      b_b^=abs(b-w)-1;//异或距离,注意两点距离为 abs(a-b)-1 
    }
    if(!b_b)cout<<"No"<<endl;//结果输出 
    else cout<<"Yes"<<endl;
  }
  return 0;
}

文章作者: 王大神——A001
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 王大神——A001 !
  目录