某岛

… : "…アッカリ~ン . .. . " .. .
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

???