前言
也是之前赛时没做出来的一道题，题意很简单，做法也不难，但是计算时间复杂度可能会难一些，所以很多看起来比较暴力的写法不感谢
题意
对于[0, s]的一段区间，第一步可以走任意次k格（走到k、2k、3k……），第二次需要掉头，走任意次(k-1)格，第三次掉头走任意次(k-2)格……第k次掉头走任意次1格，之后走的距离固定为每次1格，求最早到达s的时间。
思路
先找到一些特例：
- 当
s % k == 0：直接输出k即可
- 当
k < 2，那么最终答案一定为1
- 当
k * k <= s，最终答案一定为k或k-2，取决于k是否整除s
前两个特判比较显然，这题的核心在于第三个特判：
如果能量为k时到达s，那么s一定被k整除，否则无法到达s；
如果能量为k-1，Gleb的方向指向起点，不可能在此时到达s；
当能量为k-2时，能否到达s与前两次的步数有关。但注意到我们在第一步走k次，我们在第二次操作时通过左移某个步数x一定可以实现$s - k \times k + x \times (k - 1) \mod (k - 2) = 0$
证毕.
进行完特判之后，我们开始考虑对其余情况的判断。假设答案为ans，我们如果在每次遍历从0到s所有的位置，总的时间复杂度为$O(s\times(k - ans))$，这个时间复杂度能否被接受取决于s和ans的范围
根据特判3，如果s过大,超过k方，我们可以直接将其特判掉，不需要考虑其1e9的范围；
对于ans，我们同样可以根据特判三估计出其可能的最小值应该接近$\sqrt s$.
所以设最大运行时间为T，T可以近似为$s \times (k - \sqrt s)$
T什么时候取最大值呢？
考虑均值不等式，
当
即
T取得最大值$\frac{4k^3}{27}$
这个复杂度是勉强可以接受的，只是需要注意下常数。
至此，我们对步数从k到1遍历，可以使用bfs进行更新
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
| #include <bits/stdc++.h>
using namespace std;
int s, k;
void solve() {
cin >> s >> k;
if(s % k == 0) {
cout << k << endl;
return;
}
if(k <= 2) {
cout << 1 << endl;
return;
}
if(s >= k * k) {
cout << k - 2 << endl;
return;
}
queue<pair<int, int>> q;
q.push({0, k + 1});
for(int i = k; i >= 1; --i) {
if(i % 2 == k % 2) {
set<int> st;
while(q.front().second > i) {
int top = q.front().first; q.pop();
if(st.count(top)) continue;
for(int j = top + i; j <= s and !st.count(j); j += i) {
st.insert(j);
q.push({j, i});
}
}
if(st.count(s)) {
cout << i << endl;
return;
}
} else {
set<int> st;
while(q.front().second > i) {
int top = q.front().first; q.pop();
if(st.count(top)) continue;
for(int j = top - i; j >= 0 and !st.count(j); j -= i) {
st.insert(j);
q.push({j, i});
}
}
if(st.count(s)) {
cout << i << endl;
return;
}
}
}
cout << 1 << endl;
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t; cin >> t;
while(t--) {
solve();
}
return 0;
}
|
后记
题目本身不难，但是如果赛时因为常数TLE掉怀疑自己时间复杂度算错也不是不可能……
