bzoj 1874: [BeiJing2009 WinterCamp]取石子游戏 (sg函数,要求输出第一步具体方案)

 

1874: [BeiJing2009 WinterCamp]取石子游戏

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 726  Solved: 296
[Submit][Status][Discuss]

Description

小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的,每个人每次可以从一堆石子中取出若干个石子,每次取石子的个数有限制,谁不能取石子时就会输掉游戏。 小H先进行操作,他想问你他是否有必胜策略,如果有,第一步如何取石子。

Input

输入文件的第一行为石子的堆数N 接下来N行,每行一个数Ai,表示每堆石子的个数 接下来一行为每次取石子个数的种类数M 接下来M行,每行一个数Bi,表示每次可以取的石子个数,输入保证这M个数按照递增顺序排列。

Output

输出文件第一行为“YES”或者“NO”,表示小H是否有必胜策略。 若结果为“YES”,则第二行包含两个数,第一个数表示从哪堆石子取,第二个数表示取多少个石子,若有多种答案,取第一个数最小的答案,若仍有多种答案,取第二个数最小的答案。

Sample Input

4
7
6
9
3
2
1
2
 

Sample Output

YES
1 1
Hint
样例中共有四堆石子,石子个数分别为7、6、9、3,每人每次可以从任何一堆石子中取出1个或者2个石子,小H有必胜策略,事实上只要从第一堆石子中取一个石子即可。

数据规模和约定
数据编号 N范围 Ai范围 数据编号 N范围 Ai范围
1 N=2 Ai≤10 6 N≤10 Ai≤10
2 N=2 Ai≤1000 7 N≤10 Ai≤100
3 N=3 Ai≤100 8 N≤10 Ai≤1000
4 N≤10 Ai≤4 9 N≤10 Ai≤1000
5 N≤10 Ai≤7 10 N≤10 Ai≤1000
对于全部数据,M≤10,Bi≤10

HINT

Source

 

思路:有没有解直接sg函数搞。关键在于输出具体方案。

如果存在某个i,在第i堆取走了ok[j]个石头后,恰好使得sum的值变成0(也就是使得从N态到P态的值)

取这样的i和ok[j]中最小的(i是第一关键字,ok[j]是第二关键字)

需要注意的是,在第i堆取走ok[j]之后的sg值 应该为 sum^sg[a[i]]^sg[a[i]-ok[j]],而不是直接sum^sg[a[i]-ok[j]]

可以理解成先撤销了之前计算的a[i]的操作,换成qu

 

hdu 3980 Paint Chain (sg函数,环形串取石子)

hdu 3980 题目链接
题意:一个有n个石子的环形串,初始没有被涂颜色,两个人轮流,涂连续m个没有被涂色的石子,不能操作的人为负。问先手是否有必赢策略。

思路:和hdu2999很像。。所不同的是。。。那道题是线型的珠子。。。这道题是环型的数字。。。

然而我们机智得发现。。。环形的任意涂一次。。就变成了线型的啊orz。。。

所以先随便取一次,然后剩下的n-m个按照线型串的方法搞,划分区间即可。

由于先随便取了一次,所以和线型的交换输赢的结论。。。

以及。。要特判一次都不能取的情况。。。2A

 

 

 

 

hdu 2999 Stone Game, Why are you always there? (sg函数,线性串取石子)

hdu2999题目链接

题意:有一串石子,给定一个集合S,每次只能拿连续x个石子,石子必须是在集合S中的数,问先手是否有必赢策略。需要注意石子的位置是不能变化的,也就是说如果一串连续的石子因为中间有石子被取走,那么这段石子就变成不连续的了,也就不能一次取走。

思路:一开始没有读懂题。需要特别强调的是。石子的位置是不能合并的。。

举个例子,如果我有5个石子,S={2},那么我取完一次剩下的情况是 {3,4,5}或者{1},{4,5}或者{1,2},{5}或者{1,2,3} 一共四种。

题意搞清楚以后就好做了。。类似于bomb game那道题。。我们仍然可以把取一次的操作拆分两个子过程,也就是两个区间。我们不关心区间具体的情况,只关心区间的长度。以及,取完只有一个区间的情况不需要特殊考虑,认为是长度为0就可以了,因为sg[0]为0,不影响答案。

 

 

 

 

hdu 2873 Bomb Game(Sg函数)

hdu 2873题目链接

题意:n*m个格子,有若干炸弹。对于在第一行或者第一列的炸弹,爆炸后会到那一行或者那一列的更前面(总的来说就是更靠近左上角)的位置。对于其他位置的炸弹,爆炸后会生成两个炸弹,分别到那一行的更前面或者那 一列的更前面。问先手是否有必赢策略。

 

思路: 不会做2333
参考了 参考博客1
参考博客2

大概明白了一点。整个游戏可以分为若干个炸弹的游戏的和,而实际上一个不在边界行或者列的炸弹,依然可以继续分,分成两个炸弹的和。而位于(i.j)的炸弹,分成两个炸弹的和,有(i-1)*(j-1)种方案(这个不重要2333)

处于边界行或者列的点的sg值我们是可以知道的。。因为规则单一。。和移动等价。。

然后根据边界来进一步处理一般的情况。。

有点类似dp的思想。。。?

 

 

hdu 2509 Be the Winner (anti-sg,sg函数,sj定理)

hdu2509题目链接
题意:???

思路:同1907

 

 

BZOJ 1022 ||hdu 1907 John (sg函数,sj定理,anti-sg)

hdu1907题目链接

题意:n堆石子,每次选一堆,最少拿一个,最多拿光那一堆,拿走最有一个的人输。  问是否有必胜策略。

