2014 ACM-ICPC World Finals

听说五题可以上台领奖，恭喜 kblack。

Problem A

Unsolved.

Problem B

Upsolved by ultmaster.

题意：有 $n$ 种家具，每种家具有无限个。对于离散型的家具，每买一个带来的收益是一个等差数列；对于连续型的家具，可以买实数个。求最大收益。

题解：显然连续的和离散的分开求。然后合并起来。

• 连续：每次拿当前收益最大的，一直取到它降到和下一个相同。相同收益的可以合并起来，注意 0 的情况。
• 离散：重量使用模意义下分别维护凸壳来解决。列出式子来之后注意到是维护上凸壳，斜率为负（维护双端队列）。

细节挺多的，比较容易写错。和北京的家具题的区别在于每种家具有无限个。

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.