传送门：https://uoi2023-2.eolymp.io/problems/3
题目大纲：
给予一个整数 n 。 (n<=1e18)
你现在有一个数组 a, a 的所有号码为 0 除了 a[100] 为 1
你需要给一些指令, 每一个指令需要一个整数 s , 他会进行 d[s]+=d[s+1]
你需要找到一串指令使得 d[1]=n
输出指令的长度： 然后每个指令的 s 。
看到题目感觉一定是 log2(n)。因此考虑一直除二。
写个样例：n=140
140,70,35,17,8,4,2,1
很容易看到他一定是会到 1 的， 但是当我们看到奇数的时候要加 1 ?
所以我们本来的数组应为：
0,0,1,1,0,0,0,0 （1为特例，就算他是奇数也不需要）
但是怎么可能？ 最后一个1 应该从后面来的。
考虑整个数组都为1先
1,1,1,1,1,1,1,1
但是我们现在的除就不是 floor( x / 2 ) 了 而是 floor( ( x - 1 ) / 2)
考虑 140 为样例： 140=1+2*x, x=(140-1)/2=69 以此类推
140,69,34,16,7,3,1
那么我们就可以看到现在偶数需要+2, 奇数需要+1
2,1,2,1,1,1
代码如下：
1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 void solve() { 5 int n; cin >> n; 6 auto ans = [&](vector<int> ops) { 7 cout << ops.size() << '\n'; 8 for (int i = 0; i < (int)ops.size(); i++) cout << ops[i] << ' '; 9 cout << '\n'; 10 }; 11 vector<int> v(1, n), ops, d(101); d[100] = 1; 12 while (v.back() > 1) v.push_back((v.back() - 1) / 2); 13 for (int i = 99; i >= 1; i--) { 14 ops.push_back(i); d[i] += d[i + 1]; 15 } 16 for (int i = 0; i < (int)v.size() - 1; i++) { 17 if (v[i] % 2 == 0) { 18 ops.push_back(i + 1); d[i + 1] += d[i + 2]; 19 } 20 } 21 if (d[1] == n) { ans(ops); return; } 22 for (int i = v.size() - 1; i >= 1; i--) { 23 if (d[i] == v[i - 1]) continue; 24 ops.push_back(i); 25 ops.push_back(i); 26 } 27 ans(ops); 28 } 29 signed main() { 30 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 31 int tt, g; cin >> tt >> g; 32 while (tt--) solve(); 33 } 34 //nyl,加油!!!