ACM 博弈(难)题练习 (第一弹)

第二弹

套路&&经验总结:

1. N堆***的游戏,一般可以打表找SG函数的规律。比如CodeForces 603C

2.看起来是单轮的游戏,实际上可能拆分成一些独立的子游戏。比如CodeForces 317D

3.考虑最终如果某方胜利,最后的局面会是怎样。 比如CodeForces 594A

4.大力分类讨论,不要怕麻烦,在纸上写清楚。 比如 CodeForces 455B


CodeForces 794C

题目大意:

A和B各有一个大小为N的可重复字符集合,然后两个人轮流,每次取出从自己的集合里取出一个字符,填到一个长度为N的字符数组里,A希望最后形成的字符串字典序最小,B希望字典序最大。问最后结果是怎样。

题解:
显然A会用到自己最小的ceil(N/2)个字符,B会用到自己最大的floor(N/2)个字符。

分4种情况讨论:

1 当前轮到A。

1.1  当前A的最小字符比B的最大字符小。显然A应该把自己的最小字符放到最前面,否则B下回合至少可以把自己的最大字符放到最前面,使得结果字典序变大。

1.2  当前A的最小字符不比B的最大字符小。  A应该想办法逼B把小的放到前面去,所以A应该把自己最大字符放到最后。

2 当前轮到B。

2.1  当前A的最小字符比B的最大字符小。显然B应该把自己的最大字符放到最前面。

2.2  当前A的最小字符不比B的最大字符小。  B应该想办法逼A把大的放到前面去,所以B应该把自己最小字符放到最后。


CodeForces 786A

题目大意:

两个人在n个点的环上玩游戏,环上有一个棋子。每个人有一个数集,每回合每个人可以从自己的集合里选出一个数x, 让棋子顺时针走x步。把棋子走到1号点的人赢。

一开始不知道棋子在哪,因此要你对每个位置i,输出如果一开始棋子在i号点,结果是先手赢还是后手赢还是平局。 所有数据<=7000.

题解:

倒推回去,一共2n个状态,把已经确定的状态丢到队列里, 如果一个点存在一个后继状态是必败的,那么他是必胜的,否则必败。有点类似拓扑排序,记录每个点的后继状态有多少个已经确定了,根据已经确定的状态倒推回去即可。  没有被计算到的状态就是平局。


CodeForces - 768E

题目大意:

Nim游戏改编,加了一个限制,同一堆石头,不能拿多次相同数量的石头。 比如之前拿过一次2个石头,之后就不能再拿2个石头。 ai<=60

题解:
sg[s][mask]表示s个石头,mask存之前已经拿过哪些。用map存,爆搜出sg。 爆搜的时候有个很强力的优化,比如还剩3个石头,而mask的第2位是1,表示不能再取4了,显然把maks的第2位换成0也没有影响。  即类似(s = 3, mask = 5) 和(s = 3, mask = 1)这样的状态是等价的。  因为ai<=60, 爆搜打表就好了。

其实打完表还可以发现规律。sg[1][0] sg[2][0] sg[3][0]....sg[n][0] 这个数列是1 1 2 2 2 3 3 3 3 4 4 4 4 4 ....


CodeForces 755B

题目大意:
两个人比谁的词汇量大,轮流说单词,说过的不能再说。 给你两个人各自掌握的词汇,问谁输谁赢。

题解:
显然尽可能先把两个人都知道的单词说掉。


CodeForces 731E

题目大意:

N张贴纸排成一排,每张贴纸上写了一个数。两个人轮流玩,每次从最前面拿走至少2张贴纸,得分是拿的贴纸上的数之和。然后在最前面放回一张新的贴纸,贴纸上的数是该回合拿走的贴纸上的数之和。只剩下一张贴纸时游戏结束。 两个人都想自己的得分尽可能大。 N <= 1e5

题解:
显然任意局面都可以表示成  sum(1...i)  a[i + 1] a[i + 2] .... a[n] 这样的形式。 dp[i]表示这样的局面先手比后手最多多得多少分,很容易列出转移方程:

dp[i] = max{ sum(1...j - 1) - dp[j]} 只和j有关,用树状数组维护一个后缀最大值即可。


CodeForces 717D

题目大意:
N堆石头,每堆石头的个数不确定, 可能是0-x,然后给出每个个数的概率。 玩Nim游戏,问先手赢的概率。 N <= 1e9, x <= 100

题解:
DP + 矩阵乘法。


CodeForces 705B

题目大意:

N堆石头,每次选择一堆分成非空的两堆,两人轮流操作,不能操作的输。

题解:

假设一堆石头有x个,不管怎么分,都是要分x - 1次。   把所有的x - 1求和根据奇偶就可以知道谁胜谁负。


CodeForces 630R

题目大意:
N * N的方格,两个人轮流涂格子,要求任意两个涂颜色的格子不能相邻(有公共边)。

题解:
先将格子黑白染色。 显然两个人要么只在黑色格子上玩,要么只在白色格子上玩。 而先手可以决定在什么颜色的格子上玩。 分析一下就知道N为奇数先手胜,偶数后手胜。


CodeForces 603C

题目大意:

给定N和K。 N堆石头,每次可以从一堆石头中拿走一个,或者 如果这堆石头有偶数个(2 * x个),可以将其变成K堆有x个石头的堆。

题解:

根据k的奇偶来讨论。

如果是偶数,那么SG异或起来就消掉了。 如果是奇数,那么一对一对的消掉只剩下一个。

因此如果K为奇数.

SG(2x + 1) = mex{ SG(2x) }

