打卡信奥刷题（3136）用C++实现信奥题 P7589 黑白棋（2021 CoE-II B）

P7589 黑白棋2021 CoE-II B题目描述Alice\text{Alice}Alice和Bob\text{Bob}Bob正在玩一种称为“黑白棋”的游戏。该游戏的规则如下游戏在直角坐标系中进行。Alice\text{Alice}Alice执黑棋Bob\text{Bob}Bob执白棋。初始时在直角坐标系中任选nnn条与XXX轴平行的直线直线在YYY轴上的截距均为整数且互不相同。Alice\text{Alice}Alice在每条直线上都会放置一枚黑棋Bob\text{Bob}Bob在每条直线上都会放置一枚白棋棋子位置的XXX坐标值均为整数。在同一条直线上的两枚棋子位置不会相同。Alice\text{Alice}Alice和Bob\text{Bob}Bob轮流走棋Alice\text{Alice}Alice总是先走棋。每名玩家在走棋时先选择一条直线然后沿着直线移动该条直线上己方颜色的棋子。每个玩家可以将自己的棋子向着靠近对方棋子的方向一次性移动若干整数单位距离称之为前进。每个玩家也可以向着远离对方棋子的方向一次性移动若干整数单位距离称之为后退。只要在前进时不跨过对方的棋子也不使黑棋和白棋的位置发生重叠前进的最远距离不限但是前进的距离至少为111如果无法满足前述条件则玩家不能执行前进操作。为了避免玩家反复后退导致游戏无法结束在一局游戏中某个玩家执行后退操作的总次数不能超过kkk次。与此同时为了防止游戏区域太大以致在显示游戏状态上造成不便每次后退的距离至少为111但不能超过ddd。如果无法满足前述条件玩家不能执行后退操作。玩家在轮到自己走棋时如果能够执行操作就必须执行一次操作此操作可以是前进操作也可以是后退操作如果未超出后退次数的限制。如果某个玩家无法执行任何操作来移动自己的棋子将输掉游戏游戏结束。给定游戏的初始状态假设Alice\text{Alice}Alice和Bob\text{Bob}Bob在游戏时均采用最佳策略试确定Alice\text{Alice}Alice能否获胜。输入格式输入包含多组测试数据。输入第一行包含一个整数TTT表示测试数据的组数。接着是一个空行。接下来是TTT组表示游戏初始状态的数据。每组数据的第一行包含三个整数nnnkkkddd表示直线的数量允许后退的总次数每次后退的最大距离。接下来是nnn行数据每行包含三个整数yiy_iyi​bib_ibi​wiw_iwi​分别表示第iii条直线的YYY轴截距以及在该条直线上的黑棋的XXX坐标值和白棋的XXX坐标值bi≠wib_i \ne w_ibi​wi​。每两组测试数据之间有一个空行。输出格式如果Alice\text{Alice}Alice能够获胜输出Yes否则输出No。输入输出样例 #1输入 #12 2 0 10 3 4 8 7 7 5 3 5 15 -3 -9 -19 -7 10 21 12 12 16输出 #1Yes No说明/提示样例说明下图对应输入 #1 的第一组数据如果Alice\text{Alice}Alice采用最优策略无论Bob\text{Bob}Bob如何走棋Alice\text{Alice}Alice都能够获胜。以下是Alice\text{Alice}Alice的必胜策略。首先Alice\text{Alice}Alice选择将y3y3y3的直线上的黑棋从4移动到6使得两条直线上黑棋和白棋之间的间距均为222由于kkk为000相当于不允许执行后退操作如果Bob\text{Bob}Bob选择移动y3y3y3直线上的白棋将使得该直线上的两颗棋子相邻后续无法再移动。同样的如果Bob\text{Bob}Bob选择移动y7y7y7直线上的白棋也将使得该直线上的两颗棋子相邻后续无法再移动。因此无论Bob\text{Bob}Bob如何操作总会使得一条直线上的两颗棋子相邻无法再继续移动而另外一条直线上的棋子间距为222还可以再移动一次Alice\text{Alice}Alice将剩下可以移动的黑棋再移动一步后后续Bob\text{Bob}Bob无法移动白棋因此Alice\text{Alice}Alice会获胜。对于输入 #1 的第二组数据无论Alice\text{Alice}Alice如何走棋Bob\text{Bob}Bob总能够获胜。数据范围对于100%100\%100%的数据1≤T≤1001 \le T \le 1001≤T≤1001≤n≤1001 \le n \le 1001≤n≤1000≤k≤1000 \le k \le 1000≤k≤1001≤d≤201 \le d \le 201≤d≤20−100≤yi≤100-100 \le y_i \le 100−100≤yi​≤100−103≤bi≤103-10^3 \le b_i \le 10^3−103≤bi​≤103−103≤wi≤103-10^3 \le w_i \le 10^3−103≤wi​≤103。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;intt,a,b,c,d,e;intread(){longlongX0,w1;charcgetchar();while(c0||c9){if(c-)w-1;cgetchar();}while(c0c9)XX*10c-0,cgetchar();returnX*w;}signedmain(){tread();while(t--){aread(),bread(),cread(),b0;//输入for(inti0;ia;i)cread(),dread(),eread(),b^((de)?(e-d-1):(d-e-1));puts((b)?Yes:No);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容