ACM ICPC World Finals 2013

!!! WTF?

Problem A

Upsolved by zerol. (-1)

题意：有若干个方块，方块四周有极性。方块可以翻转旋转，问能否拼出一个无限大的方块。

题解：某人读错题（没有翻转，变成了神题）。某人建错图（无向有向之争，能否判环之争）。纠结的恶果是：没做出来。如果最后思路清晰，5 分钟就能写完。

zerol：这锅我背了。

Problem D

Solved by ultmaster. 02:47 (+2)

题意：给定一个数的所有质因子的排列数目，要求求出最小的数。

题解：简单暴搜题。但是某咸鱼费了好大力气，在队友的帮助下才写完。写完又挣扎了一会 long long 爆炸的问题。然后艰难地过了。

Problem F

Solved by ultmaster. 00:33 (+)

题意：把一个序列分成 $2k$ 组，然后每组里取出最小的，进行两两配对。使得差的最大值尽可能小。

题解：二分答案，顺序 check。

Problem H

Upsolved by ultmaster.

题意：大套娃套小套娃。只能相邻的套。如果相邻的套不起来可能要拆开套。最后要求套成若干个 $1$ 到 $m$ 的。问最小步数。

题解：套路区间 DP 题。然而想都没想。

$f(i,j)$ 表示把 $i$ 到 $j$ 合并成一个的代价。显然有重复的不行。然后枚举中间位置 $k$，两边分开算即可。把能预处理的东西都预处理，预处理暴力一点也没关系。最后还要把算好的 $f(i,j)$ 一个一个拼装起来。不过似乎也难度不大。过了样例以后就一发过了。

Problem J

Upsolved by kblack & zerol. (-5)

题意：求多边形和半圆面积交。

题解：切出圆内部的部分，通过线段进出圆的方向，记录每个弓形是否需要被计入面积，然后正常的求多边形面积即可。记得改 EPS。