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 k2k2n 1 n 2 2 n_1n_22n1​n2​2A 代表你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 k3k3n 1 1 n_11n1​1n 2 2 n_22n2​2n 3 3 n_33n3​3A 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输入 #13 3 6 9输出 #14 3 3 6 5输入输出样例 #2输入 #24 15 22 19 10输出 #2lose说明/提示数据范围及约定对于全部数据k ≤ 500000 k \le 500000k≤500000n 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_kxn1​⊕n2​⊕⋯⊕nk​。若x 0 x 0x0先手必败输出lose。若x ≠ 0 x \neq 0x0先手必胜需要构造一步操作使得操作后异或和变为0 00。构造必胜步对第i ii堆若将其变为t n i ⊕ x t n_i \oplus xtni​⊕x则新的异或和为x ⊕ n i ⊕ t 0 x \oplus n_i \oplus t 0x⊕ni​⊕t0。由于必须取走至少一根需满足t n i t n_itni​即取走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 1i1到k kk顺序扫描找到第一个满足t n i t n_itni​的堆即可。2. 算法实现读入k kk和数组a [ 1.. k ] a[1..k]a[1..k]同时计算异或和x ^ a[i]。若x 0输出lose并结束。否则遍历i 1 i 1i1到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构造必胜步。顺序扫描保证字典序最小。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N500010;constll INF1e18;constll M1e610;constll mod1e97;ll a[N];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll k;scanf(%lld,k);ll x0;for(ll i1;ik;i){scanf(%lld,a[i]);x^a[i];}if(!x){puts(lose);return0;}for(ll i1;ik;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 i1;ik;i)printf(%lld ,a[i]);return0;}