博弈问题总结

2015.12.24 20:42 Thu| 18 visits oi_2016| 2016_刷题日常| Text

POJ2484 A FUNNY GAME

当硬币数小于或等于 2 时,先手必胜。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <bits/stdc++.h>
using namespace std;

int n;

int main()
{
    while (cin >> n, n)
        puts(n <= 2 ? "Alice" : "Bob");
    return 0;
}

POJ1740 A New Stone Game

若石子堆数为奇数或堆数为偶数且石子的数目不成对出现,先手必胜。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int n, a[15];

int main()
{
    while (cin >> n, n)
    {
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; i += 2)
            if (a[i] != a[i + 1])
                ans = 1;
        printf("%d\n", ans);
    }
    return 0;
}

POJ2505 A multiplication game

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

long long n;

int main()
{
    while (cin >> n)
    {
        long long p = 1;
        while (p < n)
        {
            p *= 9;
            if (p >= n) { puts("Stan wins."); break; }
            p *= 2;
            if (p >= n) { puts("Ollie wins."); break; }
        }
    }
    return 0;
}

POJ2068 Nim

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int n, s, m[20], dp[10005][20];

int main()
{
    while (cin >> n, n)
    {
        cin >> s;
        for (int i = 0; i < 2 * n; ++i)
            cin >> m[i];
        memset(dp, 0, sizeof dp);
        for (int i = 2; i <= s; ++i)
            for (int j = 0; j < 2 * n; ++j)
                for (int k = max(1, i - m[j]); k <= i - 1; ++k)
                    if (!dp[k][(j + 1) % (2 * n)]) dp[i][j] = 1;
        cout << dp[s][0] << endl;
    }
    return 0;
}

POJ2368 Buttons

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int n;

int main()
{
    cin >> n;
    if (n == 1) puts("0");
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0)
            printf("%d\n", i - 1), exit(0);
    printf("%d\n", n - 1);
    return 0;
}

POJ1067 取石子游戏

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

const double a = (1 + sqrt(5.0)) / 2,
             b = (3 + sqrt(5.0)) / 2;
int n, m;

int main()
{
    while (cin >> n >> m)
    {
        if (n > m) swap(n, m);
        if (int(floor((m - n) * a)) != n ||
            int(floor((m - n) * b)) != m)
            puts("1");
        else puts("0");
    }
    return 0;
}

POJ2348 Euclid's Game

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

int n, m;

bool gcd(int a, int b)
{
    if (b == 0) return false;
    if (a / b >= 2) return true;
    return !gcd(b, a % b);
}

int main()
{
    while (cin >> n >> m, n || m)
    {
        if (n < m) swap(n, m);
        if (gcd(n, m)) puts("Stan wins");
        else puts("Ollie wins");
    }
    return 0;
}

POJ2234 Matches Game

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

int n;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    while (cin >> n)
    {
        int ans = 0;
        while (n--) ans ^= read();
        puts(ans ? "Yes" : "No");
    }
    return 0;
}

POJ2975 Nim

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;

int n, a[1005];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    while (cin >> n, n)
    {
        int t = 0, ans = 0;;
        for (int i = 1; i <= n; ++i)
            t ^= (a[i] = read());
        if (t == 0) { puts("0"); continue; }
        for (int i = 1; i <= n; ++i)
            ans += ((t ^ a[i]) < a[i]);
        cout << ans << endl;
    }
    return 0;
}

POJ3480 John

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;

int test, n;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> test;
    while (test--)
    {
        int t = 0, ans = 0;
        cin >> n;
        for (int x, i = 1; i <= n; ++i)
            t ^= (x = read()), ans = max(ans, x);
        if ((ans == 1 && t == 0) || (ans > 1 && t != 0))
            puts("John");
        else puts("Brother");
    }
    return 0;
}

HDU3032 Nim or not Nim?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

int test, n;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> test;
    while (test--)
    {
        int ans = 0;
        cin >> n;
        for (int x, i = 1; i <= n; ++i)
        {
            x = read();
            if (x != 0 && x % 4 == 0) x -= 1;
            else if (x % 4 == 3) x += 1;
            ans ^= x;
        }
        if (ans) puts("Alice");
        else puts("Bob");
    }
    return 0;
}

POJ3537 Crosses and Crosses

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;

#define N 2005

int n, sg[N], temp[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    for (int i = 1; i <= 2000; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            int t = 0;
            if (j - 3 >= 1) t ^= sg[j - 3];
            if (j + 3 <= i) t ^= sg[i - j - 2];
            temp[t] = i;
        }
        for (int j = 0; j <= i; ++j)
            if (temp[j] != i)
                { sg[i] = j; break; }
    }
    cin >> n;
    if (sg[n]) puts("1");
    else puts("2");
    return 0;
}

