简化题意
有很多条线,每条线上都有两人的棋,靠近对方的棋叫前进,远离叫后退,后退有次数的距离限制,而前进没有,先走走不了的一方输。
情况分析
后退不需考虑:一方只要后退,对方就可以前进相同的距离。
那么,现在只用考虑前进了,当两人的棋挨在一起的时候,本条线就走不了了。
因为两人足够聪明,所以当他们发现情况不利时,会尽量打破这种可能,举个例子:
—-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;
}