莫妮卡的博弈游戏
莫妮卡的博弈游戏
HITwh 23
我是多久没写过题解了，感觉自己已经快要废掉了(≧﹏ ≦)
题目来源：HITwh OJ(学校内网的oj，外网不能访问。。。。。)
时间限制: 1000ms 内存限制: 64M
题目描述
你最近从Steam上下载了一款名为《心跳文学社》的游戏，然后你开始玩，但逐渐地你发现一个问题，无论你使用什么方法，你都无法攻略游戏中一个名为莫妮卡的角色。随着游戏的进行，你发现你逐渐地无法控制游戏的走向，更糟糕的是，你发现莫妮卡十分清楚她正处于一个游戏当中，接着她破坏了你的游戏存档文件。为了拯救你的存档，你决定与莫妮卡玩一个游戏，如果你获胜了就可以恢复你的存档文件。
游戏规则是这样的：在你面前有\(N\)个单词，每一个单词都有一个类似好感值的属性\(X_i\)，你和你莫妮卡轮流进行每个回合的操作。在每个回合中，玩家必须从这\(N\)个单词中选择两个，然后把这两个单词组合成一个新的单词，假设之前的两个单词的好感值分别为\(X_a\)与\(X_b\)，那么新单词的好感值可以是$ X_a − X_b \(或者\) X_b − X_a $。游戏将持续进行直到只剩下一个单词，这个单词的好感值Xf将决定游戏的胜负。
如果$ X_f % 3==0 \(，那么当前回合进行操作的玩家失败； 如果\) X_f % 3==1 \(，那么你获胜； 如果\) X_f % 3==2 $，那么莫妮卡获胜。 注意，这里的取模运算是数学意义上的，比如说：\(3\%3=0\)，\(1\%3=1\)，\(−1\%3=2\)，结果不会为负数。
我们都知道，AI是十分聪明的，这意味着莫妮卡每次都会选择最佳的操作方式。而你为了拯救你的存档，你学习了博弈论的相关知识，这意味着你每次也会选择最佳的操作方式。
现在你想知道对于一个给定的局面，谁将成为最后的胜利者。
输入
输入包含多行。 第一行为一个整数\(T(1≤T≤233)\)，代表测试用例的组数。 对于每组测试用例，第一行为两个整数，分别是单词的数量\(N (1≤N≤233)\)和先进行操作的玩家\(F∈{0,1}\)，如果\(F=0\)，则你先进行操作，否则由莫妮卡先进行操作。 接下来的一行为N个整数，代表第i个单词的好感值\(X_i (−233≤Xi≤233)\)。
输出
对于每组测试用例，如果你能获胜，则在新的一行中输出"WIN"，否则输出"LOST"。 如果你觉得不能确定谁会获胜，就输出"OUTPUT THIS TO GET WA"。
样例输入
3
1 0
9
3 1
1 2 3
5 0
1 3 5 7 9
样例输出
LOST
WIN
LOST
题解
这一题乍一看很复杂，但是其中其实可以找到很巧妙的规律。我们可以发现最后的答案是与\(\%3\)的值有关的，也就是说，对于n个数\(\{x_1,x_2,x_3 ,\dots ,x_n\}\)，我们可以将其转化为\(\{ x_1\%3 , x_2\%3 , x_3\%3 , \dots ,x_n\%3 \}\)，而答案不变。在这种情况的基础下我们研究能够出现必胜策略的情况。
当\(n==1\)时
我们可以根据\(n,k,x_1\)的值来推断谁能获胜。其方程如下：
\[ Answer = \left\{ \begin{aligned} WIN & ， & x_1\%3=1 \\ LOST & , & x_1\%3=2 \\ WIN & ， & k=1 \ \&\&\ x_1\%3=0 \\ LOST & ， & k=0 \ \&\&\ x_1\%3=0 \\ \end{aligned} \right. \]
当\(n==2\)时
对于\((x_1,x_2)\)我们可以得出共有以下5种情况： \[\{ (0,0) , (1,1) , (2,2) , (0,1) , (0,2) , (1,2) \}\] 而因为我们只能进行减法运算，所以我们可以得出\(\{ (0,0),(1,1),(2,2)\}\),\(\{ (0,1),(1,2)\}\)都是相等的，所以我们最后只有\(\{ (0,0),(0,1),(0,2)\}\)三种情况。
我们假设第一步由"我"来下，即\(k=0\)。那么，对于以上三种情况： ##### (0,0) 因为下一局变为\((0)\),所以答案为WIN ##### (0,1) 我们有两种选择 $ 0-1 $ 和 $ 1-0 $ ,第一种\(\%3\)后为\(2\),第二种为\(1\)。因为我们总会选择最佳策略，所以肯定会选择\(1-0\)，然后获胜。 ##### (0,2) 我们也有两种选择$ 0-2 $ 和 $ 2-0 $ ，第一种为\(2\),第二种\(\%3\)后为\(1\)。同理，我们会选择\(0-2\)，所以我们一定能获胜。
总结
当\(n==2\)时，无论\(x_1,x_2\)为多少，当前进行操作的人一定能获胜。
所以当\(n>2\)时，我们不需要关注\(x_i\)的数值，而只需要关注当最后选至\(n==2\)时谁进行操作，即： \[ Answer = \left\{ \begin{aligned} WIN & , & (n+k)\%2=0\ ,\ n>1 \\ LOST &, & (n+k)\%2=1\ ,\ n>1 \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
27
28
29
30
31
32
33
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d%d",&n,&k);
int x;
for (int i = 1; i<=n; i++)
scanf("%d",&x);
if (n==1)
{
if (x%3==1)
printf("WIN\n");
else if (x%3==2)
printf("LOST\n");
else{
if (k==0)
printf("LOST\n");
else printf("WIN\n");
}
}
else if ((n+k)%2==1)
printf("LOST\n");
else printf("WIN\n");
}
return 0;
}