前言
今天还做了几道找规律的题目，可能是因为我菜所以才没发现正确解法吧，不过通过递推关系得到规律也是很重要的解题方法。
HDU-1847
题目描述
大学英语四级考试就要来临了，你是不是在紧张的复习？也许紧张得连短学期的ACM都没工夫练习了，反正我知道的Kiki和Cici都是如此。当然，作为在考场浸润了十几载的当代大学生，Kiki和Cici更懂得考前的放松，所谓“张弛有道”就是这个意思。这不，Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”？“双扣”？“红五”？还是“斗地主”？
当然都不是！那多俗啊~
作为计算机学院的学生，Kiki和Cici打牌的时候可没忘记专业，她们打牌的规则是这样的 ：
1、 总共n张牌;
2、 双方轮流抓牌；
3、 每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）
4、 抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；
假设Kiki和Cici都是足够聪明（其实不用假设，哪有不聪明的学生~），并且每次都是Kiki先抓牌，请问谁能赢呢？
当然，打牌无论谁赢都问题不大，重要的是马上到来的CET-4能有好的状态.
Good luck in CET-4 everybody!
Input
输入数据包含多个测试用例，每个测试用例占一行，包含一个整数n（1<=n<=1000）。
Output
如果Kiki能赢的话，请输出“Kiki”，否则请输出“Cici”，每个实例的输出占一行。
Sample Input
1
3
Sample Output
Kiki
Cici
题目分析
首先我们知道，如果在n=k的时候Cici必胜，那么我们又提议可以推出，k+1和k+2的情况下Kiki必胜，又因为最小的k的值为3，所以我们假设形如3k+1和3k+2的情况Kiki必胜，形如3k的情况Cici必胜，又因为2的幂次除了1之外全是偶数，所以我们可以证明所有形如3k的数加上这个2的幂次不会再是3的倍数，于是我们就可以递推下去得到这个结论是正确的。
有了这个结论，代码会变得很简单。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <stdio.h> int main(int argc, char const *argv[]) { int n; while(scanf("%d", &n) != EOF){ if(n%3==0) printf("Cici\n"); else printf("Kiki\n"); } return 0; } |
HDU-3951
题目描述：
After hh has learned how to play Nim game, he begins to try another coin game which seems much easier.
The game goes like this:
Two players start the game with a circle of n coins.
They take coins from the circle in turn and every time they could take 1~K continuous coins.
(imagining that ten coins numbered from 1 to 10 and K equal to 3, since 1 and 10 are continuous, you could take away the continuous 10 , 1 , 2 , but if 2 was taken away, you couldn’t take 1, 3, 4, because 1 and 3 aren’t continuous)
The player who takes the last coin wins the game.
Suppose that those two players always take the best moves and never make mistakes.
Your job is to find out who will definitely win the game.
Input
The first line is a number T(1<=T<=100), represents the number of case. The next T blocks follow each indicates a case.
Each case contains two integers N(3<=N<=10 9,1<=K<=10).
Output
For each case, output the number of case and the winner “first” or “second”.(as shown in the sample output)
Sample Input
2
3 1
3 2
Sample Output
Case 1: first
Case 2: second
题目大意
有n个硬币，标号1~n，排成一个圆环，先手与后手可以分别从这些硬币里拿走 连续 的1~k枚，比如当k=3时，可以拿走10,1,2这三枚，也可以拿走1,2这两枚，以此类推，拿走最后一枚硬币的人获胜。
题目分析
这个题目严格意义上叫做对称博弈，不过因为比较小众我把它放在找规律的里面。
其实规律并不难找，只是需要一些脑洞
分为三种情况：
– k=1时，相当于两个人轮流拿硬币，一次一个，这样就显而易见有
n为技术时先手获胜
n为偶数时后手获胜
- k>n时，先手可以一下拿走所有硬币，先手获胜。
- 当不是以上两种情况时，我们可以得到一个很有意思的结论，先手的第一次操作无论怎样都一定会把这个环拆开，变成一个链，又因为k != 1，所以后手可以把剩下的链分成两个长度完全一样的子链，从此之后，因为先手的操作只能发生在其中的一条链上，因此后手可以在另一条链上完全模仿先手的操作，从而最后达到拿走最后一枚硬币的结果。也就是后手必胜。
明确了这些规律，代码也很容易实现。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <stdio.h> int main(int argc, char const *argv[]) { int t,count = 0; scanf("%d", &t); while(t--){ count++; int n, k; scanf("%d %d", &n, &k); if(k == 1){ if(n%2==1) printf("Case %d: first\n",count); else printf("Case %d: second\n", count); } else if(k>=n) printf("Case %d: first\n", count); else printf("Case %d: second\n", count); } return 0; } |
HDU-1517 A Multiplication Game
题目描述
Stan and Ollie play the game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Stan always starts with p = 1, does his multiplication, then Ollie multiplies the number, then Stan and so on. Before a game starts, they draw an integer 1 < n < 4294967295 and the winner is who first reaches p >= n.
Input
Each line of input contains one integer number n.
OUtput
For each line of input output one line either
Stan wins.
or
Ollie wins.
assuming that both of them play perfectly.
Sample Input
162
17
34012226
Sample OUtput
Stan wins.
Ollie wins.
Stan wins.
题目大意
一个乘法游戏，从1开始，先后手依次给这个数乘上2~9，谁先使得这个数超过n谁获得胜利。
题目分析
- 若输入的n的范围是2~9，则先手胜
- 若输入的n的范围是10~18，则无论先手乘多少，后手都可以获得胜利。
- 当超过18时，先手第一次取2，则后手至少将其扩大为4，此时先手乘上9便可扩大到36，同时注意到，先手可以通过改变自己第一次的取值来控制后手第一次操作的扩大的范围，所以当先手取9，后手取2，先手再取9是=时得到最大值162，也就是说在19~162区间内先手必胜。
- 总结成规律，每次先手必胜的区间之后乘2是后手获胜的区间，每次后手获胜的区间乘9得到先手获胜的区间，也就是说，18是一个循环
依据这个，我们可以利用给出的数不停的去除以18，看最终得到的小于18的数字落在1~9区间还是10~18区间，从而判断获胜情况。1~9是先手获胜，10~18是后手获胜
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <stdio.h> int main(int argc, char const *argv[]) { double n; while(scanf("%lf", &n) != EOF){ while(n>18) n/=18; if(n<=9){ printf("Stan wins.\n"); } else printf("Ollie wins.\n"); } return 0; } |
后记
这几道找规律的题都是和博弈相关的，在做题的时候自己去分析几组数据，看看得到的结果的规律性，对我们解题很有帮助。