注意力惊人

xiaoyi_zeng · 2025-12-03 19:23:34 · 题解

B4395

哇塞，可以写题解。

打表找规律

首先你需要一份打表代码。

:::info[打表代码]

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

vector <int> v;

int main(){
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) v.push_back(i);
    while (v.size()){
        cout << v[0] << " ";
        vector <int> t;
        for (int i = 0; i < v.size(); i ++){
            if (i % k == 0) continue;
            t.push_back(v[i]);
        }
        v = t;
    }
    cout << "\n";
}

:::

嗯对，在这里 30 已经足够大了。

请不要试图输入 10^5 及以上的 n，除非你拥有一个强大的 CPU。

注意力惊人

正片开始。

首先，上面的代码所输出的是每一轮删除的第一个数。

注意到题目中没有说如果最后一轮淘汰了所有人怎么办，所以最后一轮之后肯定只剩下一个人。

注意到这一个人一定是最后输出的那个数字。

注意到如果令程序输出的第 i 个数维 x_i，则如果 x_{i+1} 存在，x_{i+1}=x_i+\lceil \frac{x_i}{k-1} \rceil。

代码编写

如果你直接写，那恭喜你成为 @KingGojianOfYue 大佬的 Hack 对象。

考虑维护长度为 k - 1 的块。

如果 x 在这个块里面，就直接一直跳，跳出去。

可以证明，这样做的时间复杂度不会超过 O( \sqrt{n} )。

你可能会问，这不是 O(\frac{n}{k}) 的吗，如果 k=2 不炸了。

实则不然，仔细一想，当 k=2 的时候，当我在 x 较大的移动时一次会移动回跨越非常多的块，此时就会节约许多时间，如此算下来，时间复杂度最大值即为 O(\sqrt{n})。

Code

:::success[AC code]

#include <bits/stdc++.h>
using namespace std;

long long n, k;

int main(){
    cin >> n >> k;

    long long x = 1, lst = 0;
    while (x <= n){
        long long id = (x - 1) / (k - 1) + 1;
        long long end = min(n, id * (k - 1));

        x = (x + ((end - x) / id + 1) * id);
        lst = x - id;
    }

    cout << lst << "\n";
}

:::