某島

… : "…アッカリ~ン . .. . " .. .
April 8, 2020

Andrew Stankevich Contest 12

https://codeforces.com/gym/100215

Problem A. Brackets

從左到右掃,開個棧記錄最優解。

Problem B. Dividing a Chocolate

斐波那契數列?

Problem C. Thermal Death of the Universe

線段樹裸題,注意一下負數的 round 規則。

Problem D. Equations System

在多項式上跑擴展歐幾里得。

Problem E. Fool』s Game

Wiki, Hall’s marriage theorem

Problem F. Lottery

直接組合 DP 就好。。。轉移和 #27 的 G 幾乎一樣。

Problem G. Two Pipelines

簡單計算幾何,點到直線距離。貪心初始解調整一下即可。

Problem H. Manhattan Police

啊,曼哈頓。。。。

So now the wants to find out what minimal amount of money is needed to allow
people of Manhattan to get from any location to any other location turning only on crossings guarded by policemen.

這個題要把這個區域連通起來且代價最小,所以顯然是求最小生成樹,一共行+列個點,每個十字路口對應一條邊。
bfs() 一次把所有邊摳出來即可。

Problem I. Regular Words

三維版本的卡塔蘭序列!數據範圍很小,暴力組合 dp 即可。

Problem J. Greate Siberian Wall

最小外接三角形?這我哪會做啊。。

Problem K. Words Game

Dead-do