CF1032C Playing Piano - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)。
题目大意是：能否构造一个长度为 \(n\) 的值域为 \([1, 5]\) 的整数序列，使得相邻两个数之间的大小关系满足给定的大小关系。
给定的大小关系可能是大于，小于和不等于。
CF 官方给的 dp 做法是假的。实际上只需要一个橙色难度的简单构造。题解区唯一的一篇构造写的不够清楚而且代码比较难懂（还是 Go 语言的），这里我贡献一篇。
把序列拆分为连续大于段，连续小于段和连续不等段。
贪心地，连续大于段从 \(5\) 开始，填 \((5, 4, 3, 2, 1)\)。连续小于段从 \(1\) 开始，填 \((1, 2, 3, 4, 5)\)。填不下去了就是连续长度大于 \(5\) 了，报个无解。
连续不等段直接在 \(2, 3\) 之间振荡。\(3, 4\) 之间，\(2, 4\) 之间也可以，但不要涉及到 \(1, 5\)，看后面就知道原因了。
然后考虑一下段和段的边界。
先小于后大于 \(a < b < c > d > e\)。发现 \(c\) 明显应该填 \(5\)，也就是跟随后面那个段，因为要让后面尽可能连续下去。按照上面的贪心填法对应的构造方案是 \((1, 2, 5, 4, 3)\)。
先大于后小于同理，跟后面。
先不等后小于 \(a \ne b \ne c < d < e\)。会发现 \(c\) 应该填 \(1\) 最好，也是跟随后面。这里就是为什么不等段的振荡最好不涉及 \(1\) 和 \(5\)，否则可能影响边界。
先不等后大于同理，跟后面。
先小于后不等 \(a < b < c \ne d \ne e\)，这个 \(c\) 可以跟前面。
先大于后不等同理，跟前面。
但是这样会有一个问题：\(\cdots > a > b > c \ne d < e < f < \cdots\)。\(d\) 应该怎么填？如果 \(c\) 没填 \(1\) 自然老办法 \(d\) 填 \(1\)，如果 \(c\) 填了 \(1\) 呢？
不难发现，此时 \(d\) 只能填 \(2\)。因为根据我们的贪心想法，\(c\) 此时都为 \(1\) 了就说明前面必有一段 \(5 > 4 > 3 >2 >1\) 的链，将 \(c\) 修改为 \(2\) 前面就会不合法。大小于号翻过来后情况也是类似的。
注意 \(n = 1\) 可能需要特判，根据你咋写的。
复杂度 \(\Theta(n)\)。
/*
* @Author: crab-in-the-northeast
* @Date: 2023-01-07 01:36:54
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2023-01-07 02:23:00
*/
#include <bits/stdc++.h>
inline int read() {
int x = 0;
bool f = true;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-')
f = false;
for (; isdigit(ch); ch = getchar())
x = (x << 1) + (x << 3) + ch - '0';
return f ? x : (~(x - 1));
}
const int maxn = (int)1e5 + 5;
int a[maxn];
char b[maxn]; // b[i] 表示 b[i] 和 b[i + 1] 的大小关系
int main() {
int n = read();
if (n == 1) {
puts("1");
return 0;
}
for (int i = 1; i <= n; ++i)
a[i] = read();
for (int i = 1; i < n; ++i) {
if (a[i] < a[i + 1])
b[i] = '<';
else if (a[i] > a[i + 1])
b[i] = '>';
else
b[i] = '!';
}
int lst = 1;
if (b[1] == '>')
lst = 5;
else if (b[1] == '!')
lst = 2;
std :: vector <int> ans = {lst};
for (int i = 2; i < n; ++i) {
int now;
char p = b[i - 1], q = b[i];
if (p == '<') {
if (lst == 5)
break;
now = lst + 1;
if (q == '>')
now = 5;
} else if (p == '>') {
if (lst == 1)
break;
now = lst - 1;
if (q == '<')
now = 1;
} else if (p == '!') {
if (q == '!') {
now = 3;
if (lst == 3)
now = 2;
} else if (q == '<') {
now = 1;
if (lst == 1)
now = 2;
} else if (q == '>') {
now = 5;
if (lst == 5)
now = 4;
}
}
ans.push_back(lst = now);
}
if (b[n - 1] == '<')
ans.push_back(5);
else if (b[n - 1] == '>')
ans.push_back(1);
else
ans.push_back(lst == 5 ? 4 : 5);
if ((int)ans.size() == n)
for (int x : ans)
printf("%d ", x);
else
printf("-1");
puts("");
return 0;
}