当前位置：首页 > news >正文

2024/5/28 P1247 取火柴游戏

news 来源：原创 2024/9/30 3:32:28

取火柴游戏

题目描述

输入 $k$ 及 $k$ 个整数 $n_1,n_2,\cdots,n_k$ ，表示有 $k$ 堆火柴棒，第 $i$ 堆火柴棒的根数为
$n_i$ ；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。

谁取走最后一根火柴为胜利者。

例如： $k = 2$ ， $n_1=n_2=2$ ，A 代表你，P 代表计算机，若决定 A 先取：

A： $\rightarrow (1,2)$ ，即从第一堆中取一根。
P： $\rightarrow (1,1)$ ，即从第二堆中取一根。
A： $\rightarrow (1,0)$ 。
P： $\rightarrow (0,0)$ 。P 胜利。

如果决定 $A$ 后取：

P： $\rightarrow (2,0)$ 。
A： $\rightarrow (0,0)$ 。A 胜利。

又如 $k = 3$ ， $n_1=1$ ， $n_2=2$ ， $n_3=3$ ， $A$ 决定后取：

P： $\rightarrow (0,2,3)$ 。
A： $\rightarrow (0,2,2)$ 。
A 已将游戏归结为 $(2, 2)$ 的情况，不管 P 如何取 A 都必胜。

编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取。如果是先取必败，则输出 lose。

输入格式

第一行，一个正整数 $k$ 。

第二行， $k$ 个整数 $n_1,n_2,\cdots,n_k$ 。

输出格式

如果是先取必胜，请在第一行输出两个整数 $a, b$ ，表示第一次从第 $b$ 堆取出 $a$
个。第二行为第一次取火柴后的状态。如果有多种答案，则输出 $\lang b,a\rang$ 字典序最小的答案（即 $b$ 最小的前提下，使
$a$ 最小）。

如果是先取必败，则输出 lose。

样例 #1

样例输入 #1

3 3 6 9

样例输出 #1

4 3 3 6 5

样例 #2

样例输入 #2

4 15 22 19 10

样例输出 #2

lose

提示

数据范围及约定

对于全部数据， $\le 500000$ ， $n_i \le 10^9$ 。

又是参加学校每日题的一天，熟练的点开了题目的算法标签，想看看这个题我有没有一点点涉猎（又是及时放弃的一天（bushi））一看：博弈论。瞬间想起了之前在b站刷到过却放在收藏夹吃灰，于是决定好好看看而不是直接放弃（

让我们分析分析这道题。经典的Nim游戏 P2197 【模板】Nim 游戏
首先我们需要认识到，仅有一堆棋子存在时，出现胜负决断
在这里插入图片描述

n=1: 先手全拿，先手必胜。

n=2:有两种情况，一种可能相同，一种情况一堆比另一堆少（多）
    (m,m) 按照“有一学一，照猫画猫”法，先手必输。(m,M)先手先从多的一堆中拿出(M-m)个，此时后手面对(m,m)的局面先手必胜。
术语:正经人称(m,m)的局面为奇异局势
n=3:(m,m,M)先手必胜局，先手可以先拿M,之后变成了(m,m,0)的局面，是不是很熟悉~

(a1,a2,a3)的话，举个例子(1,2,3),先手取完之后可能的局面为(0,2,3),(1,1,3),(1,0,3),(1,2,2),(1,2,1),(1,2,0)都是之前讲过的，情况如下：

这些的结果可以总结为：异或均为0

这块的异或到底是怎么蹿出来的，我觉得洛谷题解有一篇说的挺有意思

异或有一个特殊的规律，就是一堆数异或时，若在同一个二进制位上1的个数是偶数，那么这一位异或起来以后是0，否则为1

二进制的话就是可以使用0/1表示所有数字

我们来看上一个游戏，我们将这两堆的剩余的火柴数转变成二进制。

发现我们先手取走一个数，就是改变其二进制为上的1的个数（只考虑奇偶性），而后手再去取的话就是将其奇偶性再变回来

然后我们再回去看为什么异或和是0时先手必输，因为先手拿走了某些火柴时，我们可以根据其拿走火柴的二进制表示，在其他一堆中拿走一些一些数字，使得其异或和重新为0；

怎么搞呢？我们可以拿走一些数，也就是减某一个数，使得先手拿完后，（啰嗦警告）

所有堆中的每个二进制上的一的个数的和，我们总可以通过加减一个数，达到在某一个二进制位的1的个数进行加一or减一的效果

使得某一位二进制上的1的个数变为偶数。

从而使得游戏又恢复到了一开始的局面
题解

在这里插入图片描述

先手必胜，即先手可以拿走一些火柴，使得后手必败，而必败态是火柴堆的异或和为零；那么我们求的，就是先手拿走一些火柴后，新的火柴堆异或和为零的方案。设原异或和为X

当(a2 xor X)<a2时，能取走火柴。

#include <iostream>
#include<algorithm>using namespace std;
int k, n[500100], x;int main()
{cin >> k;for (int i = 1; i <= k; i++){cin >> n[i];x ^= n[i];}if (x == 0) { cout << "lose"; return 0; }for (int i = 1; i <= k; i++){if ((n[i] ^ x) < n[i]){cout << n[i] - (n[i] ^ x) << " " << i << endl;n[i] = n[i] ^ x;break;}}for (int i = 1; i <= k; i++){cout << n[i] << " ";}return 0;
}