題目

P3480 [POI2009]KAM-Pebbles

演算法分析

設 a [ i ] a[i] a[i]表示第 i i i堆石子的個數， c [ i ] c[i] c[i]表示 a [ i ] ? a [ i ? 1 ] a[i]-a[i-1] a[i]?a[i?1],即相鄰兩堆之間的差值,則我們每堆可以拿的石子數即為 c [ i ] c[i] c[i]，當我們在第 i i i堆拿了 x x x個時， c [ i ] c[i] c[i]變成了 c [ i ] ? x c[i]-x c[i]?x， c [ i + 1 ] c[i+1] c[i+1]變成了 c [ i + 1 ] + x c[i+1]+x c[i+1]+x，相當于我們把第i堆中可拿的石子轉移到了 i + 1 i+1 i+1堆，由此我們可以把此題轉化為一道反著的階梯nim游戲，

下面簡單了解一下階梯nim，
以下圖片摘自 淺談演算法——博弈論 例8：取石子游戲之八（Staircase Nim）

階梯nim是指，有n堆石子，每次我們可以從第i堆的石子中拿走一部分放到第i-1堆中，或者把第1堆中的石子拿走一部分，無法操作的人算輸，先說結論：階梯nim的游戲結果與只看奇數堆的石子數的普通nim結果相同，

假設我先手，那么我可以按照必勝策略把奇數堆中的石子轉移到偶數堆，當對方拿的時候我們分情況討論：

1.對方拿奇數堆中的石子到偶數堆，相當于進行對于奇數堆的普通nim，我們繼續按照必勝策略拿奇數堆中的石子；

2.對方把偶數堆的石子拿到奇數堆，則我們可以把這部分石子繼續向下拿，對于奇數堆相當于局勢沒有變動，

具體代碼如下：

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rg register
typedef long long ll;
using namespace std;
inline int sread()
{
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0') {if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	return f*x; 
}
int u;
int n,r;
int a[100000];
int c[100000];
int main()
{
	u=sread();
	for(int e=1;e<=u;++e)
	{
		n=0;	r=0;
		memset(a,0,sizeof(a));
		memset(c,0,sizeof(c));
		
		n=sread();
		for(rg int i=1;i<=n;++i) a[i]=sread();
		for(rg int i=1;i<=n;++i) c[i]=a[i]-a[i-1];

		for(rg int i=n;i>=1;i-=2) r=r^c[i];//轉化為簡單的Nim博弈 
		if(r) printf("TAK\n");
		else printf("NIE\n");
	}
	return 0;
}

反思與總結

1.學習（見識）了一種特殊的博弈型別——階梯博弈，
2.復習了簡單的Nim博弈型別，
3.水掉了一道紫題嘿嘿