Game Theory

HDU 5795 || 3032

把x个石子的堆分成非空两(i, j)或三堆(i, j, k)的操作->(sg[i] ^ sg[j])或(sg[i] ^ sg[j] ^ sg[k])是x的后继

 1 #define pron "hdu5795"
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 100;
 9 
10 int sg[maxn + 10];
11 bool vis[maxn + 10];
12 
13 int mex(){
14     for (int i = 1; i <= maxn; i ++)
15         if (not vis[i])
16             return i;
17 }
18 
19 int get_sg(int x){
20     if (sg[x] != -1)
21         return sg[x];
22 
23     memset(vis, false, sizeof vis);
24     
25     for (int i = 1; i < x; i ++){
26         int temp = get_sg(i);
27         vis[temp] = true;
28 
29         for (int j = 1; j < x - i; j ++)
30             vis[temp ^ get_sg(j) ^ get_sg(x - i - j)] = true;
31     }
32 
33     return sg[x] = mex();
34 }
35 
36 int get_sg(int x){
37     if (x % 8 == 0)
38         return x - 1;
39     if (x % 8 == 7)
40         return x + 1;
41     return x;
42 }
43 
44 int main(){
45 #ifndef online_judge
46     freopen(pron ".in", "r", stdin);
47 #endif
48     int tcase, n, flag, temp;
49     
50     scanf("%d", &tcase);
51     while (tcase --){
52         flag = 0;
53 
54         scanf("%d", &n);
55         for (int i = 0; i < n; i ++){
56             scanf("%d", &temp);
57             flag ^= get_sg(temp);
58         }
59             
60         if (flag)
61             puts("first player wins.");
62         else
63             puts("second player wins.");
64     }
65 }

5795

 1 #define PRON "hdu3032"
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int MAXN = 100;
 9 
10 bool vis[MAXN + 10];
11 int sg[MAXN + 10];
12 
13 int mex(){
14     for (int i = 1; i <= MAXN; i ++)
15         if (not vis[i])
16             return i;
17 }
18 
19 int get_sg(int x){
20     if (sg[x] != -1)
21         return sg[x];
22 
23     memset(vis, false, sizeof vis);
24 
25     int temp;
26     for (int i = 1; i < x; i ++){
27         temp = get_sg(i);
28         vis[temp] = vis[temp ^ get_sg(x - i)] = true;
29     }
30     
31     return sg[x] = mex();
32 }
33 
34 int get_SG(int x){
35     if (x % 4 == 0)
36         return x - 1;
37     if (x % 4 == 3)
38         return x + 1;
39     return x;
40 }
41 
42 int main(){
43 #ifndef ONLINE_JUDGE
44     freopen(PRON ".in", "r", stdin);
45 #endif
46     memset(sg, -1, sizeof sg);
47 
48     int Tcase, n, temp, flag;
49 
50     scanf("%d", &Tcase);
51     while (Tcase --){
52         flag = 0;
53 
54         scanf("%d", &n);
55         while (n --){
56             scanf("%d", &temp);
57             flag ^= get_SG(temp);
58         }
59 
60         if (flag)
61             puts("Alice");
62         else 
63             puts("Bob");
64     }
65 }

3032

HDU 1536 || 1944

直接get_sg，不需要打表找规律

 1 #define PRON "hdu1536"
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int MAXK = 100 + 10;
 9 const int MAXN = 10000;
10 
11 bool vis[MAXN + 10];
12 int k, Tcase, n, h, flag, s[MAXK], sg[MAXN + 10];
13 
14 int mex(){
15     for (int i = 0; i <= MAXN; i ++)
16         if (not vis[i])
17             return i;
18 }
19 
20 void get_sg(){
21     memset(sg, 0, sizeof sg);
22 
23     for (int i = 0, j; i <= MAXN; i ++){
24         memset(vis, false, sizeof vis);
25 
26         j = 0;
27         while (i >= s[j] && j < k)
28             vis[sg[i - s[j ++]]] = true;
29 
30         sg[i] = mex();
31     }
32 }
33 
34 int main(){
35 #ifndef ONLINE_JUDGE
36     freopen(PRON ".in", "r", stdin);
37 #endif
38 
39     while (scanf("%d", &k) == 1 && k){
40         for (int i = 0; i < k; i ++)
41             scanf("%d", &s[i]);
42         sort(s, s + k);
43 
44         get_sg();
45 
46         scanf("%d", &Tcase);
47         while (Tcase --){
48             flag = 0;
49             
50             scanf("%d", &n);
51             for (int i = 0; i < n; i ++){
52                 scanf("%d", &h);
53                 flag ^= sg[h];
54             }
55 
56             if (flag)
57                 putchar('W');
58             else
59                 putchar('L');
60         }
61 
62         putchar(10);
63     }
64 }

1536

Codeforces 768E

取石子，但是对于每一堆，不能取相同的个数。比如这一堆被拿走了x个，下一次就不能再拿x个了。

官方题解用的dp。但这道题可以...

处理一个数组a[i], 表示取完i个石子最多需要的步骤数，即 1 + 2 + .... + a[i] <= i。由于是后手，所以前者采取什么策略我就可以采取什么策略，因此求一个异或和就好。

#define PRON "768e"
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn = 100;

int n, a[maxn];

int main(){
#ifndef ONLINE_JUDGE
    freopen(PRON ".in", "r", stdin);
#endif

    memset(a, 0, sizeof a);
    for (int i = 0, j = 0; i <= 60; i ++){
        while (j * (j + 1) / 2 <= i)
            ++ j;

        a[i] = -- j;
    }

    scanf("%d", &n);
    int flag = 0, p;
    while (n --){
        scanf("%d", &p);
        flag ^= a[p];
    }

    puts(flag ? "NO" : "YES");
}

768E