某島

… : "…アッカリ~ン . .. . " .. .
October 6, 2021

ICPC World Final 2020

傳送門

提交地址

因為疫情原因,今年去年的 Final Adpot 了「寧理規則」,變成了 15 個題三人三機。。。
預感趣味性和策略性可能會降低好多,雖然 CF 上有紅名大佬出來倡議反對這個規則,不過好像並不會改變什麼。。。(BTW,結果這個題主本屆 World Final 直接 win 了,可見他是真的關心這個比賽。。。)

事實也確實如此,感覺題目難度也比前幾天的莫斯科邀請賽降低了好多。。變成手速 round 了。。。
(據說這場 8 個題才算簽到。。可怕。。。)

以下按照我認為的難度排序。。。

Problem C. Domes

半平面交模板題。

Problem E. Landscape Generator

區間加減等差數列,單點詢問。
顯然可以線段樹,不過這種只在最後詢問一次的話用差分+部分和技巧就可以,簽到題!

Problem G. Opportunity Cost

假設沒有 max 0 這個操作,那麼可以 O(n) 掃過去。
進一步觀察,我們枚舉 shadow 掉哪些維即可,最大值不變。

Problem O. Which Planet is This?!

分別處理每個緯度,差分之後轉換成字元串問題,KMP 出所有匹配位置得到所有合法位移。
判斷每個緯度的合法位移交集是否為空即可,這種看起來時幾何的題最後發現可以用字元串演算法通過的題目還是很有趣的,參見 HDU 3918。。

Problem D. Gene Folding

我們可以 dp 出 i 位置向左和向右最大可以摺疊掉多少位置。
(就像是我們在最優子矩形里,用單調棧處理出以 i 位置為最小值,向左和向右最遠可以延伸到哪裡一樣)
這個需要我們先預處理出每個位置的迴文半徑,Manacher 或者 字元串 hash 均可。

Problem I. Quests

問題等價於求出最多有多少 xp 可以獲得 bonus。
由於值域不大,考慮暴力 01 背包。

我們只需要對每個物品,預處理出如果要取到它的話,最大可能的背包容量是多少。
我們根據這個值從小到大依次處理每個物品即可。

Problem F. Ley Lines

平面上有 n 個點,用一條寬度為 r 的直線,最多可以覆蓋多少點。
可以 O(n2) 枚舉直線,然後再對每個點求出合法偏移量的區間,對每個區間分成 +1 -1 兩個事件,排序後掃一遍即可,不過複雜度 O(n3),
進一步考慮,一定存在一組解,使得某個點在筆刷的邊界上,因此我們 O(n) 枚舉中心,然後用類似 Master Spark 里極角排序的方法處理即可。

感覺這裡需要畫圖。

以當前枚舉的旋轉中心為 O,目標點為 P,向量 OP 的長度為 d,筆刷半徑為 r。
初始角度 為 -PI 時,筆刷下邊界在 x 軸,設當前向量的輻角為 alpha,中間三角形的夾角為 beta。
那麼 P 點會被覆蓋的區間為 [alpha, alpha+beta] 和 [alpha+PI-beta, alpha+PI]。
如果 d <= r,那麼 beta 不存在,只需要考慮 [alpha, alpha+PI]。

然後因為對稱性,我們其實只需要掃半個圓,比如 [0, PI] 這個區間,所以在這個題里不拆環也是 ok 的。。。
最後主程序非常短 …

const int N = int(3e3) + 9;
Po P[N];
int n, r;

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, r); REP(i, n) P[i].in();

    int z = 2; REP(a, n) {
        vector<pair<DB, int>> E;
        int s = 1; REP(b, n) if (b != a){
            Po v = P[b] - P[a]; DB d = v.len();
            DB a = v.arg();
            E.PB({a, 1}); E.PB({a + PI, -1});
            if (d > r) {
                DB b = asin(r/d);
                E.PB({a + b, -1});
                E.PB({a + PI - b, 1});
            }
        }
        SRT(E); for (auto e: E) checkMax(z, s += e.se);
    }
    cout << z << endl;
}