HDU4664 Triangulation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
sg[1] = 0;
for (int i = 2; i <= 2000; ++i)
{
    temp[sg[i - 2]] = i;
    for (int j = 1; j < i - 2; ++j)
        temp[sg[j] ^ sg[i - 2 - j]] = i;
    for (int j = 0; j <= i; ++j)
        if (temp[j] != i)
            { sg[i] = j; break; }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int ss[] = {0, 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 0, 5, 2, 2, 3, 3, 0,
            1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 2, 7, 4, 0, 1, 1, 2, 0, 3, 1, 1, 0,
            3, 3, 2, 2, 4, 4, 5, 5, 2, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5,
            3, 7, 4};
int sg[] = {4, 8, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 9, 3, 3, 0,
            1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 3, 7};
int test, n;

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n;
        int t = 0;
        for (int x, i = 1; i <= n; ++i)
        {
            x = read();
            t ^= x <= 68 ? ss[x] : sg[x % 34];
        }
        if (t) puts("Carol");
        else puts("Dave");
    }
    return 0;
}

POJ2960 S-Nim

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

int s, test, n, a[105], temp[105], sg[10005];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    while (cin >> s, s)
    {
        for (int i = 1; i <= s; ++i)
            a[i] = read();
        memset(sg, 0, sizeof sg);
        for (int i = 1; i <= 10000; ++i)
        {
            for (int j = 1; j <= s; ++j)
                if (i - a[j] >= 0)
                    temp[sg[i - a[j]]] = i;
            for (int j = 0; j <= s; ++j)
                if (temp[j] != i)
                    { sg[i] = j; break; }
        }
        cin >> test;
        while (test--)
        {
            int t = 0;
            cin >> n;
            for (int j = 1; j <= n; ++j)
                t ^= sg[read()];
            putchar(t ? 'W' : 'L');
        }
        puts("");
    }
    return 0;
}

POJ3595 GG and MM

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

int n;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int gcd(int a, int b)
{
    if (b == 0) return 0;
    if (a / b <= 1) return gcd(b, a % b) + 1;
    int t = gcd(b, a % b);
    if (t & 1) return t + 2;
    return t + 1;
}

int main()
{
    while (cin >> n)
    {
        int step = 0;
        for (int x, y, i = 1; i <= n; ++i)
        {
            x = read(), y = read();
            if (x < y) swap(x, y);
            step = max(step, gcd(x, y));
        }
        if (step & 1) puts("MM");
        else puts("GG");
    }
    return 0;
}

POJ2425 A Chess Game

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;

#define N 1005

int n, head[N], cnt;
int sg[N], vis[N], temp[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N * N];

