传送门

• 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

这场题目非常不错，有点 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 的位置，分情况讨论：
– 是否已经排序
– 是否再进行一次操作可以完成排序
– 否则进行一次操作，使得下标尽可能向右移，继续迭代

Posted by xiaodao
Category: 日常