2011 ACM-ICPC World Finals

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Solved by zerol. 00:46 (+)

签到

题意：图像识别

题解：数内部联通块个数

Problem D

Unsolved.

Problem E

Solved by ultmaster. 03:53 (+)

曼哈顿距离转切比雪夫距离签到。

U: 题目本身非常傻逼，没什么好说的。但是：

• 我读错了题。两次。
• kblack 搞出了某些非常玄幻的做法，导致一度不会做这个题。
• 好在稳健的 Z 给出了这题是签到题的指导性意见，然后就过了。

Problem F

Unsolved. (-3)

Problem G

Unsolved.

Problem H

Solved by zerol. 04:39 (+1)

题意：给一个连通无向图，要求选择一些点，使得删除图中任意一个点之后，所有点都可以由点集中的某个点到达。

题解：考虑每个点双，如果这个点双上有两个及以上割点，那么这个点双内不用选任何点。否则如果只有一个割点，那么在除了那个割点的其他点中随便选一个。如果整个图本身就是一个点双那么就特判。

Z: 解法有些魔幻，评测机表示对。这个算法是不断找反例，打补丁之后得出的，似乎，还挺逼真的。

Problem I

Solved by kblack. 04:06 (+1)

Problem J

Solved by ultmaster. 02:53 (+3)

题意：300 * 1000000 的 01 背包，求方案，要物品数量尽量少，同时字典序最大。

题解：发明了若干种假算法之后，直接开了个 300*1000000 的数组存储所有点的最短路径。

Problem K

Solved by ultmaster. 01:28 (+)

题意：求一个最小的间距使得多边形刚好能卡过。

题解：求完凸包，旋转卡壳。但是数据范围太小了根本不需要。