AtCoder题面
Luogu题面
题目大意
给定一个正整数 ，要求构造一个序列。对于每一个在 到 之间的整数 ，序列中包含了 个，并且将该序列首尾相接拼成环后，相邻两项之差大于等于 小于等于 。
思路
突破口是关于相邻两项之差的约束条件。
（我一开始竟然只看见了“小于等于 ”，然后我构造出来的相邻两项就有相等的情况，还调了半天 qwq）
感觉上“大于等于 ”是在让我们 递增 或 递减，而“小于等于 ”则是给了我们一个 调整的空间。
但是由于要求“包含 个 ”，那么就不能只递增或者只递减，肯定是要 反复递增递减。
然后我就得到了一个 错误 的“图”（以 为例）：
1
2
3
4
5
6
| 6 6 6 6 6 6
5 5 5 5 5 5 5 5 5 5
4 4 4 4 4 4 4 4 4 4
3 3 3 3 3 3 3 3 3 3
2 2 2 2 2 2 2 2 2 2
1 1 1 1 1
|
（好像缩进有点问题……）
这很显然是 错误 的（其实当时就只是在脑子里想了一下，没画出来，但总是感觉哪里怪怪的，所以以后还是要勤动手啊……）
递增递减确实都考虑到了，但是数量却没有保证，那么下一步就考虑 先保证数量。
于是又得到了下面的图（以 和 为例）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 6 6 6 6 6 6
5 5 5 5 5
4 4 4 4
3 3 3
2 2
1
7 7 7 7 7 7 7
6 6 6 6 6 6
5 5 5 5 5
4 4 4 4
3 3 3
2 2
1
|
很明显的是，数量肯定是对的，但是要怎么把这个“图”转换成序列呢？
还是考虑 反复递增递减，然后可以发现 从左上到下方再到右上，这就是一个 先递减后递增 的过程。
然后就进行尝试，把整个图拆成下面的样子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 6 6 6 6 6 6
5 5 5 5 5
4 4 4 4
3 3 3
2 2
1
7 7 7 7 7 7 7
6 6 6 6 6 6
5 5 5 5 5
4 4 4 4
3 3 3
2 2
1
|
可以发现对于 奇偶不同 的 拆出来的图的样子是不太一样的，这个后面再说。
这时，感觉上拆开后的图好像差不多就可以了。
那到底差哪里了呢？
就是每一个部分的 连接处，如上图中就会有两个 挨着和两个 挨着的情况，这个时候就要用到出题人给的 调整的空间 了。
我们可以把一个“部分”中的某个数放到外面，具体地说，以“部分”“”为例，我们可以把两个 （或 ）放到两个 的外侧。
这样做首先可以保证这个“部分”的中间几个位置是不破坏约束条件的，因为本身是递增或递减的，拿走其中一个之后，最多相差 。如“”拿走其中的 之后， 和 之间也就差 。
但是还有一个地方没有保证，那就是这个“部分”的两头。
还是以序列“”为例，如果把 放在两头，那么 和 只差 ，满足约束条件，但要是把 拿出来放在两头，那么 和 相差 ，就不满足约束条件了。
同样的，把 拿出来也是满足条件的，但此处为了 简便，我们直接拿相差 的即可。
接下来讲一下“简便”的含义：
我们可以发现，每一个“部分”原始的两头都是 ，所以我们把如“”的序列加进去后只需进行两次“交换”：首项和第二项、倒数第二项和末项。
但是这里还有一个问题，那就是如果每一部分的两头都进行了这样的“交换”，就会“负负得正”，就变成了两个 挨着，那么我们可以借用“拼图”的思想，就是一头设计成凸出去的，另一头是凹进来的。具体到这个题上就是，一头“交换”，另一头不“交换”。
但是如果都这样设计也不行，因为在枚举到最后的“部分”的时候，如果规模太小，就进行不了“交换”。
例如“”这个“部分”，如果进行了“交换”，那么两个 就会挨着。还有“”这个“部分”，只有一个元素，无法进行“交换”。（ 的奇偶不同）那么像这样的情况，两头的值就必须都是 。而与此类“部分”相接的“部分”是倒数第二个“部分”和第一个“部分”，那么倒数第二个“部分”的后面一头和第一个“部分”的前面一头就要设计成“交换”后的。
那么我们就可以把每一个“部分”的后面一头“交换”，前面一头不变（第一个“部分”两头都要“交换”）。
再讲一个实现上的细节。
怎样把一个“部分”加到要输出的数组里呢？
可以发现，每次都是从 到一个“顶点”，再从“顶点”到 。比如“”这个序列中的“顶点”就是 。
那么我们就可以对“顶点”进行“监视”。
可以发现每个“顶点”都比前一个“部分”的“顶点”大 ，但是在实现的时候不要直接写 +=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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <bits/stdc++.h>
using namespace std;
int read() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return x * w;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) write(x / 10);
putchar(x % 10 ^ '0');
}
const int N = 500505;
int a[N];
signed main() {
int n = read();
int top = 1;
int idx;
for (int i = n; i >= top; i -- ) {
a[ ++ idx] = i;
}
swap(a[1], a[2]);
top ++ ;
for (int i = top; i <= n; i ++ ) {
a[ ++ idx] = i;
}
swap(a[idx], a[idx - 1]);
top ++ ;
while (n - top > 1) {
for (int i = n; i >= top; i -- ) {
a[ ++ idx] = i;
}
top ++ ;
for (int i = top; i <= n; i ++ ) {
a[ ++ idx] = i;
}
swap(a[idx], a[idx - 1]);
top ++ ;
}
if (n - top == 1) {
a[ ++ idx] = n;
a[ ++ idx] = n - 1;
a[ ++ idx] = n;
} else {
a[ ++ idx] = n;
}
for (int i = 1; i <= idx; i ++ ) write(a[i]), putchar(' ');
puts("");
return 0;
}
|
复杂度是 的，轻松过。
