牛牛和牛可乐的赌约2时间限制2秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述牛牛感觉在上一次赌约中情况对于自己非常不利所以决定再赌一场。这时候牛蜓队长出现了第一绝对不意气用事第二绝对不漏判任何一件坏事第三绝对裁判的公正漂亮。牛蜓队长带他们来到了一个棋盘游戏棋盘左上角是( 0 , 0 ) (0,0)(0,0)这个棋盘在( x , y ) (x,y)(x,y)的位置有一个棋子牛牛和牛可乐轮流移动这个棋子这个棋子可以左移也可以上移可以移动一格或者两格直到不能再移动即到( 0 , 0 ) (0,0)(0,0)的那个人算输。如果原本在( x , y ) (x,y)(x,y),左移一格即为( x , y − 1 ) (x,y−1)(x,y−1)上移一格即为( x − 1 , y ) (x−1,y)(x−1,y)这个时候牛牛为了弥补上一局的不公平决定要自己先手如果两个人都用最优的策略最后牛牛是否能获胜。输入描述有多组输入样例第一行为样例组数t t ≤ 1 × 10 6 tt≤1×10^6tt≤1×106接下来t tt行每行有一个整数x xx和y yy分别表示初始位置 x , y ≤ 1 × 10 9 x,y≤1×10^9x,y≤1×109输出描述输出t行如果牛牛获胜就输出” y y d s ” ”yyds””yyds”不带引号否则输出” a w s l ” ”awsl””awsl”示例1输入2 0 0 0 2输出awsl yyds解题思路本题是经典**组合博弈SG函数尼姆博弈**问题。棋子每次可向上/向左移动1格或2格走到( 0 , 0 ) (0,0)(0,0)的玩家落败。先推导单维度状态的SG函数得出单个坐标k kk的SG值为k m o d 3 k \bmod 3kmod3。二维坐标( x , y ) (x,y)(x,y)等价于两个独立博弈叠加总SG值为( x m o d 3 ) ⊕ ( y m o d 3 ) (x\bmod3) \oplus (y\bmod3)(xmod3)⊕(ymod3)。博弈规则总SG为0时先手必败反之先手必胜等价于判断x m o d 3 x\bmod3xmod3与y m o d 3 y\bmod3ymod3是否相等。每组查询仅需两次取模运算复杂度O ( 1 ) O(1)O(1)可高效应对t ≤ 10 6 t\le10^6t≤106、坐标值达10 9 10^9109的海量查询。总结核心逻辑通过SG函数找到博弈胜负的周期规律将复杂移动博弈简化为模3比较。关键操作推导一维SG周期、利用尼姆博弈异或判定胜负、快速取模处理每组询问。效率保障纯常数级运算无预处理与循环开销完美适配百万级查询与超大数值范围。代码简要说明利用ans[3][3]预存所有模3组合的胜负结果下标相等代表必败0输出awsl不等代表必胜1输出yyds。开启快读优化应对10 6 10^6106组大数据输入。对每组坐标x , y x,yx,y分别对3取模查表直接输出对应结果逻辑极简且运行高效。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll x,y;cinxy;ll ans[3][3]{{0,1,1},{1,0,1},{1,1,0}};if(ans[x%3][y%3])coutyydsendl;elsecoutawslendl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T1;cinT;while(T--)solve();return0;}