某島

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

顯然可以網路流。注意到每個城市出發和到達最多一個航班,所以進一步簡化,匹配就可以了。