UOI 2023 An Array And Addition Again

传送门：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,加油!!!