Posted on 2007-10-31 18:11
ZelluX 阅读(1718)
评论(2) 编辑 收藏 所属分类:
Algorithm
问题：
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
碰到这道题时我的思路：
设集合A, B分别为先手能赢和后手能赢的二元无序对(x,y)的集合
先从最基础的开始考虑，(n,0) (n,n) 属于A，因为这样的情况先手肯定能赢（n为正整数，下同）
如果存在(a,b)，对于一切n，(a-n,b-n)均属于A，则(a,b)属于B
很容易找到一个(2,1)，这是后手肯定能赢的情况
接下来从先手的角度分析，如果他能在移动石子后留给对手(2,1)个石子，那么他就能赢，于是
(2+n,1) (2+n,1+n) (2,1+n) 均属于 A
找出一个不属于A的最小对，(5,3)， 这个元素肯定属于B集合，因为从中任意取出元素后的结果肯定属于A集合
相应的，(5+n, 3) (5, 3+n), (5+n, 3+n) 均属于A
这时发现，B集合相对A集合元素少很多，只要找出B集合中元素的特征，就能解决这个问题。
一旦B中包含(x,y)对，A中就会相应的包含(x, y+n), (x+n, y), (x+n,y+n)
由此想出一种构造B集合的方法，设当前构造出的集合为S，a为不在S中的最小的数，即
a = MIN{ x | x 不属于 (p, q), 对于一切(p, q)属于S }
则把(a, a+gap)加入B中，其中gap是当前S中所有对之差的最小值+1
构造出的序列为
(1,2) -> (3, 5) -> (4, 7) -> (6, 10)
到这里这道题目应该已经能过了，不过还有一种达到O(1)的优化，接下来的就不是我想出来的了 =,=
首先是Betty定理：
如果无理数alpha, beta满足
1. alpha, beta > 0
2. 1/alpha + 1/beta = 1
那么，序列{[alpha*n]}和{[beta*n]}构成自然数集的一个分划，其中[]是取整函数
这道题对应的alpha和beta分别是(1+sqrt(5))/2,(3+sqrt(5))/2，其实是一个黄金分割
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int x, y;
double alpha = (1.0 + sqrt(5.0)) / 2.0;
double beta = (3.0 + sqrt(5.0)) / 2.0;
while (cin >> x >> y) {
if (x > y) {
int temp = x;
x = y;
y = temp;
}
int n = ceil(y / beta);
int x1 = alpha * n;
int y1 = beta * n;
if (x == x1 && y == y1)
cout << 0 << endl;
else
cout << 1 << endl;
}
return 0;
}