------------------------------------------------

把第一题放出来
虽然没什么用

第一题 妈妈的糖果（candy）

小雪是一个新高一的学生，她有一个龙凤胎哥哥。他哥哥每次都找她的茬，小雪最讨厌她哥哥了。有一天小雪的妈妈给了2堆糖，可恶的哥哥又来抢小雪的糖吃了。小雪誓死保卫自己的糖果，但是她哥哥坚决要抢一些糖过来。正在他们争执不休的时候，哥哥提出了一个建议：“我们用这2堆糖来玩一个游戏，小雪先暂时拿走其中的一堆糖，然后把剩下的那堆糖分成2份让哥哥操作。哥哥再暂时拿走其中一堆糖，继续把剩下的那堆糖分成2份让小雪操作，直到其中一个人拿走一堆糖后另一堆只剩下一个糖，这时候操作的人胜利，可以拿走全部的糖。”小雪怕哥哥使用暴力不得不接受这个建议，但是他哥哥是非常聪明的肯定有什么奇怪的想法。小雪不知道自己能否得到这2堆糖，她绑着马尾辫找到了你，求你帮助她打败哥哥。

输入格式：每个测试点1行，有2个数a，b，以空格隔开，表示初始的2堆糖的数目（1<=a,b<=2^64） (不要问我为什么有那么多糖)

输出格式：如果小雪胜利，输出“xiaoxue’s victory”

否则的话输出“gegezhentaoyan!”

（不包括双引号）

样例输入1：

1 5

样例输出1：

xiaoxue’s victory

样例输入2：

3 2

样例输出2：

gegezhentaoyan!

后话：哥哥还是很厚道的。

谨以此题膜拜Matrix67牛

————————————我是邪恶的分割线————————————

以下为自己想的题解

vijos p1196原题，典型的博弈题。（orz Matrix67神牛）

主要就是要手动推出必胜态和必败态

演示如下：

因为题意是选其中一堆糖给对方操作，所以我们仅仅考虑把一堆糖分成2堆的策略

当糖果数=1，操作的人赢，为必胜态

当糖果数=2，只能分成1+1，那对面的人就得到必胜态，所以是必败态

当糖果数=3，只能分成1+2，对面的人肯定拿走1让你操作2个的，所以你得到必败态，所以这个状态是必败态

当糖果数=4，可以分成2+2，1+3，选2+2对面的人肯定拿到必败态，所以是必胜态

当糖果数=5，可以分成2+3，1+4，选2+3对面的人依然拿到必败态，所以是必胜态。

当糖果数=6，可以分成3+3，同上，是必胜态

当糖果数=7，可以分成3+4，2+5，1+6，每种分发都会让对方留一个必败态给你，所以是必败态

……………………

我们用下表表示上面的结果用T表示必胜态，用F表示必败态

糖果数 1 2 3 4 5 6 7 8 9 10 11 12 13

状态 T F F T T T F F T T T F F

我们可以找到一个规律，当糖果数的个位数为2 3 7 8的时候是必败态

之后这题就十分简单了

只要判断读入的2个数的个位数是不是都属于{2,3,7,8}

如果是的话小雪输，如果不是的话小雪赢

换一个推法

上面考虑必胜必败态的时候我们发现如果拆分情况中拆分出来的2个数的状态都是必败态的话，那这个状态就是必胜态。所以我们可以用已知的必败态去推测后面的状态。

2和3是必败态，这是很显然的

2+2=4 所以4是必胜态

2+3=5所以5是必胜态

3+3=6所以6是必胜态

但是我们用2和3得不到7，所以7是必败态

同理8也是必败态

由2 3 7 8可以推出12 13 17 18

看下列式子

12=8+4=8+2+2

13=8+5=8+3+2

17=8+9=8+7+2

18=8+10=8+7+3

12 13 17 18都是某3个必败态的数字的和

考虑一个数X被分为A和B

如果A和B其中只有一个是必胜态（假设为A）

那么X是必败态，且A一定可以分为2个必败态的和

所以X是3个必败态的和

所以当一个数是3个必败态的和的话这个数是必败态

因为8+2=10 3+7=10

所以12=10+2 13=10+3 17=10+7 18=10+8都是必败态

同理22 23 27 28也是必败态

所以个位数为2 3 7 8 的就是必败态

因为小雪赢的情况比较多，所以说他哥还是很厚道的 >_<

另外输出单引号可以用chr(39)或者4个单引号完成。

A ЮLE

2011年6月14日星期二

2009年10月28日 17:06 阅读(83) 评论(3) 分类：program 《小雪模拟赛》

没有评论:

发表评论