某岛

… : "…アッカリ~ン . .. . " .. .
June 22, 2022

Codeforces Round #800 (Div.1)

传送门

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