题目大意
这是问题的简单版本。版本之间的区别在于x的约束；在这个版本中，x≤105。
Polycarp有一个包含从1到1012的所有自然数的序列。他决定通过执行以下操作$ x $次来修改这个序列：
- 同时删除所有在位置y，2⋅y，3⋅y，…，m⋅y≤n的数字，其中$ n $是当前序列的长度。
之后，Polycarp想要在剩余序列中找到第$ k 个数字，或确定结果序列的长度小于 k $。
帮助Polycarp解决这个问题！
考虑一个例子。假设$ x = 2 ， y = 3 ， k = 5 $，那么：
红线划掉的数字在第一次操作后被删除，蓝线划掉的数字在第二次操作后被删除。因此，位置$ k = 5 处的数字是数字 10 $。
思路讲解
二分答案。
思路参考了A_G 的代码。
将这道题目转化为二分答案的关键，就在于把找到剩余的第 $ k $ 个数字，转化为找到一个长度为 len 的初始序列，使得其剩余至少 k 个数字，那么不难发现，最小的，符合我们的要求的 len 就是答案。
那么，一次操作会减少多少个数字（长度为 len 时）？ 其实就是 ⌊ylen⌋。
因此，简单版本，检查函数也不难书写，直接模拟改过程即可：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| auto check=[&](ll len) {
ll cnt=1;
while (cnt<=X) {
if (len<=0) {
break;
}
len-=len/Y;
++cnt;
}
if (len>=K) {
return true;
}
return false;
};
|
AC代码
AC
https://codeforces.com/contest/2169/submission/360432707
源代码
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
void Solve() {
ll X,Y,K;
cin >> X >> Y >> K;
if (Y==1) {
cout<<-1<<"\n";
return;
}
auto check=[&](ll len) {
ll cnt=1;
while (cnt<=X) {
if (len<=0) {
break;
}
len-=len/Y;
++cnt;
}
if (len>=K) {
return true;
}
return false;
};
auto range=ranges::views::iota(1ll,(ll)1e12+1)|views::reverse;
auto it=ranges::partition_point(range,check);
if (it==range.begin()) {
cout<<-1<<"\n";
return;
}
ll ans=*ranges::prev(it);
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
|
心路历程（WA，TLE，MLE……）