SG(2x) = mex{SG(x), SG(2x - 1)}

如果K为偶数

SG(2x + 1) = mex{ SG(2x) }

SG(2x) = mex{0, SG(2x - 1)}

打个表就可以发现神奇的规律。 并且这个规律很容易用数学归纳法证明。

大致是K为奇数的时候。

前面5特殊判断, x > 5的时候 x为奇数sg=0, x为偶数 sg[x] sg[2x] sg[4x] sg[8x] 是 1 2 1 2交替。

K为偶数的时候:
0 1 2 0 1 0 1 0 1 0 1.... 从第3项开始01交替。


CodeForces 533C

题目大意:

两个人各有一个棋子在棋盘上玩, 先手每次可以向左或者向下走一步,后手可以向左或向下或左下走一步。谁先走到(0, 0)谁就赢,不能走到坐标为负的点,也不能走到别人的棋子上。

题解:

设先手棋子为A,后手为B。

若B在A的右上方(包括正上方和正右边),容易知道A必胜,因为A总可以使自己在B的左下方。

同理若B在A的左下方,B必胜。

剩下两种对称的情况。

若B在A的右下方,A应该尽可能先往下走,B尽可能往左下走,模拟这个过程直到变成上面两种情况。

若B在A的左上方同理。


CodeForces 549C

题目大意:

两个人玩游戏,有N个数,每次去掉一个数,剩下K个数,先手想让剩下的K个数之和是奇数,后手想要偶数。

题解:

假设还剩下K + 1个数,这里面有奇数也有偶数,那么最后选的人肯定赢。

也就是说,如果最后一次选择轮到A,B肯定要在之前要么把奇数全拿完,要么把偶数选拿完,否则肯定输。

然后就分类讨论判断就好了。


CodeForces 346A

题目大意:

给出一个正整数集合,两个人轮流玩,每次可以选两个数x, y, 要求|x - y|不在集合里,然后把|x - y|加入集合。 不能操作者输。

题解:

首先可以通过一通操作搞出所有数的gcd = d(辗转相减),游戏结束时的集合是确定的,一定是d, 2d, 3d....k*v   k*v是一开始集合元素的最大值。所以就知道一共玩了多少轮,根据奇偶判断必胜。


CodeForces 455B

题目大意:

两个人在Trie树上博弈,从根开始,每次往下移动一个位置,不能移动的输。  重复该游戏k轮,上一轮输的人下一轮变为先手。  第k轮赢的人 真正赢得游戏。

题解:

一开始以为就是一个傻逼SG,然后WA到死。

因为要重复k次游戏,所以当前这一轮,有时候明明可以获胜,但是故意落败也许才是正确的选择,但有时候你想输掉这轮游戏对方偏偏会让你赢。

考虑做2次SG,分别一轮游戏是先手能否必胜,能否必败。

如果先手可以必胜,先手也可以必败,显然他能掌控局面取得胜利,只要前面k-1轮故意输掉,最后一轮赢回来。

如果后手可以必胜,那么后手只要一直赢就好了,显然后手胜利。

剩下最后一种情况:先手可以必胜,后手可以必败。

倒过来考虑,假设我想要在第k轮赢,那么第k轮我必须是先手,也就是说第k-1轮我必须输。 而后手可以必败,所以第k-1轮我必须是后手,第k-2轮我必须赢。

所以我期望的应该是从第k轮倒过来 赢输赢输交替。 因此k为奇数先手胜,否则后手胜。


CodeForces 594A

题目大意:

数轴上有N个点,N为偶数。 两个人轮流删点,直到剩下最后2个点。 先手想要最后剩下的两个点距离尽可能近,后手想要尽可能远。 求最后的距离。

题解:

假设最后剩下两个点分别是第L个点和第R个点。 两个人都有N / 2 - 1次机会。

先手知道这件事。如果R - L > N / 2,不管后手怎么取,先手完全可以把[1, L - 1], [R + 1, N]这些点取完(如果后手帮着取,那更好了),使得最后剩下的石头i,j    [i, j] 包含于[L, R],距离显然更小。 矛盾。 也就是说先手总能使得R - L <= N / 2,   且先手可以实现选定一个[L, L + N / 2],只要不断取区间外的点,一定能使的最后的两个点落在这个区间内。也就是说最后的距离一定小于等于min{Xi + N / 2 - Xi}

而后手每次至少可以选最中间的点删掉,使得最后剩下的两点R - L = N / 2。 这样距离>=min{Xi + N / 2 - Xi}.

所以最后答案就是min{Xi + N / 2 - Xi}。


CodeForces 317D

题意:

两个人取数,一开始有1-n,每次如果取了x,那么x, x2, x3, x4....都不能取了。  n <= 1e9.

题解:

考虑将数分类。那些有幂次关系的分到同一类, 不同类之间的博弈是独立的,可以看做一个子游戏。 每一类最多有29个数, 对于每个子游戏x, x2, x3....xk,只和个数k有关。状压DP一下求出sg值,k最大是29,可以用map来存。

暴力打表后得到的sg值如下:

sg[30] = {0, 1, 2, 1, 4, 3, 2, 1, 5, 6, 2, 1, 8, 7, 5, 9, 8, 7, 3, 4, 7, 4, 2, 1, 10, 9, 3, 6, 11, 12};

所以只要将这n个数分类即可,考虑如果一个类至少有2个数,其中最小的那个一定<=sqrt(n), 枚举即可。 剩下的类都是只有一个数的。

上一篇:数据库调优-02


下一篇:Linux下SVN安装配置和使用中遇到的问题