利用一个星期的时间学习了博弈问题的基础知识, 做了最简单的若干习题, 在这里总结一下;


基础知识


平等博弈

与不平等博弈对立, 先后手面对不同局面, 可以做相同的决策, 是比较常见的类型, 我学习的是和平等博弈有关的内容;
重要的性质: 必败局面的后继局面一定是必胜局面, 必胜局面的后继局面一定存在必败局面;


sg函数

\[sg[S]=mex \\{ sg[T] | T \in next(S) \\}\]

\(sg[S] = 0\), \(S\)为必胜局面,\(sg[S] \neq 0\), \(S\)为必负局面;

游戏的和

当一个游戏\(S\)可以拆成若干个子游戏\(G_i, (i \in [1, n])\), 且不存在子游戏间的干扰, 那么该游戏可以认为是这若干个子游戏的和, \(sg[S] = sg[G_1] \ xor \ sg[G_2] \ xor \ ... \ xor \ sg[G_n]\);



经典模型


石子类

  1. Nim Game
    • n堆石子,双方轮流从任意一堆石子中取出至少一个,不能取的人输.
    • 对于一堆x个石子, \(sg(x)=x\).
    • 利用游戏的和, 所以所有石子个数的异或和为0是必败态,否则为必胜态.
  2. Bash Game
    • 每人最多一次只能取m个石子,其他规则同Nim Game.
    • \(sg(x)=x \space mod \space (m+1)\).
  3. Nim_K Game
    • 一次可以从最多K堆石子中取出任意多个,其他规则同Nim Game.
    • 在二进制下各位上各堆石子的数字之和均为(K+1)的倍数的话则为必败态,否则为必胜态.
    • 推广: 一个由n个子游戏组成的游戏,每次可以在最多K个子游戏中进行操作.
    • 然后只要把结论中各堆石子的个数改为各个子游戏的SG值即可.
  4. Anti-Nim Game(Misère Nim)
    • 不能取的一方获胜,其他规则同Nim Game.
    • 关于所谓的”Anti-SG游戏”及”SJ定理”贾志鹏的论文上有详细说明,不过似乎遇到并不多.
    • 结论是一个状态是必胜态当且仅当满足以下条件之一:
      1. SG值不为0且至少有一堆石子数大于1;
      2. SG值为0且不存在石子数大于1的石子堆.
  5. Staircase Nim
    • 每人一次可以从第一堆石子中取走若干个,或者从其他石子堆的一堆中取出若干个放到左边一堆里(没有石子的石子堆不会消失),其他规则同Nim Game.
    • 当且仅当奇数编号堆的石子数异或和为0时为必败态.
    • 将石子从奇数推向偶数可以理解为拿走石子, 偶数推向奇数后手可以接着推回偶数, 理解为没有进行操作;
  6. Wythoff Game
    • 有两堆石子,双方轮流从某一堆取走若干石子或者从两堆中取走相同数目的石子,不能取的人输.
    • 对任意自然数k,都存在唯一的一个必败态使得两堆石子数差为k,设其为\(P_k=(a_k,b_k)\),表示石子数分别为\(a_k,b_k(ak⩽bk)\).
    • 那么\(a_k\)为在\(P_{k0}(k0<k)\)中未出现过的最小自然数,\(b_k=a_k+k\).
    • 结论:\(a_k = \lfloor \frac{ \sqrt{5} + 1}{2} * k \rfloor\).

非石子类

  1. 翻硬币游戏

    n枚硬币排成一排,有的正面朝上,有的反面朝上。

    游戏者根据某些约束翻硬币(如:每次只能翻一或两枚,或者每次只能翻连续的几枚),但他所翻动的硬币中,最右边的必须是从正面翻到反面。

    谁不能翻谁输。

    把游戏转化为其他的取石子游戏之类的,然后用如下定理解决:

    局面的 SG 值等于局面中每个正面朝上的棋子单一存在时的 SG 值的异或和。

  2. 树上删边游戏

    给出一个有n个结点的树,有一个点作为树的根节点,双方轮流从树中删去一条边边,之后不与根节点相连的部分将被移走,无法操作者输.

    结论: 叶子结点的SG值为0,其他结点SG值为其每个儿子结点SG值加1后的异或和.

  3. 无向图删边游戏

    一个无向连通图,有一个点作为图的根。

    游戏者轮流从图中删去边, 删去一条边后,不与根节点相连的部分将被移走。

    谁无路可走谁输。

    对于这个模型,有一个著名的定理——Fusion Principle:

    我们可以对无向图做如下改动:将图中的任意一个偶环缩成一个新点,任意一个奇环缩成一个新点加一个新边;所有连到原先环上的边全部改为与新点相连。 这样的改动不会影响图的 SG 值。


