CF1620F 题解
GaryH
·
·
题解
CF1620F 题解
题意：
给定排列 p，要求拟定一个新序列 p'，满足：
-
- 构造无向图 G，其中 (i,j) 有边当且仅当 i<j,p'_i>p'_j，要求 G 是二分图。
请给出方案或报告没有方案。
做法：
首先注意到，一张图不是二分图，当且仅当其存在至少一个奇环，
故考虑什么情况图中存在奇环。
直接想似乎没什么思路，我们考虑这种特殊图的一个性质，即：
若图中存在奇环，当且仅当图中存在一个长为 3 的奇环。
怎么证明？我们考虑反证法，但我们先要说明一些东西。
虽然题意是无向图，但我们在接下来考虑问题的时候，可以将边定向，即：
若 i<j 且 p'_i>p'_j，则连一条 i\rightarrow j 的有向边。
我们先考虑三个点 i,j,k，若同时存在两条有向边 i\rightarrow j,j\rightarrow k，则等价于：
那么，我们开始反证，即若图中存在一个长度大于 $3$ 的奇环但不存在长度为 $3$ 的奇环，
那此时在奇环中，连接任意一点的两条边，
两条边要么同时是这个点的出边，要么同时是这个点的入边。
这样的话，任意点 $u$ 的出度减入度之差 $d_u$ 不是 $2$ 就是 $-2$，
则一个奇环上所有点的 $d$ 值之和必然不为零，因为有奇数个点，
而实际上一个奇环上的点的 $d$ 值之和显然必须为零，故产生矛盾。
故我们让图中不存在长为 $3$ 的奇环，就可以满足条件。
而一张图中不存在长为 $3$ 的奇环，当且仅当原序列 $p'$ 中不存在 $i<j<k$ 且 $p'_i>p'_j>p'_k$。
此时，我们考虑一个简单的 DP，即：
$f_{i,x,y}$ 为填了序列 $p'$ 的前 $i$ 个，此时序列所有数最大为 $x$，所有逆序对末尾数最大为 $y$，
这样能否不存在长为 $3$ 的奇环，若能则 $f_{i,x,y}=1$，否则 $f_{i,x,y}=0$。
这样是 $O(n^3)$ 的，显然过不去，而转移已经是 $O(1)$ 的，无法优化，故我们考虑优化状态。
我们发现，对于两个都已经构造前了 $i$ 位的序列 $p1,p2$，若两者前 $i$ 位的最大数都为 $x$，
设两者的逆序对末尾数最大值分别为 $y1,y2$，显然，在 $y1$ 和 $y2$ 中取小者对应的序列更有潜力，
或者，形式化的：不妨设 $y1>y2$，则任意一个长为 $n$ 的合法序列，
若其长为 $i$ 的前缀由 $p1$ 构成，则我们将前缀换成 $p2$ 后也一定合法。
同样的，对于一对固定的 $(i,y)$，显然 $x$ 越小序列越容易合法，就不过多赘述了。
那么，对于状态中一对固定的 $(i,x)$，我们只需要存储一个最小的可能 $y$ 即可，即 $f_{i,x}=y$。
当然，如果对于状态中一对固定的 $(i,x)$，其不存在任何一个可能的 $y$，我们就令 $f_{i,x}=INF$。
于是我们就将复杂度优化到了 $O(n^2)$，但还是过不去。
看上去似乎这个无法再进一步优化状态，我们尝试写下状态转移方程：
设 $z=\pm p_{i+1},f_{i,x}=y(z\geq y)$，则我们有：
1. $z<x\rightarrow f_{i+1,x}=z$；
2. $z\ge x\rightarrow f_{i+1,z}=y$。
我们惊讶地发现，转移后新的 $(x,y)$ 中至少有一个值等于 $z=\pm p_{i+1}$。
那么，我们就只需要记 $f_{i,0/1,0/1}$ 代表前 $i$ 位，第 $i$ 位填的值是正/负，其中 $x/y$ 等于 $\pm p_{i+1}$。
状态的转移和前面本质相同，我就不写了，不会可以看代码。
这样的复杂度就是 $O(n)$ 的了，也足以通过本题。
注意题中要求给出方案，故我们需要记录前驱。
**code**：
```
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;
const int N (1e6 + 10);
vector < int > ans;
int n, p[N], f[N][2][2];
struct Node { int i, j, k; } pre[N][2][2];
void work() {
cin >> n;
rep (i, 1, n) cin >> p[i];
rep (i, 0, n + 1) rep (j, 0, 1)
rep (k, 0, 1) f[i][j][k] = 2e9;
f[1][0][0] = f[1][1][0] = -2e9;
rep (i, 1, n - 1) rep (j, 0, 1) rep (k, 0, 1) {
int x, y, t = f[i][j][k];
if (!j && !k) x = -p[i], y = t;
if (!j && k) x = t, y = -p[i];
if (j && !k) x = p[i], y = t;
if (j && k) x = t, y = p[i];
Node nw = (Node) {i, j, k};
rep (sgn, 0, 1) {
int z = (sgn ? 1 : -1) * p[i + 1];
if (z < y) continue;
if (z < x) if (f[i + 1][sgn][1] > x)
f[i + 1][sgn][1] = x, pre[i + 1][sgn][1] = nw;
if (z >= x) if (f[i + 1][sgn][0] > y)
f[i + 1][sgn][0] = y, pre[i + 1][sgn][0] = nw;
}
}
rep (fj, 0, 1) rep (fk, 0, 1) {
int i = n, j = fj, k = fk;
if (f[i][j][k] < 2e9) {
ans.clear(), puts ("YES");
while (i >= 1) {
ans.pb (j ? p[i] : -p[i]);
Node nw = pre[i][j][k];
i = nw.i, j = nw.j, k = nw.k;
}
reverse (ans.begin(), ans.end());
for (int x : ans) printf ("%d ", x);
return puts (""), void();
}
}
puts ("NO");
}
int main() {
int tasks; cin >> tasks;
while (tasks--) work();
return 0;
}
```