题目大意
这是问题的简单版本。版本之间的区别在于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 $。
思路讲解
D1 思路
二分答案。
思路参考了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;
};
|
我们直接使用这个第一问当中的这个 check 函数，由于其是 O(X)，会超时。我们也可以优化这个二分检查器代码，让其一次性把 subtract←⌊ylen⌋ 相同的一起处理。这样子，使用二分的复杂度就是 O(AlogA)，其中 A 是一个数字能够拥有的这个因数数量量级。
不过题目作者专门卡了我们二分答案一手，因此必须采用逆向还原的思路。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| for (ll i=1;i<=X;++i) {
ll subtract=0;
if (len%(Y-1)==0) {
subtract=len/(Y-1)-1;
len+=subtract;
}else {
subtract=len/(Y-1);
ll dis=((Y-1)*(subtract+1))-len;
ll cnt=(dis+subtract-1)/subtract;
cnt=min(X-i+1,cnt);
i+=cnt-1;
len+=cnt*subtract;
}
if (len>(ll)1e12) {
cout<<-1<<"\n";
return;
}
}
|
逆向还原，我们知道，每出现 y−1 个数字，那么就代表有一个数字被删除了，那么一次需要增长的长度就是 ⌊y−1len⌋？
这里有一个比较阴的特殊情况，就是 len≡0(mody−1)，这个时候，能够增长的长度就是只有 ⌊y−1len⌋−1。
我们可以就像最简单的，当序列长度为 y−1，其达到 y−1 需要多少长度，是 y 吗？显然不是，其需要增长的就是 0 长度。
我们和优化二分的时候采用一样的思路，每次增长相同长度的，一起操作，这样子时间复杂度就是 O(A)。
具体而言，就是先计算需要增长的长度 subtract，然后计算需要能够以 subtract 继续增长的次数，即 cnt，然后 cnt←min(cnt,X−i+1)，避免加上 cnt 超过操作次数限制。不断重复这个过程，直到达到操作次数 X。
AC代码
AC
https://codeforces.com/contest/2169/submission/360686378
源代码
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
105
106
107
108
109
110
111
112
113
|
#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>
#include <cassert>
#include <cstdio>
#include <chrono>
#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;
}
ll len=K;
if (K<Y) {
cout<<K<<"\n";
return;
}
for (ll i=1;i<=X;++i) {
ll subtract=0;
if (len%(Y-1)==0) {
subtract=len/(Y-1)-1;
len+=subtract;
}else {
subtract=len/(Y-1);
ll dis=((Y-1)*(subtract+1))-len;
ll cnt=(dis+subtract-1)/subtract;
cnt=min(X-i+1,cnt);
#ifdef LOCAL
assert(cnt>0);
#endif
i+=cnt-1;
len+=cnt*subtract;
}
if (len>(ll)1e12) {
cout<<-1<<"\n";
return;
}
}
cout<<len<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
|
TLE
https://codeforces.com/contest/2169/submission/360461585
二分 TLE 代码
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#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>
#include <cassert>
#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) {
if (len<Y) {
if (len>=K) {
return true;
}
return false;
}
for (ll i=1;i<=X;++i){
if (len<=0) {
break;
}
ll subtract=len/Y;
if (subtract<=0) {
break;
}
ll rem=len-(Y*subtract-1);
ll cnt=(rem+subtract-1)/subtract;
cnt=min(X-(i-1),cnt);
#ifdef LOCAL
assert(cnt>0);
#endif
i+=cnt-1;
len-=cnt*subtract;
}
if (len>=K) {
return true;
}
return false;
};
auto range=views::iota(1ll,(ll)1e12+1ll)|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……）