inline void add(int x, int y)
{
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void getsg(int x)
{
    if (vis[x]) return;
    vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        getsg(edge[i].to);
    for (int i = head[x]; i; i = edge[i].next)
        temp[sg[edge[i].to]] = x;
    for (int i = 0; i <= n; ++i)
        if (temp[i] != x)
            { sg[x] = i; break; }
}

int main()
{
    while (cin >> n)
    {
        memset(head, 0, sizeof head);
        cnt = 0;
        for (int s, i = 1; i <= n; ++i)
        {
            s = read();
            while (s--) add(i, read() + 1);
        }
        memset(sg, 0, sizeof sg);
        memset(vis, 0, sizeof vis);
        memset(temp, 0, sizeof temp);
        for (int i = 1; i <= n; ++i)
            getsg(i);
        while (int m = read())
        {
            int t = 0;
            while (m--)
                t ^= sg[read() + 1];
            puts(t ? "WIN" : "LOSE");
        }
    }
    return 0;
}

HDU3537 Daizhenyang's Coin

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int count(int x)
{
    int cnt = 0;
    for (int i = x; i; i >>= 1)
        cnt += i & 1;
    return cnt & 1 ? x : x + 1;
}

int n;

int main()
{
    while (cin >> n)
    {
        int t = 0;
        set<int> s;
        for (int x, i = 1; i <= n; ++i)
        {
            x = read();
            if (s.find(x) == s.end())
                t ^= count(2 * x), s.insert(x);
        }
        puts(t ? "No" : "Yes");
    }
    return 0;
}

HDU3710 Christmas Game

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define N 1005
#define M 10005

int test, n, m, x[M], y[M], head[N], cnt, sg[N];
int tot, deep[N], low[N], dcc, size[N], bel[N];
stack<int> q;

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void tarjan(int x, int fa)
{
    deep[x] = low[x] = ++tot;
    q.push(x);
    for (int i = head[x]; i; i = edge[i].next)
    {
        if (fa == (i ^ 1)) continue;
        if (!deep[edge[i].to])
            tarjan(edge[i].to, i), low[x] = min(low[x], low[edge[i].to]);
        else low[x] = min(low[x], deep[edge[i].to]);
    }
    if (deep[x] == low[x])
    {
        ++dcc;
        while (true)
        {
            int now = q.top(); q.pop();
            bel[now] = dcc;
            if (now == x) break;
        }
    }
}

void dfs(int x, int fa)
{
    sg[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa)
            dfs(edge[i].to, x), sg[x] ^= sg[edge[i].to] + 1;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    while (cin >> test)
    {
        int t = 0;
        while (test--)
        {
            memset(head, 0, sizeof head); cnt = 1;
            cin >> n >> m;
            for (int i = 1; i <= m; ++i)
                x[i] = read(), y[i] = read(),
                add(x[i], y[i]), add(y[i], x[i]);
            tot = 0; dcc = 0;
            memset(deep, 0, sizeof deep);
            tarjan(1, 0);
            memset(head, 0, sizeof head); cnt = 1;
            memset(size, 0, sizeof size);
            for (int i = 1; i <= m; ++i)
                if (bel[x[i]] != bel[y[i]])
                    add(bel[x[i]], bel[y[i]]), add(bel[y[i]], bel[x[i]]);
                else ++size[bel[x[i]]];
            for (int i = dcc; i; --i)
                if (size[i] & 1) add(i, ++dcc), add(dcc, i);
            dfs(bel[1], 0);
            t ^= sg[bel[1]];
        }
        puts(t ? "Sally" : "Harry");
    }
    return 0;
}

BZOJ2940 [Poi2000]条纹

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

int c, z, n, m, sg[1005], temp[100005];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> c >> z >> n;
    for (int i = 1; i <= 1000; ++i)
    {
        for (int j = 0; j + c <= i; ++j)
            temp[sg[j] xor sg[i - j - c]] = i;
        for (int j = 0; j + z <= i; ++j)
            temp[sg[j] xor sg[i - j - z]] = i;
        for (int j = 0; j + n <= i; ++j)
            temp[sg[j] xor sg[i - j - n]] = i;
        for (int j = 0; j > -1; ++j)
            if (temp[j] != i) { sg[i] = j; break; }
    }
    cin >> m;
    while (m--)
        puts(sg[read()] ? "1" : "2");
    return 0;
}

POJ1678 I Love this Game!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

int test, n, a, b, num[10005], f[10005], f2[10005];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void calc(int x)
{
    for (int i = x + 1; i <= n; ++i)
        if (num[i] - num[x] >= a && num[i] - num[x] <= b)
            f[x] = min(f[x], -f[i]);
    if (f[x] == 0x3f3f3f3f) f[x] = num[x];
    else f[x] += num[x];
}

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n >> a >> b;
        for (int i = 1; i <= n; ++i)
            num[i] = read();
        sort(num + 1, num + n + 1);
        memset(f, 0x3f, sizeof f);
        for (int i = n; i; --i)
            if (num[i] >= a) calc(i);
        int ans = 0x80000000;
        for (int i = 1; i <= n; ++i)
            if (num[i] >= a && num[i] <= b)
                ans = max(ans, f[i]);
        if (ans == (int)0x80000000)
            ans = 0;
        cout << ans << endl;
    }
    return 0;
}

POJ2311 Cutting Game

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int n, m, sg[205][205], temp[100005];

int main()
{
    for (int tag = 0, i = 2; i <= 205; ++i)
        for (int j = 2; j <= 205; ++j)
        {
            ++tag;
            for (int k = 2; i - k >= 2; ++k)
                temp[sg[k][j] ^ sg[i - k][j]] = tag;
            for (int k = 2; j - k >= 2; ++k)
                temp[sg[i][k] ^ sg[i][j - k]] = tag;
            for (int k = 0; k > -1; ++k)
                if (temp[k] != tag) { sg[i][j] = k; break; }
        }
    while (cin >> n >> m)
        puts(sg[n][m] ? "WIN" : "LOSE");
    return 0;
}

HDU2177 取(2堆)石子游戏

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

const double a = (1 + sqrt(5.0)) / 2, b = (3 + sqrt(5.0)) / 2;

int n, m, p[1000005];

int main()
{
    for (int i = 1; i * b <= 1000000; ++i)
        p[int(floor(i * a))] = floor(i * b),
        p[int(floor(i * b))] = floor(i * a);
    while (cin >> n >> m, n || m)
    {
        if (p[n] == m) { puts("0"); continue; }
        puts("1");
        if ((m - n) * a < n && (m - n) * b < m)
            cout << floor((m - n) * a) << ' ' << floor((m - n) * b) << endl;
        if (p[m] < n)
            cout << p[m] << ' ' << m << endl;
        if (p[n] < m && min(n, p[n]) != p[m] &&
            min(n, p[n]) != floor((m - n) * a))
            cout << min(n, p[n]) << ' ' << max(n, p[n]) << endl;
    }
    return 0;
}

