当前位置：首页 > news >正文

题解：B4395 [常州市赛 2025] 金币

news 2026/6/12 6:24:56

题解：B4395 [常州市赛 2025] 金币

前言

题目传送门

思路讲解

一个十分经典的约瑟夫问题。

我们可以想象淘汰的过程，相当于每 $k$ 个人中有1人被淘汰，留下来 $k-1$ 个人，而且多余的人也会有一人被淘汰，那么我们就可以设置一个答案变量 $x$，表示答案位置，那么根据刚才的推论，答案每次加上 $\left \lceil \frac{x}{k-1} \right \rceil $，直到其加上后大于 $n$ 就输出。

但是很明显会超时，当 $k$ 非常大的时候，时间复杂度接近 $O(n)$，$k$ 较小是时间复杂度是 $O(log$ $n)$ 或者 $O(k$ $log$ $n)$，直接炸掉。

我们需要去优化时间复杂度，根据每次 $x$ 加上的值去分情况解决：

当这个值 $<k$ 时，需要求出 $x$ 要多久才能使加上的数加 1。
当这个值 $\ge k$ 时，暴力出奇迹。

Code

#include <bits/stdc++.h>
#define int long long // 不开longlong见祖宗
using namespace std;
int n, k;
// 计算下一个安全位置的函数
inline int add(int u)
{// 这个公式用于计算在当前淘汰规则下，下一个不会被淘汰的位置return u + 1 + (u - 1) / (k - 1);
}
signed main()
{cin >> n >> k; //输入int x = 1; // 初始位置设为1// 第一个循环：尝试快速逼近最终解，最多循环k次for (int i = 0; i < k; i++){// cur表示在当前步长(i+1)下可以跳过的最大步数int cur = k - 1 - (x - 1) / (i + 1);// 如果跳过cur步后会超过或等于n，直接计算最终位置if (x + cur * (i + 1) >= n){// 计算最终位置：x加上剩余步数x += (n - x) / (i + 1) * (i + 1);cout << x << endl; // 输出结果return 0;}else{// 否则，更新x的位置x += cur * (i + 1);}}// 第二个循环：如果第一个循环没有找到解，继续逐步计算while (1){// 计算下一个安全位置if (add(x) > n){// 如果下一个位置超过n，当前x就是解break;}// 否则，更新xx = add(x);}cout << x << endl; // 输出最终结果return 0;
}