筷子游戏

设当前玩家的一指手、二指手数量为 $a,c$，对方的对应数量为 $b,d$，并令 $n=a+c$、$m=b+d$。

给一指手赋权 $2$，二指手赋权 $1$。每次攻击都会使双方的总权值减少，因此不会平局。没有手的玩家失败。对总权值进行强归纳，可以同时证明以下结论。

• 若 $n>m$，则获胜。
• 若 $m\geq n+2$，则失败。
• 若 $n=m$，则当且仅当 $b=m$ 且 为奇数时失败。

当 $n>m$ 时，如果能够消灭对方的一只手，就这样做。对方在下一回合至少落后两只手，因此失败。如果不能立即消灭手，双方就都只有一指手。将对方的一只手变成二指手后，对方的手更少，而且有二指手，不满足少一只手时的特殊获胜条件。

当 $m\geq n+2$ 时，无论如何攻击，对方剩下的手都更多，因此对方获胜。

当 $m=n+1$ 时，不消灭手的攻击会让对方继续领先。要获胜，必须消灭一只手，使数量相等，并让下一位玩家处于同数量的必败状态。这要求当前玩家的手全是一指手。此时只能消灭对方的二指手，对方的一指手数量不变，所以恰好得到上述三个条件。

当 $n=m$ 且对方有二指手时，可以消灭一只手，让对方处于少一只手的必败状态。若对方有至少两只二指手，消灭其中一只即可。若对方只有一只二指手，自己有二指手，且对方还有一指手，则消灭对方的一指手。若自己全是一指手，则消灭对方的二指手。剩余情形中对方只有一只手，直接消灭即可获胜。

若对方全是一指手，用自己的二指手消灭对方的一只手，当且仅当 $a$ 为偶数时是获胜操作。用一指手攻击一指手，当且仅当自己也全是一指手且 $n$ 为偶数时是获胜操作。合并可知，恰好在 $a$ 为奇数时失败。

子任务 1 可以用四种手的数量作为状态进行记忆化搜索，每次攻击后交换双方的角色。设初始手数的最大值为 $K$，状态数为 $O(K^4)$。提供的实现使用有序映射，时间复杂度为 $O(K^4\log(K+1))$，空间复杂度为 。 时足够。

子任务 2 中，当且仅当 $N>M$，或者 $N=M$ 且 $N$ 为偶数时，先手获胜。完整问题将 $n=N,m=M,a=a_1,b=b_1$ 代入判定条件即可。二者的时间和空间复杂度均为 。输入以及 的计算应使用 64 位整数。

独立处理每个测试用例。总时间为 $O(T)$，额外空间为 $O(1)$。暴力实现跨测试用例共享记忆化结果，总时间为 $O(T+K^4\log(K+1))$，空间为 。不会逐一展开每只手，因此无需限制手的数量之和。

Solution written by GPT