博弈论入门总结

 /*

    
 hdu 1846
    
 题目大意： 
    
 	有一堆石子一共有n个，两人轮流进行取石子，每走一步可以取走1…m个石子，最先取光石子的一方为胜；
    
 如果游戏的双方使用的都是最优策略，请输出哪个人能赢。
    
   7. Input
    
 输入数据首先包含一个正整数C(C<=100)，表示有C组测试数据。
    
 每组测试数据占一行，包含两个整数n和m（1<=n,m<=1000），n和m的含义见题目描述。
    
   11. Output
    
 如果先走的人能赢，请输出“first”，否则请输出“second”，每个实例的输出占一行。
    
   14. Sample Input
    
 2
    
 23 2
    
 4 3
    
   19. Sample Output
    
 first
    
 second
    
   23. *******************************
    
 巴什博弈，当n % (m+1) == 0时，必败！ 
    
  
    
 */
    
  
    
 #include <iostream>
    
 using namespace std;
    
  
    
 int C, n, m;
    
  
    
 int main() {
    
 	cin >> C;
    
 	while(C--) {
    
 		cin >> n >> m;
    
 		if(n % (m+1) != 0)
    
 			cout << "first" << endl;
    
 		else
    
 			cout << "second" << endl;
    
 	}
    
 	
    
 	return 0;
    
 }
    
    
    
    
    AI写代码

 /*

    
   3. 链接：https://www.nowcoder.com/acm/contest/77/G
    
 来源：牛客网
    
   6. 题目描述
    
     幼儿园开学了，为了让小盆友们能尽可能的多的享受假期。校长大人决定让小盆友分批到校，至于每批学生来多少人由一个小傻子和一个小仙女
    
 负责，两个人轮番负责，校长会在最后的时候去查看工作进度，小傻子不想被别人嘲笑自己傻，小仙女要证明自己比小傻子聪明。所以她们回去争抢安排最后一名小盆友。每次安排的小盆友至少为1，至多为上一次安排的2倍。小仙女抢到了先手的机会。第一次安排小盆友不能直接安排所有的小盆友一起回校。 
    
   10. 输入描述:
    
 单组测试数据输入一个整数n，n代表小盆的个数（n>=2&&n<=1e9)
    
 输出描述:
    
 输出获胜人的名字——“Xian”或者“Sha”
    
   15. 输入
    
 3
    
 输出
    
 Sha
    
 说明
    
 （Fisrt）1 -> (Second)  2         ||     2 - > 1  
    
 无论小仙女先送一个还是两个都会被小傻子获胜
    
   23.   24. 输入
    
 4
    
 输出
    
 Xian
    
 说明
    
 1 -> 2 -> 1    ||    1 -> 1 -> 2        
    
 小仙女先送一个，小傻子无论送一个或者两个都会被小仙女取胜。
    
   32. */
    
  
    
 #include <iostream>
    
 using namespace std;
    
  
    
 int main() {
    
 	int n, tag = 0;
    
 	long long a = 1, b = 1, t;
    
 	cin >> n;
    
 	while(a <= n) {
    
 		if(a == n)
    
 			tag = 1;
    
 		t = b;
    
 		b += a;
    
 		a = t;
    
 	}
    
 	if(tag == 1)
    
 		cout << "Sha";
    
 	else
    
 		cout << "Xian";
    
 		
    
 	return 0;
    
 }
    
    
    
    
    AI写代码

 /*

    
 hdu2516 
    
 Description
    
 	有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；
    
 二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，
    
 问最后你是胜者还是败者。
    
   8. Input
    
 	输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，
    
 表示两堆石子的数目，a和b都不大于1,000,000,000。
    
 Output
    
 	输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。
    
   14. Sample Input
    
 2 1
    
 8 4
    
 4 7
    
   19. Sample Output
    
 0
    
 1
    
 0
    
   24. */
    
  
    
 #include <iostream>
    
 #include <cmath>
    
 using namespace std;
    
  
    
 int main() {
    
 	int a, b;
    
 	double p = (sqrt(5.0)+1)/2;
    
 	while(cin >> a >> b) {
    
 		int dif = abs(a-b);
    
 		a = a<b ? a:b;
    
 		if(a == (int)(p*dif))
    
 			cout << "0" << endl;
    
 		else
    
 			cout << "1" << endl;
    
 	}
    
 	
    
 	return 0;
    
 }
    
    
    
    
    AI写代码

 /*

    
 hdu1850 
    
 题目大意：
    
 	桌子上有M堆扑克牌；每堆牌的数量分别为Ni(i=1…M)；两人轮流进行；每走一步可以任意选择一堆并取走其中的任意张牌；
    
 桌子上的扑克全部取光，则游戏结束；最后一次取牌的人为胜者。
    
 Input 
    
 	输入数据包含多个测试用例，每个测试用例占2行，首先一行包含一个整数M(1<M<=100)，
    
 表示扑克牌的堆数，紧接着一行包含M个整数Ni(1<=Ni<=1000000，i=1…M)，分别表示M堆
    
 扑克的数量。M为0则表示输入数据的结束。
    
 Output 
    
 	如果先手的人能赢，请输出他第一步可行的方案数，否则请输出0，每个实例的输出占一行。
    
   13. Sample Input
    
 3
    
 5 7 9
    
 0
    
   18. Sample Output
    
 1
    
   21. */
    
  
    
 #include <iostream>
    
 #include <cstdio>
    
  
    
 const int MAX = 100009; 
    
 int n, a[MAX];
    
  
    
 int main() {
    
     while(scanf("%d", &n), n) {
    
     int sum = 0, ans = 0;
    
     for(int i = 0; i < n; i++) {
    
         scanf("%d", &a[i]);
    
         sum ^= a[i];
    
     }
    
     
    
     if(sum == 0) {
    
 			cout << 0 << endl;
    
 			continue;
    
 		}
    
     for(int i = 0; i < n; i++)
    
         if((sum^a[i]) <= a[i]) ans++;
    
     cout << ans << endl;
    
     }
    
     
    
     return 0;
    
 }
    
    
    
    
    AI写代码