思路:anti-nim问题。。。

要用到sj定理(是啥。。。?)

参考资料:参考博客

 

SJ定理

对于任意一个Anti-SG游戏,如果定义所有子游戏的SG值为0时游戏结束,先手必胜的条件:
1、游戏的SG值为0且所有子游戏SG值均不超过1。
2、游戏的SG值不为0且至少一个子游戏SG值超过1。

 

 

hdu 1730 Northcott Game (二维sg函数)

hdu 1730

题意:n行格子,每行m个,每行有一黑一白两个棋子,给定初始位置,先手执黑棋,后手执白棋,每次可以在同一行内向左移动,不能超过边界,且不能越过对方的棋子,同一个格子只能有一个棋子。问先手是否必赢。

 

思路:可以看成n个独立的游戏的 叠加。。。所以最后异或和一下就好。。

我们来求sg函数。。。一开始的是想把点对hash成一个数。。。然后发现其实没必要。。。直接二维就好了。。

由于初始化的时候要考虑最大。。。所以sg函数的值会有一个便宜。。。和设定N有关。。减去偏移就好了。。。(我的代码里这个偏移是11026)

1A蛤蛤蛤

 

 

 

 

 

 

 

 

hdu 1536 S-Nim (sg函数)

hdu 1536题目链接

题意:还是若干堆石子,但是每次取的个数只能是集合S中有的数。。问是否必赢。。。

思路:sg函数。。。1A

 

 

 

hdu 1848 Fibonacci again and again (sg函数)

hdu 1848题目链接

 

题意:三堆石头,每次任选一堆取,取的石子数目必须是斐波那契数列中的数(1,2,3,5,8….)问先手是否有必赢策略。

 

思路:sg函数即可。。。。这次sg函数的优越性终于体现出来了。。。其他方法估计很难写吧。。

以及,这道题不知道为什么让我联想到了生成函数。。。感觉生成函数和sg函数作为工具还是有不少共同点的。。。

 

 

hdu 1850 Being a Good Boy in Spring Festival (nim游戏问必胜方案数,sg函数)

hdu1850题目链接
题意:n堆石子。。每堆可以取任意多个。。。先取完的赢。。问先手能否赢。。能赢的话第一步有几种取法。。
思路:sg函数。。对于方案数,可以用nim游戏的结论。

未命名。设异或和为sum..那么统计满足 a[i]^sum<a[i]的个数就是第一步能走的方案数。

以及。。sg函数。。如果走的步数是任意的。。也就是没有限制。。。那么sg[i] = i…此时也就退化成了一般的nim游戏。。。

 

 

hdu 1847 Good Luck in CET-4 Everybody! (巴什博奕,找规律||sg函数)

hdu1847题目链接
题意:n个石子,每次只能取2的幂次个。。。问先手是否有必赢策略。。。
思路:画n点p点。。。发现n为3的倍数的时候先手必输。。。否则先手必赢。。。

也可以利用sg函数求解。。。
从这里我们可以看出,sg函数类似于母函数,本身并不是一类问题,而是一种求解问题的工具。

hdu 1849Rabbit and Grass(一维nim游戏,sg函数)

Rabbit and Grass

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3058    Accepted Submission(s): 2261

Problem Description

大学时光是浪漫的,女生是浪漫的,圣诞更是浪漫的,但是Rabbit和Grass这两个大学女生在今年的圣诞节却表现得一点都不浪漫:不去逛商场,不去逛公园,不去和AC男约会,两个人竟然猫在寝食下棋……
说是下棋,其实只是一个简单的小游戏而已,游戏的规则是这样的:
1、棋盘包含1*n个方格,方格从左到右分别编号为0,1,2,…,n-1;
2、m个棋子放在棋盘的方格上,方格可以为空,也可以放多于一个的棋子;
3、双方轮流走棋;
4、每一步可以选择任意一个棋子向左移动到任意的位置(可以多个棋子位于同一个方格),当然,任何棋子不能超出棋盘边界;
5、如果所有的棋子都位于最左边(即编号为0的位置),则游戏结束,并且规定最后走棋的一方为胜者。

对于本题,你不需要考虑n的大小(我们可以假设在初始状态,棋子总是位于棋盘的适当位置)。下面的示意图即为一个1*15的棋盘,共有6个棋子,其中,编号8的位置有两个棋子。

大家知道,虽然偶尔不够浪漫,但是Rabbit和Grass都是冰雪聪明的女生,如果每次都是Rabbit先走棋,请输出最后的结果。

 

Input
输入数据包含多组测试用例,每个测试用例占二行,首先一行包含一个整数m(0<=m<=1000),表示本测试用例的棋子数目,紧跟着的一行包含m个整数Ki(i=1…m; 0<=Ki<=1000),分别表示m个棋子初始的位置,m=0则结束输入。

 

Output
如果Rabbit能赢的话,请输出“Rabbit Win!”,否则请输出“Grass Win!”,每个实例的输出占一行。

 

Sample Input
2
3 5
3
3 5 6
0

 

Sample Output
Rabbit Win!
Grass Win!

 

Author
lcy

 

Source
是一个略有变形的nim游戏模型
如果在i位置上有 k个棋子
我们可以看做有k堆数量为i的堆
可以向左移动1~i步
就可以看做每次从数量为i的堆中拿走数量1~i
这样就是nim游戏.
而nim游戏的结论是..异或和为0必败.

同样,我们可以用sg函数来解决。
m个棋子可以认为是m个1个棋子的游戏的和。
而游戏的和的sg值就是所有子游戏的sg值的异或。