P6270 [SHOI2002]取石子游戏 题解

CSDN同步

原题链接

POJ链接

简要题意:

双方轮流拿石子,共两堆石子,每次可以拿去一堆中的任意个或者两堆中的相同多个。先走方是否一定能获胜(失败)?

博弈论经典:威佐夫博弈 模板题。

显然,我们用 (P) 态表示必败态,(A) 态表示必胜态,用 (f_{x,y}) 表示两堆分别为 (x) 个和 (y) 个的状态。显然:

[f_{x,y} in igg( A,P igg) ]

然后,先规定边界:

[f_{0,0} = P , f_{0,x} = f_{x,0} = A ]

[f_{x,y} = f{y,x} ]

我们只需考虑 (x<y) 的情况。

去处边界,(f_{1,2} = P),这是显然的,你无论如何都是输。

然后,(f_{1,k} = A(k >2)),这是因为,你只要把 (k) 个石子降为 (2) 个石子,然后对方是先手,(ecause f_{1,2} = P)( herefore f_{1,k} = A(k > 2)).其中式子中可以认为 (P=0,A=1).

同理,(f_{2,k} = A(k>1)),因为 (f_{2,1} = P),把 (k) 堆石子弄成一堆就行。

从上面可以看出,如果把 (f_{x,y}) 写在平面直角坐标系上,那么 每一列只有一个 (P)(因为其它的都转移成它)。

我们继续寻找 (f_{3,k} = P)(k) 值。

下面,我们用 (x^1) 表示 (x) 状态的取反值。(取反即 (P gets A)(A gets P)

[f_{3,4} = f(1,2)^1 = P^1 = A ]

[f_{3,5}=max(f_{3,4},f_{3,3},f_{2,4},f_{1,3})^1 = A^1 = P ]

(max) 即在所有状态中取最优解(能赢则赢,全输则输)。

因此,(f_{1,2})(f_{3,5})(P) 态。

然后经过类似枚举发现:(其实是用电脑动态规划打表的

(f_{1,2} , f_{3,5},f_{4,7},f_{6,10},f_{8,13} = P)

这时我们大概发现了一点规律。

首先,第 (i)(P) 态一定是 (f_{x,x+i}) 的形式。

你发现这个数列有极了规律。

(i)(P) 态应当时 (f(m_i,m_i+i)),其中 (m_i) 表示前 (i-1)必败态中未出现的最小数

什么意思?比方说,第 (3)(P) 态。

前面出现过 (1,2,3,5)( herefore) 就是 (f_{4,4+3} = f_{4,7})

然后,给出一段伪代码,求出前 (1) ~ (10^5)(P) 态。

freopen("data.txt","w",stdout);
	bool h[1000001]; int last=1; //last表示上次出现的位置,用来优化搜索,保证线性
	memset(h,0,sizeof(h)); //桶清0
	for(int i=1;i<=100000;i++) {
		for(int j=last;j<=INT_MAX;j++)
			if(!h[j]) {
				last=j; h[j]=1; h[j+i]=1;
				printf("%d %d
",j,j+i);
				break;
			}
	}

时间复杂度是 (O(10^5)),然后我们得到一个表:

打表真快乐

(如果你想分析,也可以试着分析一下这种大数据)

(天哪,你不会以为我想把 (10^9) 的表滚出来然后交吧,不好意思)

然后经过 看题解 分析发现:

[m_i = i imes frac{1 + sqrt{5}}{2} ]

然后直接判断即可。

时间复杂度:(O(n)).

期望得分;(100pts).

实际得分:(90pts).(始终不知道怎么错的,但 ( exttt{POJ}) 上交是 ( ext{AC}) 的)

#include<math.h>
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

typedef long long ll; //后来调试无果开了 long long

inline ll read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int main(){
	ll a,b;
	while(scanf("%lld%lld",&a,&b)!=EOF) {
		if(a<b) swap(a,b);
		a=(int)((a-b)*(1+sqrt(5))/2.0);
		if(a==b) puts("0");
		else puts("1");
	}
	return 0;
}

原文地址:https://www.cnblogs.com/bifanwen/p/12622836.html