P2599 [ZJOI2009]取石子游戏

斯德哥尔摩 · 2018-07-28 22:52:35 · 个人记录

P2599 [ZJOI2009]取石子游戏

博弈论的Nim游戏中比较难的题。

首先，讲个性质：

取石子时，当先手使得左右两边的石子相等时，可以保证先手必胜。

因为当先手取到左右石子相等的局面时，则后手无论在哪一堆取石子，接下来先手都可以有相同的方法取另一堆石子。

这样又回到了原来的状态（左右石子相等），则无论如何先手都有办法应对后手的取法。

设在区间[i,j]左边放Left[i][j]（可以为0）个石子后（区间内石子保持原状），产生的局面为先手必败局面，Right[i][j]就是在右边放，定义类似。

设val[i]为第i堆石子个数。

最后我们只用看Left[2][n]是否等于val[1]就可以了。（如果等于就说明这个情况先手必败，否则先手必胜）

这一题可以注意到对于一段区间[L,R], 若L+1到R的石子数固定, 那么使得在这段区间上先手必败的val[L]有且仅有一个。

接下来证明Left[i][j]是唯一的：

1. 若存在两或以上个Left[i][j]，则从某一个必定可一步转移到另一个，矛盾，故最多只有一个。

2. 若没有Left[i][j]，那么必胜态只可能通过拿右边的石子转移到某个必败态。

   由于此时左边石子可以是任意个，右边石子数固定，于是必有右边的某一个石子数对应了多种必败态。

   这些必败态只有左边的石子数不同，与1矛盾，舍去。

最后我们考虑Left[i][j]的求法，分类讨论：

设l=Left[i][j-1],r=Right[i][j-1],w=val[j]。通过下面的分析我们可以发现#Left[i][j]#只和l,r,w三个数有关.

1. 边界条件：Left[i][i]=Right[i][i]=val[i].

   两堆一样的，后手照着先手拿的数量在另一堆拿即可。

2. 首先，最容易想到的是r==w的情况，这时[i,j]这段区间已经先手必败，那么Left[i][j]==0。

3. 若w<l,w<r，则Left[i][j]=w。

   因为此时当两堆石子相同时，后手照着先手取，这样先手一定会先拿完某一堆，后手占据主动。

   这之后又会出现某一种我们分类讨论中的情况，相当于一种递归，直到后手获胜。

4. 若w<l,w>r，则Left[i][j]=w-1。

   此时如果先手在左边拿使其个数变为y，若y<r，则后手在右边也拿到y即可变为情况3；

   若y>=r，则后手在右边拿到y + 1，于是回到了相同的情况。

   若先手在右边拿到y，若y<r，同样可到情况3；

   若y==r, 直接把左边的堆拿完，先手便面临败局；

   若y>r，则在左边拿到y-1，回到相同情况。

5. 若w<r,w>=l，则Left[i][j]=w+1，与情况4恰好相反。

6. 若w>l,w>r，则left[i][j]=w。

   若先手将某一堆拿到了y，且y>r, 跟着先手拿即可回到相同情况；

   若y<l，回到情况3；

   若在在左边拿到l或在右边拿到r，后手拿掉另一堆即可；

   否则根据情况在另一堆拿到y-1或是y+1，分别对应情况4和5。