传送门
Problem D. Permutation Graph
给定一个排列 A ，排列的每个位置对应图中的一个节点，如果一段区间的端点上的数恰好等于这个区间的两组最值，那么我们就给这两个端点位置之间连一条无向边。
问从位置 1 出发到位置 n 的最短路。
这个题有两种做法。。做法 1。。
只要考察路径上的必经之点。。不失一般性，我们考察最小数。。。
假设位置为 p，那么最后的路径一定经过这个位置，因为 p 左右两边互不联通，那么我们显然可以用 p 进行递归，变成 [0, p] 和 [p, n) 两个子问题，且两边对称，我们考虑 [0, p] 这个子问题。
和开始的状态稍微不同，因为我们知道最右侧必然是最大数，因此这一次我们要找 [0, p] 区间的最小数，设位置为 x，那么再次分割成 [0, x] 和 [x, p] 两个子问题。
其中 [x, p] 最大值和最小值都在两侧，直接返回 1，而 [0, x] 是一个结构一样的子问题，于是结束，整个算法只需要预处理前缀和后缀的最小、最大值和对应下标即可，复杂度 O(n)，非常简单。
const int N = int(5e5) + 9;
int a[N], n; PII l[2][N], r[2][N];
int f(PII s[][N], bool b, int x) {
int p = s[b][x].se; if (x == p) return 0;
return 1 + f(s, b^1, p);
}
int gao() {
RD(n); REP(i, n) RD(a[i]);
l[0][0] = l[1][0] = {a[0], 0};
FOR(i, 1, n) {
l[0][i] = min(l[0][i-1], {a[i], i});
l[1][i] = max(l[1][i-1], {a[i], i});
}
r[0][n-1] = r[1][n-1] = {a[n-1], n-1};
DWN(i, n-1, 0) {
r[0][i] = min(r[0][i+1], {a[i], i});
r[1][i] = max(r[1][i+1], {a[i], i});
}
int p = l[0][n-1].se;
return f(l, 1, p) + f(r, 0, p);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
Rush OT(gao());
}
做法 2。。。做法 2 基于这样的结论，算法运行过程中，一定只需要不断往右走，不需要返回。。。
（这个结论实际上比做法 1 的结论弱。。。而且不用做法 1 的方式证。。也其实更麻烦。。。证明可以考察某个点 x，如果它向某个方向，例如右边，连接了 r0, r1, r2… 一组点，那么这些点一定构成一个递增或者递减序列。。因此自然 r 序列之间也互相连通，因此直接连到最远的点更优。）
无论如何，考虑这个做法。。从 1 出发，每次移动到最远的点。方法是，假设当前点为 x，那么考察 x 和 x+1 的大小关系，不失一般性，假设 a[x] < a[x+1]，那么我们先要找到后缀里的第一个比 a[x] 小的数，假设是 p，之后我们要找一个从 x 出发的，不超过位置 p 的连续递增序列所能到达的最远位置 r，x = r 并迭代到下一步即可。我们只需要预处理出，每个数向右，第一个小于它和第一个大于它的位置分别在哪里即可。..
这个是栈 or 笛卡尔树的基本操作。。。https://oi-wiki.org/ds/cartesian-tree/
2.1 栈版本
const int N = int(5e5) + 9;
int a[N], n; int r[2][N];
int gao() {
RD(n); REP(i, n) RD(a[i]);
stack<int> s[2];
a[n] = -INF; s[0].push(n);
a[n+1] = INF; s[1].push(n+1);
#define rr r[b][i]
DWN(i, n, 0) REP(b, 2) {
while ((a[i] < a[s[b].top()]) ^ b) s[b].pop();
rr = s[b].top(); s[b].push(i);
}
int z = 0;
for (int i=0;i!=n-1;++z) {
bool b = a[i] > a[i+1]; int r0 = rr; b ^= 1;
while (rr < n && rr < r0) i = rr;
}
return z;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
Rush OT(gao());
}
2.2 笛卡尔树
const int N = int(5e5) + 9;
int a[N], n; int r[2][N];
#define rr ::r[b][i]
namespace Cartesian_Tree{
int l[N], r[N], p[N];
int lc[N], rp[N];
#define lx l[x]
#define rx r[x]
#define ly l[y]
#define ry r[y]
void dfs(int x) {
if (!x) return;
rp[lx] = x; rp[rx] = rp[x];
dfs(lx); dfs(rx);
}
void build(bool b) {
a[0] = b ? n+1 : 0;
FOR_1(x, 0, n) rx = 0;
REP_1(x, n) {
int y = x-1; while ((a[y] > a[x]) ^ b) y = p[y];
p[lx = ry] = x; p[ry = x] = y;
}
rp[r[0]] = n+1; dfs(r[0]);
}
void init() {
REP(b, 2) {
build(b);
REP_1(i, n) rr = rp[i];
}
}
};
int gao() {
RD(n); REP_1(i, n) RD(a[i]);
Cartesian_Tree::init();
int z = 0;
for (int i=1;i!=n;++z) {
bool b = a[i] > a[i+1]; int r0 = rr; b ^= 1;
while (rr <= n && rr < r0) i = rr;
}
return z;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
Rush OT(gao());
}
Problem F. Tree Recovery
给一个 n <= 100 的树，告诉你所有点对最短路径之间的相等关系。
要求重构这颗树
感觉 TC 肯定出过类似的题？一般感觉这种题应该是复杂的构造？
不过这个题可以直接 O(n4) 暴力。。。我们以所有路径的相等关系建立并查集，如果存在解，那么树中的 n-1 边必然组成一个恰好 size = n-1 的连通块。
于是我们直接暴力合并，之后检查连通块是否恰好满足，
1. size = n-1
2. 构成一颗树
3. 满足初始条件
三组条件即可。
