牛牛和牛可乐的赌约2【牛客tracker 每日一题】

牛牛和牛可乐的赌约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 ） t（t≤1×10^6）t（t≤1×106）
接下来t tt行每行有一个整数x xx和y yy，分别表示初始位置（ x , y ≤ 1 × 10 9 ） （x,y≤1×10^9）（x,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周期、利用尼姆博弈异或判定胜负、快速取模处理每组询问。
效率保障：纯常数级运算，无预处理与循环开销，完美适配百万级查询与超大数值范围。

代码简要说明

1. 利用ans[3][3]预存所有模3组合的胜负结果：下标相等代表必败（0，输出awsl），不等代表必胜（1，输出yyds）。
2. 开启快读优化，应对10 6 10^6106组大数据输入。
3. 对每组坐标x , y x,yx,y分别对3取模，查表直接输出对应结果，逻辑极简且运行高效。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;voidsolve(){ll x,y;cin>>x>>y;ll ans[3][3]={{0,1,1},{1,0,1},{1,1,0}};if(ans[x%3][y%3])cout<<"yyds"<<endl;elsecout<<"awsl"<<endl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T=1;cin>>T;while(T--)solve();return0;}