冬马和纱的博弈游戏

冬马和纱的博弈游戏

题目来源: HITwh OJ

思路

首先，我们知道，该题目的最终答案与\(\%3\)后的数值有关，所以我们可以得知，对于读入的每一个数，我们对其\(\%3\)后不影响其数值。

此外，我们可以明显的得出，\(\%3\)后相同的数值具有相同的属性，所以我们总共只有三种数值\(0,1,2\)。

冬马和纱的角度

那么，我们从冬马和纱的角度来思考问题。我们假设当前的差\(\%3\)为\(0\)，那么此时无论小木曽雪菜选什么，冬马和纱都选择和她一样的，从而使差一直为\(0\)。因此，若小木曽雪菜先开始，且可以\(1,2\)的个数都是偶数，冬马和纱一定能胜利。

而若是冬马和纱先开始时，我们发现，若是有\(\%3=0\)的数，则我们可以通过先选择\(0\)从而使问题变成如上的问题。若是没有的话，我们假设随便选择一个数\(x(x\in {1,2})\)，然后继续按照上述方案行事的话，若原来\(1,2\)的个数都为偶数的话，最后一定会剩下一个最开始我们选择的数，并且轮到小木曽雪菜选择，从而使差便为\(0\)。

因此，答案很显然了:

\[ Ans = \left\{ \begin{aligned} &Touma Kazusa &,\ &num[1]\%2==0 && num[2]\%2==0 \\ &Ogiso Setsuna &,\ &otherwise \end{aligned} \right.\]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <cstdio>

int a[300];

int main()
{
trueint T;
truescanf("%d",&T);
truewhile (T--)
true{
truetrueint n,f;
truetruescanf("%d%d",&n,&f);

truetrueint num[3];
truetruenum[0] = num[1] = num[2] = 0;

truetruefor (int i = 1; i<=n; i++)
truetrue{
truetruetruescanf("%d",&a[i]);
truetruetruenum[a[i]%3]++;
truetrue}
truetrueif (num[1]%2==0 && num[2]%2==0)
truetruetrueprintf("Touma Kazusa\n");
truetrueelse printf("Ogiso Setsuna\n");
true}
}