P1247 取火柴游戏【洛谷算法习题】-育师

P1247 取火柴游戏

网页链接

P1247 取火柴游戏

题目描述

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

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

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

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

如果决定A AA后取：

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

又如k = 3 k=3k=3，n 1 = 1 n_1=1n1=1，n 2 = 2 n_2=2n2=2，n 3 = 3 n_3=3n3=3，A AA决定后取：

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

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

输入格式

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

第二行，k kk个整数n 1 , n 2 , ⋯ , n k n_1,n_2,\cdots,n_kn1,n2,⋯,nk。

输出格式

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

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

输入输出样例 #1

输入 #1

3 3 6 9

输出 #1

4 3 3 6 5

输入输出样例 #2

输入 #2

4 15 22 19 10

输出 #2

lose

说明/提示

数据范围及约定

对于全部数据，k ≤ 500000 k \le 500000k≤500000，n i ≤ 10 9 n_i \le 10^9ni≤109。

解题思路

本题是Nim 博弈的经典模板题，要求判断先手胜负，若先手必胜则输出字典序最小的第一步取法及取后的状态。

1. 问题等价转化

游戏规则是标准的 Nim 游戏：每次从一堆中取走任意正数根火柴，取走最后一根者获胜。
Nim 定理：设所有堆火柴数的异或和为x = n 1 ⊕ n 2 ⊕ ⋯ ⊕ n k x = n_1 \oplus n_2 \oplus \dots \oplus n_kx=n1⊕n2⊕⋯⊕nk。
- 若x = 0 x = 0x=0，先手必败，输出lose。
- 若x ≠ 0 x \neq 0x=0，先手必胜，需要构造一步操作，使得操作后异或和变为0 00。
构造必胜步：对第i ii堆，若将其变为t = n i ⊕ x t = n_i \oplus xt=ni⊕x，则新的异或和为x ⊕ n i ⊕ t = 0 x \oplus n_i \oplus t = 0x⊕ni⊕t=0。由于必须取走至少一根，需满足t < n i t < n_it<ni，即取走n i − t n_i - tni−t根。这样的i ii一定存在（因为x xx的最高位1 11必然来自某一堆）。
字典序最小：题目要求输出的( b , a ) (b, a)(b,a)字典序最小，即优先最小化堆号b bb，再最小化取走数量a aa。因此只需从i = 1 i = 1i=1到k kk顺序扫描，找到第一个满足t < n i t < n_it<ni的堆即可。

2. 算法实现

读入k kk和数组a [ 1.. k ] a[1..k]a[1..k]，同时计算异或和x ^= a[i]。
若x == 0，输出lose并结束。
否则，遍历i = 1 i = 1i=1到k kk：
- 计算t = a[i] ^ x。
- 若t < a[i]，则：
  - 输出a[i] - t和i（即从第i ii堆取走a[i] - t根）。
  - 更新a[i] = t。
  - 跳出循环。
按顺序输出更新后的数组a aa。

3. 复杂度分析

时间复杂度：读入O ( k ) O(k)O(k)，异或和计算O ( k ) O(k)O(k)，寻找第一步最坏O ( k ) O(k)O(k)，输出O ( k ) O(k)O(k)。总时间复杂度O ( k ) O(k)O(k)。k ≤ 5 × 10 5 k \le 5 \times 10^5k≤5×105，完全可行。
空间复杂度：存储数组a aa需要O ( k ) O(k)O(k)，空间限制 256M 足够。

总结

利用 Nim 博弈的异或和判定先手胜负，并通过将某堆变为n i ⊕ x n_i \oplus xni⊕x构造必胜步。顺序扫描保证字典序最小。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=500010;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll a[N];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll k;scanf("%lld",&k);ll x=0;for(ll i=1;i<=k;i++){scanf("%lld",&a[i]);x^=a[i];}if(!x){puts("lose");return0;}for(ll i=1;i<=k;i++){if((a[i]^x)>=a[i])continue;printf("%lld %lld\n",(a[i]-(a[i]^x)),i);a[i]=a[i]^x;break;}for(ll i=1;i<=k;i++)printf("%lld ",a[i]);return0;}