关于G题我发现是除以 2 上取整减一但是被边界卡住这件事
题很显然可以打表，打表代码如下
#include <bits/stdc++.h>
using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<int> sg(k + 1, -1);
sg[k] = 0;
auto SG = [&](auto self, int n) -> int {
if (~sg[n]) {
return sg[n];
}
std::vector<bool> vis(k + 2);
for (int i = 1; i <= n and n + i <= k; i += 1) {
vis[self(self, n + i)] = true;
}
for (int i = 0; ; i += 1) {
if (!vis[i]) {
return sg[n] = i;
}
}
};
std::cout << "n = " << n << ", k = " << k << ":\n";
for (int i = n; i <= k; i += 1) {
std::cout << SG(SG, i) << " \n"[sg[i] == 0];
}
std::cout << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(12);
int T = 1;
std::cin >> T;
while (T--) {
solve();
}
return 0;
}
我看了其中两组
Case #1
Input
15
10 40
10 41
10 42
10 43
10 44
10 45
10 46
10 47
10 48
10 49
10 50
10 51
10 52
10 53
10 54
Output
n = 10, k = 40:
9 8 7 6 5 4 3 2 1 0
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 41:
10 9 8 7 6 5 4 3 2 1 0
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 42:
10 9 8 7 6 5 4 3 2 1 0
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 43:
0
10 9 8 7 6 5 4 3 2 1 0
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 44:
0
10 9 8 7 6 5 4 3 2 1 0
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 45:
0
11 10 9 8 7 6 5 4 3 2 1 0
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 46:
0
11 10 9 8 7 6 5 4 3 2 1 0
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 47:
1 0
11 10 9 8 7 6 5 4 3 2 1 0
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 48:
1 0
11 10 9 8 7 6 5 4 3 2 1 0
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 49:
1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 50:
1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 51:
2 1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 52:
2 1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 53:
2 1 0
13 12 11 10 9 8 7 6 5 4 3 2 1 0
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 54:
2 1 0
13 12 11 10 9 8 7 6 5 4 3 2 1 0
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Case #2
Input
15
10 100
10 101
10 102
10 103
10 104
10 105
10 106
10 107
10 108
10 109
10 110
10 111
10 112
10 113
10 114
Output
n = 10, k = 100:
1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 101:
1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 102:
1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 103:
2 1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 104:
2 1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 105:
2 1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 106:
2 1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 107:
2 1 0
13 12 11 10 9 8 7 6 5 4 3 2 1 0
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 108:
2 1 0
13 12 11 10 9 8 7 6 5 4 3 2 1 0
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 109:
2 1 0
13 12 11 10 9 8 7 6 5 4 3 2 1 0
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 110:
2 1 0
13 12 11 10 9 8 7 6 5 4 3 2 1 0
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 111:
3 2 1 0
13 12 11 10 9 8 7 6 5 4 3 2 1 0
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 112:
3 2 1 0
13 12 11 10 9 8 7 6 5 4 3 2 1 0
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 113:
3 2 1 0
13 12 11 10 9 8 7 6 5 4 3 2 1 0
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
n = 10, k = 114:
3 2 1 0
13 12 11 10 9 8 7 6 5 4 3 2 1 0
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
我们逆序来看，注意到从 开始每次都是除以
上取整减一，除了最后最接近
的那一次。
同时我们不关心具体的值是什么，只看是否等于 ，所以只要看最后
是否会除到
，如果越界直接
Alice 获胜。
C++ 代码
#include <bits/stdc++.h>
using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;
void solve() {
int n, k;
std::cin >> n >> k;
while (true) {
if (k == n) {
std::cout << "Bob\n";
return;
} else if (k < n) {
std::cout << "Alice\n";
return;
}
k = (k - 1) / 2;
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(12);
int T = 1;
std::cin >> T;
while (T--) {
solve();
}
return 0;
}
腾讯泡池子942人在聊