三角尼姆【牛客tracker 每日一题】

三角尼姆时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给出一个正三角形棋盘两方必须轮流在棋盘上摆放棋子每次可以摆放一枚或三枚棋子但所摆放的棋子必须相连一直线且一格中最多只能放一枚棋子放下最后一枚棋子的人是输家。下图给出了在N 8 N8N8时的一些可行的动作这个时候 B o b BobBob和 A l i c e AliceAlice在这个棋盘上下棋且总是 B o b BobBob先手请问谁会胜。输入描述第一行一个正整数T , 1 ≤ T ≤ 10 T,1≤T≤10T,1≤T≤10代表测试数据的组数每组输入在一行中给出一个正整数N NN代表三角形棋盘的变长1 ≤ N ≤ 100 1≤N≤1001≤N≤100输出描述每组输入在一行中输出胜者示例1输入2 1 2输出Alice Alice解题思路本题属于组合博弈奇偶性分析问题核心结论由操作的奇偶性性质直接推导得出与棋盘具体形状无关。总格子数计算边长为n nn的正三角形棋盘总格子数为等差数列求和S n ( n 1 ) 2 S \frac{n(n1)}{2}S2n(n1)​。操作性质分析每次可放置1枚或3枚棋子两种操作放置的数量均为奇数。因此无论选择哪种操作放置后剩余空位数的奇偶性必然翻转。必败态推导规则规定放置最后一枚棋子的人落败。当仅剩1个空位时当前玩家必须放置最后一枚直接落败因此剩余1个空位是必败态奇数。由于每次操作必然翻转奇偶性可递推得出所有剩余空位为奇数的局面都是必败态所有剩余空位为偶数的局面都是必胜态。胜负判定若总格子数S SS为奇数先手Bob初始面对奇数空位处于必败态Alice获胜。若总格子数S SS为偶数先手Bob可放置1枚棋子将局面变为奇数必败态留给对手Bob获胜。“棋子必须连成直线”的限制不影响最终结论因为单个格子天然满足直线条件玩家始终可以选择放置1枚棋子来保证奇偶性翻转该策略永远合法。算法时间复杂度为O ( 1 ) O(1)O(1)每组测试用例仅需一次计算与判断。总结核心逻辑利用每次操作均为奇数的性质推导出胜负仅由总格子数的奇偶性决定奇数先手败、偶数先手胜。关键操作计算三角形总格子数、判断奇偶性、对应输出胜者。效率保障纯常数级运算无循环与预处理极快响应所有测试用例。代码简要说明输入处理读取测试用例组数T TT逐组读取三角形边长n nn。奇偶性判断通过公式(n1)*n/2计算总格子数对2取模判断奇偶性。结果输出结果为奇数则输出Alice先手Bob必败偶数则输出Bob先手必胜。输入优化关闭同步流加速输入输出适配多组测试场景。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cinT;while(T--){ll n;cinn;if((n1)*n/2%21)coutAliceendl;elsecoutBobendl;}return0;}