竞赛讨论区 > 关于G题我发现是除以 2 上取整减一但是被边界卡住这件事
头像
Levi_yxc
发布于 05-12 17:33
+ 关注

关于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;
}
2025最新求职资料大礼包领取
真题
历年笔试真题附答案
爱奇艺2020校招编程题汇总
作业帮2021校园招聘-动画设计师
2021届伴鱼春季校园招聘技术岗B卷
全部 >
面经
面试常考问题整理
管理类双非硕的23秋招记录＆反思
0926腾讯音乐笔试题解
2022考研失败春招选手的群面攻略（适用于菜鸡互啄型）
全部 >
内推
员工内推码获取
拼多多2025校招内推
明阳内推码 ISKJ1B
同花顺算法专场笔试倒计时1天！可内推
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(0) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”