某岛

… : "…アッカリ~ン . .. . " .. .
August 18, 2012

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
枚举 + 模拟。。