Problem J. ‘S No Problem

樹形 DP,比 我出的那個題 簡單多了。
顯然如果只有一條路徑的話是個經典題,不妨討論,如果有 k 條路徑的話可以做嗎?
我們發現其實是個樹上背包。
dp[u][2][5] 表示當前節點的奇偶性,以及子樹中一共出現了多少路徑的端點,簡單轉移即可。

Problem B. The Cost of Speed Limits

給定一個邊權無向圖,對於某個節點,如果其相鄰的邊里有權值不一樣的邊,
那麼需要在這個點上對每一條出發的邊都設置一個限速標牌。

每個限速標牌的代價為 c,增加某條邊的單位權值的代價為 1。
問如何修改這張圖,使得總代價最少。

另一個樹形 dp!
題目其實還不錯,但是數據範圍非常迷,貌似大家都是 O(n2) 爆過去的。。。
總之這個題爭議比較大,參見 maroonrk 的吐槽

————————

dp[u][i] 表示將這個節點相鄰的邊全部修改成 i 的代價,
sign[u] 表示所有相鄰節點防止限速牌的代價,
best[u] 表示所有 dp[u] 和 sign[u] 的最小值。

那麼轉移方程有:
sign[u] = c*SZ(adj[u]) + \sum best[v]
dp[u][i] = \sum min(sign[v] + 修改到 v 的邊權, dp[v][i]) + 修改到 p 的邊權

離散化掉第二維,輸出 best[1] 即可,複雜度 O(n2),注意常數可過。

Problem A. Cardiology

貌似是簡單題,但是我讀不懂題意。。。。

Problem M. Trailing Digits

給定 b,d,a,求 nb <= a,使得 nb 末尾的數字 d 最多。

不會。。。

Problem H. QC QC

互動式問題,非常經典的測謊問題。
有 n 個人,其中一些人是好人,一些人是壞人,並且每個人都知道所有人分別是好人還是壞人。
你可以詢問某個人,另一個人是好人還是壞人,好人總是會告訴你真實信息,壞人可以說謊。
用最少的詢問區分好人和壞人。

atcoder 也出過一個版本
那個題里 n <= 2000,你至多可以詢問 2n 次。
這個題里,n <= 100,你至多可以詢問 12 輪,每輪次,你需要問所有人一次問題。。。

首先如果壞人 >= 好人那麼無解,因為壞人可以綁票偽裝成好人然後反咬。
否則肯定有解,因為如果對所有人問一次同一個人,如果有超過半數的人認為它是好人,那麼它一定是好人。
接著問這個好人就可以了。不過這樣詢問次數可能是 n2/2 次。

怎麼樣在 O(n) 次詢問里找到一個好人呢。。。
有一個非常 nice 的方法,
首先這個村子裡每個村民都是預言家,
當 A 說 B 是狼人時,只有下面三種情況。
1. 真預言家報查殺。
2. 狼人悍跳誣陷預言家。
3. 狼人出賣自己的狼同伴以做高自己的身份。

不管怎麼說,A、B 不會同時為好人。
那麼我們只要用棧構造一條詢問鏈,按照順序用棧頂的元素詢問每個人,
如果詢問為假,就彈出棧頂,否則就 push 一個新人。
那麼 n-1 次詢問過後,

假設當前棧中某個人是好人,那麼它詢問鏈後面的每個人也都是好人,
所以棧頂的那個人一定場上身份最高的。
有因為在有解的情況下,此時棧中一定至少有一個人是好人,所以棧頂的那個人一定是好人。
這樣一共 2(n-1) 次詢問就可以知道所有的結果了。

用類似的方法可以解決 WF 的這個題。

Problem N. What’s Our Vector, Victor?