Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

取石子游戏

Posted on 2007-10-31 18:11 ZelluX 阅读(1563) 评论(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;
}



评论

# re: 取石子游戏  回复  更多评论   

2007-10-31 21:30 by Rex Mao
这题在ACM里坐过,当时只知道公式,没想过原理。

# re: 取石子游戏  回复  更多评论   

2007-11-01 11:40 by ZelluX
@Rex Mao
这题应该是某届NOI的题目,也被放到了POJ上

只有注册用户登录后才能发表评论。


网站导航: