https://codeforces.com/contest/1922/problem/E
题目大意
给定 $x \ (2 \le x \le 10^{18})$ 构造出一个不超过 $200$ 长的有刚好 $x$ 个严格上升子序列的数组，数组中元素 $a_i$ 满足 $-10^9 \le a_i \le 10^9$。（包括空串）
简要题解
注意到我们很容易构造出两组完全无关的子数组。如我们把 $[x + 1, y]$ 和 $[1, x]$ 值域的数组拼起来，显然最后的结果是 $ans_1 + ans_2 - 1$（都有空数组，子序列不会跨域两段）。
我们总可以先从 $x$ 中减掉一些较大的值，之后在序列 $a$ 中增加一些单个的值，来修正最后的差的量。因此我们只需找到一些删掉较大值高效的方法。
容易发现 $1, 2, 3, \cdots, n$ 可以构成 $2 ^ n - 1$ 个非空子序列。而每次减掉最大的 $2 ^ n - 1$ 一定可以使数字 $x$ 的最高位变为 $0$，也就是说我们可以通过最多 $60$ 个这样的独立序列将 $x$ 变为 $0$。
但是这样还是太多了 $(60 + 1) * 60 / 2 > 1800$ 项，还是太多了（虽然这个似乎是跑不满，但是实际上很容易就超 $200$ 了）。
const int MB = 60;
void solve() {
LL m; cin >> m; m--;
vector<int> ans;
int cur = 1;
for (int i = MB; i > 0; i--) {
while (m >= ((1LL << i) - 1)) {
m -= ((1LL << i) - 1);
for (int j = 0; j < i; j++) {
ans.push_back(cur + i - j);
}
cur += i;
}
}
reverse(ans.begin(), ans.end());
int n = ans.size();
cout << n << '\n';
for (int i = 0; i < n; i++) {
cout << ans[i] << (" \n"[i == n - 1]);
}
}
于是我们想如何更高效的利用刚才减掉 $2^n - 1$ 的序列。
例如 $1, 2, 3, 4, 5$，我们注意到如果我们加入 $6$ -> $1, 2, 3, 4, 6, 5$ 则 $6$ 结尾的上升子序列与 $5$ 结尾的一样多且不会增加 $5$ 结尾的串，因此我们在这个最大 $2^n - 1$ 的基础上可以进一步的减掉一些 $2 ^ i$。而每次只需增加一个数。这样我们最多只需要用 $60 + 60$ 个数即可。
（代码比较丑，其实没必要合并情况，而且不合并可能会写的清晰很多。）
复杂度
$T$：$O(ans)$
$S$：$O(ans)$ 也可以 $O(1)$。
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
/*
1 -> 1
1 2 -> 3
1 2 3 -> 7
*/
const int MB = 60;
void solve() {
LL m; cin >> m; m--;
vector<int> ans;
int cur = 1;
int f = 1, ff = 0;
for (int i = MB; i > 0; i--) {
while (m >= ((1LL << i) - f)) {
// cerr << m << ' ' << i << ' ' << f << ' ' << ((1LL << i) - f) << endl;
m -= ((1LL << i) - f);
if (!f) {
ans.push_back(cur++);
} else {
f = 0;
ans.push_back(i);
cur = i + 1;
}
}
if (!f) {
if (!ff) ff = 1;
else ans.push_back(i);
}
}
while (m--) {
ans.push_back(cur++);
}
reverse(ans.begin(), ans.end());
int n = ans.size();
cout << n << '\n';
for (int i = 0; i < n; i++) {
cout << ans[i] << (" \n"[i == n - 1]);
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
标答做法
标答的做法看起来更好一些。
对于一个序列，最后加入比所有元素都大的元素会使方案数 $\times 2$。因为每种方案都可以变为选与不选最后元素的两种。
最后加入比所有元素都小的元素可以使方案数 $+1$。因为只会加入一种只包含新加元素的序列。
#include <bits/stdc++.h>
using namespace std;
vector<int> f(long long x) {
vector<int> res;
if (x == 2) {
res.push_back(0);
} else if (x & 1) {
res = f(x - 1);
res.push_back(*min_element(res.begin(), res.end()) - 1);
} else {
res = f(x / 2);
res.push_back(*max_element(res.begin(), res.end()) + 1);
}
return res;
}
int main() {
int t;
cin >> t;
while (t--) {
long long x;
cin >> x;
auto ans = f(x);
cout << ans.size() << '\n';
for (int i : ans) cout << i << ' ';
cout << '\n';
}
}
Next: [CF] F. Replace on Segment - Educational Codeforces Round 161 (Rated for Div. 2)