传送门
- https://codeforces.com/contest/1693
- https://www.bilibili.com/video/BV18Y411T71q
- https://www.acfun.cn/v/ac35355359_3
- https://zhuanlan.zhihu.com/p/530668156
- https://zhuanlan.zhihu.com/p/529953575
Table of Contents
这场题目非常不错，有点 atc 的感觉了 …
Problem B. Fake Plastic Trees
题意：给定一棵有根树，每一个节点有一个区间 l[i], r[i]。每次操作可以选择从根出发的路径，沿着路径上的每个点增加一个数，满足增加的数组成的序列非递减，
问至少多少次操作，能够满足每个节点的值都在其给定的区间里。
题解：树 DP
先弱化问题，假设 l[i] = r[i]。
设 dp[u] 表示以 u 为根节点的子树都满足条件时，至少需要多少次操作。
那么有 dp[u] = \sum dp[v] + (\sum r[v] < r[u])。
回到原问题，我们 dp 过程中贪心的让每个节点的标号尽可能大即可。
const int N = int(2e5) + 9;
VI adj[N]; LL l[N], r[N];
int n, z;
void dfs(int u) {
LL s = 0; for (int v: adj[u]) dfs(v), s += r[v];
if (s < l[u]) ++z;
else checkMin(r[u], s);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
Rush {
RD(n); REP_1(i, n) adj[i].clear();
FOR_1(i, 2, n) adj[RD()].PB(i);
REP_1(i, n) RD(l[i],r[i]);
z = 0; dfs(1);
cout << z << endl;
}
}
Problem C. Keshi in Search of AmShZ
Problem D. Decinc Dividing
称一个数组满足 DecInc，如果它可以由一个递减和一个递增序列构成（可为空）。
现给定一个排列 P，问它有多少连续子序列满足 DecInc。
这个 DP 我觉得挺难的。。。
const int N = int(2e5) + 9;
int a[N], f[N], g[N], n;
// f_i, in inc, max dec
// g_i, in dec, min inc
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n); REP(i, n) RD(a[i]);
LL z = 0; int p = n;
DWN(i, n, 0) {
f[i] = n+1; g[i] = 0;
FOR(j, i+1, n) {
int fj = 0, gj = n+1;
if (a[j-1] < a[j]) checkMax(fj, f[j-1]);
if (g[j-1] < a[j]) checkMax(fj, a[j-1]);
if (a[j-1] > a[j]) checkMin(gj, g[j-1]);
if (f[j-1] > a[j]) checkMin(gj, a[j-1]);
if (fj == f[j] && gj == g[j]) break;
f[j] = fj; g[j] = gj;
if (fj == 0 && gj == n+1) {
p = j;
break;
}
}
z += p-i;
}
cout << z << endl;
}
Problem E. Outermost Maximums
题意：给定一个长度为 n+2 的数组，设 a[0] = a[n+1] = 0。每一步你可以：
– 将最左边的最大值修改为它左边的次大值。
– 将最右边的最大值修改为它右边的次大值。
问至少多少次操作，可以让数组全部变为 0。
个人觉得这个题非常优雅。。。
官方题解 没看懂。。评论区里 Endagorion 的题解 换了种说法，和 官方题解 等价，还是不太好懂。。。
但是官方题解在最后的链接里 推荐了一份来自 ecnerwala 的题解，这个题解和上面的做法非常不同，非常容易丽洁！
下面我们来讲一下这个。。。
首先这个 E 题是一个多阶段决策问题，对于这类问题通常的做法是 dp，但是我们很难设计状态进行 dp。。。
对于多阶段决策问题，当然还有一个可能的做法就是贪心，然后这个题有一个结论：对于当前决策的数，每次都找两边较小的数进行转移。（虽然我觉得，这个结论也不是很显然。。）
考虑构造解，我们发现光有这个结论还是不够，考虑重复数字。。可能在某个阶段，左右两边的数大小一样，这样我们又不知道怎么转移了。。官方题解是先弱化问题，只考虑排列。。但是我觉得这步弱化收效甚微。。
首先修改数字的过程本身就会出现重复数字，而且最后还是要回来处理重复数字的问题。。并不是很直观。。
这份题解则提供了一种非常 nice 的思路。。而且重复数字对这个做法完全不影响。。。
方法就是延迟处理。。既然当前阶段不好做判断，那么不如先打个 ? 标记。。。
我们按照从大到小的顺序处理所有的数字（我觉得这比题解从左向右的顺序要好得多！）。
那么当处理到一个数字时，考察当前轮次，这些相同的数字所形成的区间，
所有在这个区间左侧的 ？都置为 <。（因为后续肯定有更小的数出现在它们的左侧）
所有在这个区间右侧的 ？都置为 >。
重合的部分依然是 ?。（这些位置当前轮次的决策不影响结果）
以样例 2 那个排列为例。。。过程就是：
//13542 //..?.. +1 //..<?. +1 //.??>. +2 //.<<?? +2 //???>> +3
每个位置被标记成 ? 都会对答案带来 +1 的贡献，而且这些 ? 标记每个轮次都构成一个连续的区间。。。只要开个树状数组把处理过的位置，每次单点 +1，并维护当前区间的位置，每次加上区间和就可以了。。Orz。。
代码很短。。。
Problem F. I Might Be Wrong
题意
给定一个 01 序列，每次操作可以选择一个子区间进行排序，代价是这个区间 0 和 1 数量的差再 + 1。
问最少多少代价完成排序。
题解
结论：只需若干次代价为 1 的操作。
做法：
只考虑 0 比 1 数量多的情况，用一个下标维护当前最左侧 1 的位置，分情况讨论：
– 是否已经排序
– 是否再进行一次操作可以完成排序
– 否则进行一次操作，使得下标尽可能向右移，继续迭代
