AtCoder AGC012C - Tautonym Puzzle

神仙构造题,做的构造题显然还不够多,只能想到一个长度为 $log^2 n$ 的构造方法,显然无法通过此题。

由于一定要两两成对才能给答案贡献,所以不妨将序列分成两个部分:前者是 $1 \sim m$ 的一个排列,后者就是 $1 \sim m$ 。

如此构造,对于左边的每一个上升子序列,我们都能在右边找到其对应的子串,从而贡献到答案中。

于是问题转化成了构造一个数列,使得其上升子序列的个数恰好等于 $n$ 。

倘若对于一个数列:

  1. 放最前面,上升子序列的个数 $+1$ ;
  2. 放最后面,上升子序列的个数 $\times 2 + 1$ 。

依据此规则构造即可。

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
#include <bits/stdc++.h>

typedef long long lint;

using namespace std;

lint n;

vector<int> opr;
deque<int> ans;

int main() {
scanf("%lld", &n);
while (n) {
if (n & 1) {
n = (n - 1) >> 1;
opr.push_back(1);
continue;
}
--n;
opr.push_back(0);
}
reverse(opr.begin(), opr.end());
for (int i = 0; i < (int)opr.size(); ++i)
if (!opr[i])
ans.push_front(i + 1);
else
ans.push_back(i + 1);
for (int i = 0; i < (int)opr.size(); ++i)
ans.push_back(i + 1);
printf("%d\n", (int)ans.size());
for (int i = 0; i < (int)ans.size(); ++i)
printf("%d ", ans[i]);
}