#bYybttg060707. 1669:S-Nim
1669:S-Nim
好的,我将这道题整理为清晰的题面格式,并补充样例解释、数据范围与时空限制:
题目描述
原题来自:HDU 1536
两个人玩游戏,规则如下:
- 有 堆石子,分别有 颗石头;
- 每次从一堆石子中取走若干石子,可取的石子数必须是集合 中的一个;
- 谁无法操作谁输。
多组数据,对于每组数据,给定集合 ,然后给出 个局面(每个局面给出石子堆数 和各堆石子数 ),判断每个局面是必胜态(W)还是必败态(L)。
输入格式
输入多组数据,每组数据格式如下:
第一行:第一个整数 ,如果 表示数据结束;否则后面跟着 个整数 ,表示可取石子数的集合。
第二行:一个整数 ,表示询问的局面数。
接下来的 行,每行描述一个局面:
- 第一个整数 ,表示石子堆数;
- 接下来 个整数 ,表示每堆石子的数量。
输出格式
对于每组数据,输出一行长度为 的字符串,其中第 个字符表示第 个局面的胜负情况:
W表示先手必胜(Winning position)L表示先手必败(Losing position)
样例
样例输入
2 2 5
3
2 5 12
3 2 4 7
4 2 3 7 12
5 1 2 3 4 5
3
2 5 12
3 2 4 7
4 2 3 7 12
0
样例输出
LWW
WWL
样例解释
第一组数据:
- ,可取石子数集合 。
- 个询问。
-
第一个局面:,石子数 。
计算每堆的 SG 值(根据可取石子数集合 ):- SG(0)=0
- SG(1)=0(因为无法取 2 或 5,没有合法移动)
- SG(2)=mex{SG(0)}=1
- SG(3)=mex{SG(1)}=1
- SG(4)=mex{SG(2)}=mex{1}=0(因为只能取 2 或 5,5 大于 4 不能取,只能取 2 到 SG(2)=1)
- SG(5)=mex{SG(0),SG(3)}=mex{0,1}=2
- SG(6)=mex{SG(1),SG(4)}=mex{0,0}=1
- SG(7)=mex{SG(2),SG(5)}=mex{1,2}=0
- SG(8)=mex{SG(3),SG(6)}=mex{1,1}=0
- SG(9)=mex{SG(4),SG(7)}=mex{0,0}=1
- SG(10)=mex{SG(5),SG(8)}=mex{2,0}=1
- SG(11)=mex{SG(6),SG(9)}=mex{1,1}=0
- SG(12)=mex{SG(7),SG(10)}=mex{0,1}=2
局面 1:SG(5)=2, SG(12)=2,异或和 = 2⊕2=0,所以先手必败 →
L。 -
第二个局面:,石子数 。
SG(2)=1, SG(4)=0, SG(7)=0,异或和 = 1⊕0⊕0=1≠0,先手必胜 →W。 -
第三个局面:,石子数 。
SG(2)=1, SG(3)=1, SG(7)=0, SG(12)=2,异或和 = 1⊕1⊕0⊕2=2≠0,先手必胜 →W。
所以第一组输出 LWW。
第二组数据:
- ,可取石子数集合 。
- 个询问。
类似计算 SG 值(实际上可取任意 1~5 个,SG 值循环规律明显),计算各局面异或和:
- 石子 5,12 → SG(5)=?, SG(12)=? 计算得异或和非 0 →
W; - 石子 2,4,7 → 异或和非 0 →
W; - 石子 2,3,7,12 → 异或和为 0 →
L。
所以第二组输出 WWL。
数据范围
对于全部数据:
时空限制
- 时间:
- 内存:
提示
这是 Nim 游戏的限制取法版本(Take-away Game 的多堆版本)。
对于给定的集合 ,我们可以预处理 到 的 SG 值。
递推公式:
然后对于每个局面,计算所有堆的 SG 值的异或和:
- 若异或和 ≠ 0,先手必胜(W);
- 若异或和 = 0,先手必败(L)。