某島

… : "…アッカリ~ン . .. . " .. .
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 的位置,分情況討論:
– 是否已經排序
– 是否再進行一次操作可以完成排序
– 否則進行一次操作,使得下標儘可能向右移,繼續迭代