某島

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

Andrew Stankevich Contest 16

https://codeforces.com/gym/100220

Problem A. Cactusability

定義一個一棵樹的仙人掌力(Cactusability)為有多少種添加邊的方案,使得可以將其轉化為仙人掌(cactus)。
給定一棵樹,求其仙人掌力。

非常 nice 的樹形 DP。

Problem B. Darts

丟飛鏢,最後剩 n 分,列印所有的可以合法的湊成 n 分的投擲方案,要求最後一步必須落在 double 的格子里。
因為要輸出所有方案,所以直接 dfs() 即可。

Problem C. Domino in Casino

給定一個 nxm 的矩陣,你可以往其中放置 k 枚多米諾骨牌,每塊骨牌的得分是覆蓋的兩個格點的全值的乘積。
求一種覆蓋方案,最大化 k 枚骨牌的得分之和。

k 比較大,狀態壓縮 DP 會爆,所以用費用流。

Problem D. Love Is. . .

平面上兩個關鍵點 a, b,以及一堆矩形障礙。
問是否可以找到一點,同時看見 a, b。

一定存在解,使得目標點到關鍵點的連線,和障礙物相切。
暴力枚舉即可。多邊形也可以這麼做。

Problem E. Set Partitions

下一排列(next_permutation) 我們都會做,那麼下一划分(next_partition)呢?

Problem F. Pipe Layout

一條迴路問題,插頭 DP 基本功。

Problem G. Word Square

暴搜。

Problem H. Subword

It is interesting to note that for each word α and each word β there is such word γ equivalent to α that contains β as a subword. Your task in this problem is to find the shortest such word.

Problem I. HTML Table

模擬。

Problem J. Wheel of Fortune

???