2014 ACM-ICPC World Finals

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Solved by kblack. 01:58 (+1)

题意：给一个大吊车，问吊着多少重量范围的时候是稳定的。

题解：只有最左最右的支点需要考虑，计算整个吊车的中心，分情况算一下力臂。

Problem D

Solved by zerol. 00:52 (+)

题意 & 题解：简单博弈 DP 签到。

Problem E

Solved by ultmaster. 04:13 (+5)

题意：无向图，对于一个点来说边循环有序。两个点等价当且仅当使用当前点和能走到的点和边的相对顺序不能将他们区分出来。求等价类。

题解：考虑一种哈希。如果能将一个点在 $k$ 跳内能达到的点的哈希做出来，那么就可以由 $k$ 推出 $k+1$。取 $k=100$ 来决定最后的答案。这里有几个问题：

• 环怎么解决：考虑字典序最小的一种位移方法。（刚开始直接找了最小的，就自闭了）
• 不仅出边的相对顺序相关，入边也是能看到顺序的（样例中就有），所以等于转移的时候要把入边左右的东西也要记下来。这要实际上是多一维状态，但是我打了个补丁。
• 补丁打得太多 TLE 了，优化了一下终于过了。

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Solved by ultmaster & zerol. 04:38 (+2)

题意：100 个点，每两个点有边当且仅当他们距离不超过 $d$。求最大团。

题解：枚举三个点。随机。贪心加。（据说不枚举三个点也能过啊？）

正解：枚举两个点，然后考虑交集内的情况。将距离超过 $d$ 的点相互连线，注意到是一个二分图。跑最大匹配求独立集即可。

Problem J

Unsolved.

Problem K

Solved by kblack. 01:01 (+2)

题意：k 个覆盖区间，求最少的区间数完整覆盖。

题解：先复制两倍，记 $jump_{i,j}$ 为从第 i 个区间开始，使用 $2^j$ 个区间最远覆盖后第一个没被覆盖的位置，然后枚举起点快乐倍增。

Problem L

Unsolved.