POJ3922&HDU2580&2486 A simple stone game

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

int test, n, k, a[1000000], b[1000000];

int main()
{
    cin >> test;
    for (int s = 1; s <= test; ++s)
    {
        cout << "Case " << s << ": ";
        cin >> n >> k;
        a[1] = 1; b[1] = 1;
        int tot = 1;
        for (int t = 0; a[tot] < n; ++tot)
        {
            a[tot + 1] = b[tot] + 1;
            while (t < tot && 1ll * a[t + 1] * k < a[tot + 1]) ++t;
            b[tot + 1] = a[tot + 1] + b[t];
        }
        if (a[tot] == n) { puts("lose"); continue; }
        while (true)
        {
            while (a[tot] > n) --tot;
            if (a[tot] == n) { cout << n << endl; break; }
            n -= a[tot];
        }
    }
    return 0;
}

HDU1538 A Puzzle for Pirates

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

int test, n, m, p;

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n >> m >> p;
        if (n <= 2 * m + 1)
        {
            if (p == n) cout << m - (n - 1) / 2 << endl;
            else if (p % 2 == n % 2) cout << 1 << endl;
            else cout << 0 << endl;
        }
        else
        {
            int t = 1;
            while (2 * m + t * 2 <= n) t *= 2;
            if (p > 2 * m + t) cout << "Thrown" << endl;
            else cout << 0 << endl;
        }
    }
    return 0;
}

HDU3404&POJ3533 Light Switching Game

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

int n;

int nim_multi(int x, int y)
{
    if (x < y) swap(x, y);
    if (y == 0) return 0;
    if (x == 1) return 1;
    int t = 2; while (t * t <= x) t = t * t;
    int c1 = nim_multi(x / t, y / t),
        c2 = nim_multi(x / t, y % t) ^ nim_multi(x % t, y / t),
        c3 = nim_multi(x % t, y % t);
    return (c1 ^ c2) * t ^ c3 ^ nim_multi(t / 2, c1);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    while (cin >> n)
    {
        int t = 0;
        while (n--)
            t ^= nim_multi(nim_multi(read(), read()), read());
        if (t) puts("No");
        else puts("Yes");
    }
    return 0;
}

BZOJ1393 [Ceoi2008]knights

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

int k, n, t, x[200005], y[200005];

bool getsg(int x, int y)
{
    if ((x + 3) % 4 <= 1 && (y + 3) % 4 <= 1) return false;
    if (n % 4 == 1 && ((x == n || y == n) && x + y - n != n - 1)) return false;
    if (n % 4 == 0 && x == n && y == n) return false;
    return true;
}

bool check(int x, int y)
{
    if (x <= 0 || x > n || y <= 0 || y > n) return false;
    return true;
}

int getstep(int x, int y)
{
    int re = 0;
    if (getsg(x, y) == false)
    {
        re = ((x - 1) / 4 + (y - 1) / 4) * 2;
        if (n % 4 == 0 && x == n && y == n) re += 2;
        return re;
    }
    if (check(x - 2, y + 1) && !getsg(x - 2, y + 1))
        re = max(re, getstep(x - 2, y + 1));
    if (check(x - 2, y - 1) && !getsg(x - 2, y - 1))
        re = max(re, getstep(x - 2, y - 1));
    if (check(x - 1, y - 2) && !getsg(x - 1, y - 2))
        re = max(re, getstep(x - 1, y - 2));
    if (check(x + 1, y - 2) && !getsg(x + 1, y - 2))
        re = max(re, getstep(x + 1, y - 2));
    return re + 1;
}

void findway(int x, int y)
{
    int s = getstep(x, y);
    if (check(x - 2, y + 1) && getstep(x - 2, y + 1) == s - 1)
        { printf("%d %d\n", x - 2, y + 1); return; }
    if (check(x - 2, y - 1) && getstep(x - 2, y - 1) == s - 1)
        { printf("%d %d\n", x - 2, y - 1); return; }
    if (check(x - 1, y - 2) && getstep(x - 1, y - 2) == s - 1)
        { printf("%d %d\n", x - 1, y - 2); return; }
    if (check(x + 1, y - 2) && getstep(x + 1, y - 2) == s - 1)
        { printf("%d %d\n", x + 1, y - 2); return; }
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> k >> n;
    for (int i = 1; i <= k; ++i)
        x[i] = read(), y[i] = read(),
        t = max(t, getstep(x[i], y[i]));
    if (t % 2 == 0) { puts("NO"); return 0; }
    puts("YES");
    for (int i = 1; i <= k; ++i)
        findway(x[i], y[i]);
    return 0;
}