习题

  • 【51nod1661】 黑板上的游戏 解题报告: 固定题目中的\(k\), 对sg函数进行大表, 可以发现显然的规律: \(sg(1)=0, sg(ak+1)=sg(a), sg(ak+b)=a(k-1)+b-1(1<b<=k)\), 可以使用归纳法进行证明.
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef double ff;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N = 100010;
ll n, sg[N], a[N], k, ans;
inline ll got(ll x) {
return x - (x+k-1)/k;
}
inline ll calc(ll a) {
if (a % k != 1) return got(a);
else return calc(a/k);
}
inline ll able(ll sg, ll a) {
ll tmp = sg + (sg + k-2) / (k-1);
while (tmp < a) {
if ((ff)tmp * (ff)k >= a)
return tmp;
if ((ff)tmp * (ff)k + 1.0 >= a)
return 0;
tmp = tmp * k + 1;
}
return 0;
}
int main() {
/*make a list to look
int f[N], app[N], k, n;
cin >> n >> k;
f[1] = 0;
FORU(i, 2, n) {
mmst(app, 0);
FORU(j, max(1, i/k), i-1) {
if (j * k < i) continue;
app[f[j]] = 1;
}
FORU(j, 0, i) if (!app[j]) {
f[i] = j; break;
}
}
FORU(i, 1, n)
cout << i << ": " << f[i] <<endl;
*/
ios :: sync_with_stdio(false);
cin >> n >> k; ll x;
FORU(i, 1, n) {
cin >> a[i], sg[i] = calc(a[i]);
ans ^= sg[i];
}
if (!ans) puts("Bob");
FORU(i, 1, n) {
if (x = able(sg[i] ^ ans, a[i])) {
printf("Alice %d %lld\n", i, x);
return 0;
}
}
return 0;
}
  • 【51nod1714】 B君的游戏 解题报告: 根据游戏规则,游戏可以看做若干子游戏的和, 每堆石子的sg函数, 只与石子个数的二进制1数有关, 而二进制数位最多有60个1, 所以直接对二进制1数进行打表sg;
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef unsigned long long ull;
typedef double ff;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N = 100100;
ull a;
int ans, n;
const int sg[70]={0,1,2,4,8,16,32,64,128,255,256,512,1024,2048,3855,4096,8192,13107,16384,21845,27306,32768,38506,65536,71576,92115,101470,131072,138406,172589,240014,262144,272069,380556,524288,536169,679601,847140,1048576,1072054,1258879,1397519,2005450,2097152,2121415,2496892,2738813,3993667,4194304,4241896,4617503,5821704,7559873,8388608,8439273,8861366,11119275,11973252,13280789,16777216,16844349,17102035,19984054,21979742};
int main() {
cin >> n; int tmp;
FORU(i, 1, n) {
cin >> a, tmp = 0 ;
while (a) tmp += a&1, a >>= 1;
ans ^= sg[tmp];
}
puts((ans?"B":"L"));
return 0;
}
  • 【hackerrank】 Nimble Game 因为\(i\)位置的石子只能移向\(j(j<i)\)的位置, 所以可以将\(i\)位置的每一个石子转换成一堆有\(i\)个石子的石子,直接求sg函数;
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef double ff;
typedef vector<ll> vi;
typedef pair<int, int> pii;
const int N = 100100;
int test, n, ans, x;
int main() {
ios :: sync_with_stdio(false);
cin >> test;
while (test--) {
ans = 0, cin >> n;
REP(i, n) {
cin >> x;
if (x & 1) ans ^= i;
}
puts((ans?"First":"Second"));
}
return 0;
}
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef double ff;
typedef vector<ll> vi;
typedef pair<int, int> pii;
int sg[100001];
int p,xs,x,t,n;
vector <int > v;
void _div() {
sg[1]=0;
for (int i=2;i<=100000;i++) {
v.clear();
v.push_back(-1);
p=sqrt(i);
for (int j=1;j<=p;j++)
if (i%j==0) {
if (j%2!=0) v.push_back(sg[i/j]);
if ((i/j)%2!=0) v.push_back(sg[j]);
}
v.push_back(10000000);
sort(v.begin(),v.end());
for (int j=1;j<v.size();j++)
if (abs(v[j]-v[j-1])>1)
sg[i]=v[j-1]+1;
}
}
int main() {
scanf("%d",&t);
_div();
while (t--) {
scanf("%d",&n);
xs=0;
REP(i, n) {
scanf("%d",&x);
xs=xs^sg[x];
}
if (xs==0) printf("2\n");
else printf("1\n");
}
return 0;
}
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef double ff;
typedef vector<ll> vi;
typedef pair<int, int> pii;
int sg[15][15];
inline bool cmp(pii a, pii b) {
if (a.fi + a.se != b.fi + b.se)
return a.fi + a.se < b.fi + b.se;
else
return (a.fi < b.se);
}
vector<pii> vec;
int main() {
ios :: sync_with_stdio(false);
REP(i, 15) REP(j, 15)
vec.pb(mp(i, j));
sort(vec.begin(), vec.end(), cmp);
for (vector<pii>::iterator it = vec.begin(); it != vec.end(); it++) {
int i = it->first;
int j = it->second;
sg[i][j] = 0;
for (int x = 0;; x++) {
bool found = false;
if (i-2 >= 0 && j-1 >= 0 && sg[i-2][j-1] == x) found = true;
if (i-2 >= 0 && j+1 < 15 && sg[i-2][j+1] == x) found = true;
if (i-1 >= 0 && j-2 >= 0 && sg[i-1][j-2] == x) found = true;
if (i+1 < 15 && j-2 >= 0 && sg[i+1][j-2] == x) found = true;
if (!found) {
sg[i][j] = x; break;
}
}
}
int test, x, y, k;
cin >> test;
while (test--) {
cin >> k;
int total_sg = 0;
while (k--) {
cin >> x >> y;
total_sg ^= sg[x-1][y-1];
}
puts((total_sg == 0 ? "Second" : "First"));
}
return 0;
}
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef double ff;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N =31;
int a[N][N], gr[N][N][N][N], n, t;
int prime_check(int x, int y, int z, int m) {
FORU(i, x, z) FORU(j, y, m)
if (a[i][j]==1 || a[i][j]==4 || a[i][j]==6 || a[i][j]==8 || a[i][j]==9) return 0;
return 1;
}
int grundy(int x, int y, int z,int m) {
int v[75];
if (gr[x][y][z][m]!=-1)
return gr[x][y][z][m];
if (prime_check(x ,y ,z ,m)) {
gr[x][y][z][m]=0;
return 0;
}
for (int i=0;i<75;i++) v[i]=0;
for (int i=x+1;i<=z;i++) v[grundy(x,y,i-1,m)^grundy(i,y,z,m)]=1;
for (int i=y+1;i<=m;i++) v[grundy(x,y,z,i-1)^grundy(x,i,z,m)]=1;
for (int i=0;i<75;i++)
if (v[i]==0) {
gr[x][y][z][m]=i;
return gr[x][y][z][m];
}
return -1;
}
void solve() {
scanf("%d",&n);
FORU(i, 1, n) FORU(j, 1, n)
scanf("%d",&a[i][j]);
mmst(gr, -1);
grundy(1,1,n,n);
if (gr[1][1][n][n]!=0) printf("First\n");
else printf("Second\n");
}
int main() {
scanf("%d",&t);
while(t--) solve();
return 0;
}
  • 【hackerrank】Stone Division 解题报告: 同样, 记忆化搜索求sg函数, 每个数的约数个数是\(O( \sqrt[3]{n})\)级别的,所以直接暴力枚举每个数被哪些集合中的数分解;
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef double ff;
typedef vector<ll> vi;
vi s;
map<int, bool> rec;
ll n, m;
bool dfs(ll x) {
if (rec.find(x) != rec.end())
return rec[x];
REP(i, sz(s))
if (x % s[i] == 0)
if (x / s[i] % 2 == 0)
return (rec[x] = 1);
else
if (!dfs(x / s[i]))
return (rec[x] = 1);
return (rec[x] = 0);
}
int main() {
ios :: sync_with_stdio(false);
cin >> n >> m; ll x;
REP(i, m) cin >> x, s.pb(x);
if (dfs(n)) puts("First");
else puts("Second");
return 0;
}
  • 【hackerrank】Simple Game 解题报告: 如果\(k=2, sg[x] = (x-1)&1\), 如果\(k > 3, sg[x] = x - 4\),如果\(k = 3\), 利用dp, 统计sg值为\(x\)的方案数, 最后输出sg值不为0的方案数;
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef double ff;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N = 602, K = 1024, p = 1E9 + 7;
int dp[N][K], nwdp[N][K], m, n, k, sg[N];
bool can[K];
int main() {
cin >> m >> n >> k;
if (k == 2) {
FORU(i, 1, 600)
if (i % 2 == 1) sg[i] = 0;
else sg[i] = 1;
}
if (k == 3) {
sg[1] = 0;
FORU(i, 1, 600) {
memset(can, 0, sizeof(can) );
FORU(j, 1, i-1) {
int cur = sg[j] ^ sg[i - j];
can[cur] = true;
}
FORU(j, 1, i - 2) {
for (int l = 1; j + l < i; l++) {
int cur = sg[j] ^ sg[l] ^ sg[i - j - l];
can[cur] = true;
}
}
REP(j, K)
if (can[j] == false) {
sg[i] = j; break;
}
}
}
if (k > 3) FORU(i, 1, 600) sg[i] = i - 1;
dp[0][0] = 1;
REP(i, n) {
memset(nwdp, 0, sizeof(nwdp) );
REP(j, m) REP(gr, K) {
if (dp[j][gr] == 0) continue;
for (int nxt = 1; nxt + j <= m; nxt++) {
nwdp[j + nxt][gr^sg[nxt] ] += dp[j][gr];
if (nwdp[j + nxt][gr^sg[nxt] ] >= p)
nwdp[j + nxt][gr^sg[nxt] ] -= p;
}
}
swap(dp, nwdp);
}
int s = 0;
FORU(i, 1, K-1){
s += dp[m][i];
if (s >= p) s -= p;
}
cout << s << endl;
return 0;
}
  • 【hackerrank】Move the Coins 解题报告: 一个树上阶梯问题, 静态的情况是奇数层的石子异或和,现在可以改变一个子树深度的奇偶,只需要维护这个子树的异或和, 在基础异或和上异或即可;
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef double ff;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N = 51000;
int n, q, c[N], in[N], out[N], body[N], cnt, pre[N], dep[N], ans;
vi nxt[N];
void dfs(int x, int fa) {
int y;
in[x] = ++cnt, body[cnt] = x;
dep[x] = dep[fa] ^ 1;
if (dep[x]) ans ^= c[x];
REP(i, sz(nxt[x])) {
y = nxt[x][i];
if (y != fa) dfs(y, x);
}
out[x] = cnt;
}
inline int got(int l, int r) {
return pre[r] ^ pre[l-1];
}
int main() {
ios :: sync_with_stdio(false);
cin >> n; int x, y;
FORU(i, 1, n) cin >> c[i];
FORU(i, 1, n - 1) {
cin >> x >> y;
nxt[x].pb(y), nxt[y].pb(x);
}
dep[0] = 1, dfs(1, 0);
FORU(i, 1, n) pre[i] = pre[i-1] ^ c[body[i]];
cin >> q;
while (q --) {
cin >> x >> y;
if (in[y] >= in[x] && in[y] <= out[x])
puts("INVALID");
else if (dep[y]^dep[x])
puts((ans?"YES":"NO"));
else
puts((ans^got(in[x], out[x]))?"YES":"NO");
}
return 0;
}
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef double ff;
typedef vector<int> vi;
typedef pair<int, int> pii;
int f[60] = {0, 0, 0, 1, 0, 2, 3, 4, 0, 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};
int test, n, ans;
int main() {
ios :: sync_with_stdio(false);
cin >> test;
while (test--) {
cin >> n, ans = 0;
int x;
FORU(i, 1, n) cin >> x, ans = ans ^ f[x];
puts(ans?"ALICE":"BOB");
}
return 0;
}
/*
bitset<1000000000> ap;
void dfs(int lef, int s, int ha, int d) {
if (!lef && d > 1) ap.set(ha);
FORU(i, s, lef) dfs(lef - i, i + 1, ha ^ f[i], d + 1);
}
int main() {
freopen("A.out", "w", stdout);
cout << "{0";
f[1] = 0;
FORU(i, 2, 50) {
ap.reset();
dfs(i, 1, 0, 0);
REP(j, 1000000000) if (ap[j] == 0) {
f[i] = j; break;
}
cout << ", " << f[i];
}
cout << "};" << endl;
return 0;
}
*/
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef double ff;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N = 100010;
int n, a[N];
int main() {
ios :: sync_with_stdio(false);
cin >> n; FORU(i, 1, n) cin >> a[i];
ll ans = 0, tot = 0, mark = 0;
static map<int, int> hav;
for (int x = 1; x <= n; x += 2) {
if (x > 1) {
ans += tot - hav[(a[x] - a[x-1])^mark];
if (a[x] - a[x-1]) ++ ans;
// DEBUG(x); DEBUG(ans);
}
if (x == 1) mark^=a[x], hav[a[x]^mark] += 1, tot += 1;
if (x > 1) {
mark ^= a[x] - a[x-1];
hav[a[x]^mark] += 1, tot += 1;
hav[(a[x] - a[x-1])^mark] += 1, tot += 1;
}
}
mark = tot = 0;
hav.clear();
for (int x = 2; x <= n; x += 2) {
ans += tot - hav[(a[x] - a[x-1])^mark];
if (a[x] - a[x - 1]) ++ ans;
// DEBUG(x); DEBUG(ans);
mark ^= a[x] - a[x-1];
hav[a[x] ^ mark] += 1, tot += 1;
hav[(a[x] - a[x-1]) ^ mark] += 1, tot += 1;
}
cout << ans << endl;
return 0;
}
  • 【hackerrank】Return of the Nim 解题报告: 如果\(n=2\), 问题就是经典的威佐夫问题;否则, \(n\)一定为奇数, 如果当前局面当做经典nim游戏求sg为必败态, 那么即使使用全局减法,所得后继状态一定为必胜态,即当前局面仍为必败态;
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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define mmst(a, x) memset(a, x, sizeof(a))
#define DEBUG(x) cout << #x << " : " << (x) << endl;
#define LOOK(x, a, b) {cout << #x << " : ";FORU(i, a, b) cout << x[i] << ' '; cout << endl; }
typedef long long ll;
typedef double ff;
typedef vector<int> vi;
typedef pair<int, int> pii;
ll a = 618033988, b = 749894848, c = 204586834;
ll p = 1000000000, n, m, x, nInt, nDec, test;
int main() {
ios :: sync_with_stdio(false);
cin >> test;
int tInt, tDec, N, ans;
while (test--) {
cin >> N;
if (N == 2){
cin >> n >> m;
if (n < m) swap(n, m);
n -= m;
if (n > m || (n << 1) < m) puts("Sherlock");
else {
nInt = n / p, nDec = n % p;
x = nDec * c;
x = b * nDec + c * nInt + x / p;
x = a * nDec + b * nInt + x / p;
x = n + a * nInt + x / p;
if (x == m) puts("Watson");
else puts("Sherlock");
}
} else {
ans = 0;
FORU(i, 1, N) cin >> x, ans ^= x;
puts((ans?"Sherlock":"Watson"));
}
}
return 0;
}

留言