传送门：https://codeforces.ml/contest/1469/problem/D
题意
一段序列$a_1…a_n，a_i=i$，最多n+5次操作后，使序列变为n-1个1和1个2。 这个操作为，先选择两个数x和y，然后使$ax=\left \lceil \frac{ax}{ay} \right \rceil$.
思路
辗转根号，这个操作在n=2e5时，最多5*2次，每次$(n,\sqrt n)$需要两次。
对于每个区间$(\sqrt n, n)$，只需要选择(i,i+1)操作一次就变成1了。
总次数为n-7+5*2=n+3次。
Code
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
| ##pragma GCC optimize(2)
##include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;
##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
void solve()
{
int _; cin >> _;
while(_--) {
int n; cin >> n;
vector<pair<int, int> > v, x(20);
vector<int> a(10);
int t = n;
int k = 0;
while(t > 2) {
a[++k] = t;
t = (int) (ceil(sqrt(t)));
}
t = k;
for(int i = 3;i <= n; i++) {
if(i == a[t]) {
x[t * 2] = {i, (int)(ceil(sqrt(i)))};
x[t * 2 - 1] = {i, (int)(ceil(sqrt(i)))};
t--;
}
else v.push_back({i, i + 1});
}
cout << v.size() + k * 2 << endl;
for(auto i : v) {
cout << i.first << " " << i.second << endl;
}
for(int i = 1;i <= 2 * k; i++) {
cout << x[i].first << " " << x[i].second << endl;
}
}
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/12/29/educational-codeforces-round-101-rated-for-div-2-d/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！