某岛

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

Andrew Stankevich Contest 13

https://codeforces.com/gym/100216

Problem A. Generalized Assignment

给定一个 \(n\times n \) 的矩阵,要求从中选取一些数字,使得每行每列恰好选择了 k 个,最小化这些数字的和。
k = 1 的话就是二分图最大权匹配,所以可以直接上费用流模板。不知道存不存在更好解法。

Problem B. Bandits

https://en.wikipedia.org/wiki/Pirate_game
海盗分金。

Problem C. Matrix Game

二分答案 + 高斯消元判定。

Problem D. Paper Mosaic

给定 n 个多边形(边数范围 3-6),保证每个多边形的外接圆半径相等。
问最少用几个这样的圆,可以切处所有的多边形。

计算几何 + 搜索剪枝?哇。。太神了不会。

Problem E. Shortest Path

带负权环的最短路,Bellman-Ford 模板题。

Problem F. Cutting Puzzle

问一个三边长分别为 \( a \times b\times c \) 的立方体,最少切多少刀,可以切成一堆 \(1\times 1\times 1\) 的单位矩形。
只考虑一维的话,答案显然是 \( \lceil log_2{n} \rceil \)。每个维度分开讨论,加起来即可。

Problem G. Pyraminx

一起来愉快的转魔方吧。。。

Problem H. Sand-Glass

简单几何。

Problem I. Solid Tilings

这不是那个经典问题吗。状态压缩 DP + 容斥原理。
参见 BZOJ 1435. [ZJOI2009]多米诺骨牌

Problem J. Lucky Tickets

显然可以网络流。注意到每个城市出发和到达最多一个航班,所以进一步简化,匹配就可以了。