Alice and Bob（不断补充）

我之前做过一些博弈的题目，以为博弈都是DP，结果被坑了很多次，其实博弈有很多种，在此，把我见过的类型都搬上来。

1，HDU3951(找规律)

题意：把n枚硬币围成一个圆，让Alice和Bob两个人分别每人每次拿k(1<=k<=m)枚连续的硬币，谁能拿到最后谁赢；

思路：找规律，A拿了之后，B只要把剩下的分成偶数块，Ｂ就能赢，找到的规律就是除了m=1 && n&1是A赢，其余全是B赢，即B能够分成偶数块；

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <sstream>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <cstdlib>
 7 #include <string>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <queue>
12 #include <stack>
13 #include <algorithm>
14 using namespace std;
15 #define ll long long
16 #define _cle(m, a) memset(m, a, sizeof(m))
17 #define repu(i, a, b) for(int i = a; i < b; i++)
18 #define MAXN 30005
19 
20 int main()
21 {
22    int T;
23     scanf("%d", &T);
24     for(int kase = 1; kase <= T; kase++)
25     {
26         int a, b; scanf("%d%d", &a, &b);
27 
28         if((a%2 && b==1) || a<=b) printf("Case %d: first
", kase);
29         else
30         {
31             printf("Case %d: second
", kase);
32         }
33 
34     }
35    return 0;
36 }

View Code

2,JOJ 1063（找规律）

题意：1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完，以后每次取的石子数不能超过上次取子数的2倍。取完者胜.

思路：找规律，如果牌数在数组中出现过就是Bob赢，a[i] = a[i-1] + a[1-2],其中a[0] = 2,a[1] = 3;

 1 const int N = 51;
 2 double arr[N] = {2, 3};
 3 int main(void)
 4 {
 5     int i;
 6     double n;
 7     for( i=2; i < N; ++i ) arr[i] = arr[i-1] + arr[i-2];
 8     while( scanf("%lf", &n), n != 0 )
 9     {
10         for( i=0; i < N; ++i )
11             if( arr[i] == n )
12             {
13                 printf("Second win
");
14                 break;
15             }
16         if( i == N ) printf("First win
");
17     }
18     return 0;
19 }

代码

3，HDU4597（记忆化搜索）

题意：给出2叠卡片，每叠卡片有n张牌，告诉你卡片上的数字，每个人每次只能选择2叠卡片中最上边或者最下边的卡片，然后累加，最后谁得到的数字最大谁就能赢；

思路：记忆化搜索

dp[l1][r1][l2][r2]表示在pile1的数还剩下从l1到r1（开区间），pile2的数还剩下bl到r2的情况下,先手能取得的最大值。状态转移就最多只有四个方向，如果取pile1的左边那个数，那能获得的最大价值就是，

即dp[l1-1][r1][l2][r2] = a[l1+1] + (suma[r1-1]-suma[l1+1]+sumb[r2-1]-sumb[l2]-dp[l1+1][r1][l2][r2])（预处理出pile1的和pile2的前缀和，用剩下的价值减去后手能获得的最大价值）,然后记忆化搜索.

View Code