首页 > 题解 > bzoj 1299 [LLH邀请赛]巧克力棒

bzoj 1299 [LLH邀请赛]巧克力棒

Description

TBL和X用巧克力棒玩游戏。每次一人可以从盒子里取出若干条巧克力棒,或是将一根取出的巧克力棒吃掉正整数长度。TBL先手两人轮流,无法操作的人输。 他们以最佳策略一共进行了10轮(每次一盒)。你能预测胜负吗?

Input

输入数据共20行。 第2i-1行一个正整数Ni,表示第i轮巧克力棒的数目。 第2i行Ni个正整数Li,j,表示第i轮巧克力棒的长度。

Output

输出数据共10行。 每行输出“YES”或“NO”,表示TBL是否会赢。如果胜则输出”NO”,否则输出”YES”

Sample Input

3

11 10 15

5

13 6 7 15 3

2

15 12

3

9 7 4

2

15 12

4

15 12 11 15

3

2 14 15

3

3 16 6

4

1 4 10 3

5

8 7 7 5 12

Sample Output

YES

NO

YES

YES

YES

NO

YES

YES

YES

NO

HINT

20%的分数,N<=5,L<=100。

40%的分数,N<=7。 50%的分数,L<=5,000。

100%的分数,N<=14,L<=1,000,000,000。

题解

这道题的题意就是有n堆石子,之后你每次操作有两种做法

第一种是在已经建立的nim游戏上进行nim游戏。
第二种是在未被选的堆中选取若干堆加入这个nim游戏中。

然而这道题的必败态可以这么建:

如果是先手的话,我可以建立出来一个异或和为0的nim游戏,此时后者有两种做法:

第一种是在该nim游戏上游戏,则先手又可以将这个游戏的异或和变为0
第二种是选取新的石子堆加入原来的nim游戏。

如果是先手的话不会给后手机会来添加一组异或和为0的石子堆。所以先手建立的一定是选取最多的元素的异或和为0的nim游戏,此时,在剩下的堆里,一定不能有一组石子堆的异或和为0,这很显然。

所以如果后者选取第二种做法,那么会使得原有的Nim游戏的异或和不为0,所以先手又可以将这个游戏的异或和变为0。

即如果先手开始选取最多石子堆来建立一个异或和为0的nim游戏,则后者必败。

又可以转化一下,如果先手可以选出一个任意数量的石子堆建立的异或和为0的nim游戏,则后者必败。

然后枚举一下所有的状态就可以了,$2^14


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×