Andrew Stankevich』s Contest #4

Overview:

。。#4 有 11 道題 ~~ 大部分都是經典題啦。。
。。其中 H (平鋪瓷磚) 和 J 題 (點集三角剖分)一定不能錯過。。。。。。

http://acm.zju.edu.cn/onlinejudge/searchProblem.do?contestId=1&titlefrom=0&authorfrom=0&sourcefrom=0&query=Andrew+Stankevich%27s+Contest+%234

Problem A. The Smart Bomb
給定三個圓心,求三個圓的半徑使其互不相交且面積和最大。
(。。yy 結論後解一次方程。。(兩兩相切。。

Problem B. I Just Called
模擬電話計費系統。
死做。

Problem C. Order-Preserving Codes
。裸。。)
最小代價子母樹 + 四邊形不等式

Problem D.
反素數。。
搜索。。

http://acm.buaa.edu.cn/contest/22/problem/E/
(注意 「Antiprime」 的漢語可能引起歧義。。Orz
http://en.wikipedia.org/wiki/Emirp
http://en.wikipedia.org/wiki/Antiprime
Highly composite numbers
http://oeis.org/A002182
Number of divisors of n-th highly composite number.
http://oeis.org/A002183

Problem E. Long Dominoes
SCDP

Problem F. The Magic Wheel
枚舉

Problem G. Cracking SSH
DP

Problem H. Periodic Tilings
搜索判定。。

Problem I. Trade
給定一個二分圖,要求一個最小的邊集,使得每個頂點至少被兩條邊覆蓋。
280ms+- 退流
1760ms 上下界網路流

Problem J. Counting Triangulations
。。三角剖分,記憶化搜索 + 凸包 Nice ( 1500 ms +-

Problem K. Unfair Contest
枚舉 + 模擬。。