2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest

Problem A

Solved by ultmaster. 02:54 (+)

题意：类似双塔问题。不过这是 三塔问题。

题解：跟双塔问题一样做，不过要记两维状态：第二座比第一座高多少，第三座比第二座高多少。不过状态可能高达 1E4 * 1E4，还要乘 400，难以接受。

zerol 提出可能中间状态也不会转移到太高的地方去，900 或者 1000 就够了。但是内存不够，没法回溯。

ultmaster 遂改成了 200，反复迭代 random_shuffle 跑到 4 秒退出。跑了很久 AC 了。

Problem F

Solved by kblack. 03:36 (+1)

题意：有 $n$ 个不同大小的桶，可以进行的操作包括：加满一个桶，倒空一个桶，从一个桶倒到另一个桶，直到空或满，要加出指定容量。

题解：首先排除最大桶也装不下的情况，观察后发现一堆桶可以捣鼓出的一定是 gcd 的倍数的量，进一步的，不妨把最大的桶当成剩余系，其他的往里倒，剩余系只有 $2*10^4$ 的大小，最多就倒那么多次，一定能把指定的量倒出来。

Problem G

Solved by zerol. 00:34 (+3)

签到失败，背锅。我能把 product 看成 sum 也是很厉害的。

Problem H

Solved by ultmaster. 01:38 (+)

题意：给一个点集 $\{(x_i, y_i)\}$，每次询问 $(a,b)$，让你在点集中挑一个点使得 $ax+by$ 最小。

题解：令 $ax+by=c$ 则 $y=\frac{c}{b}-\frac{a}{b}x$。即求截距最小。数形结合一下可知，一定在点集的下凸壳上取到。把下凸壳求出来，然后在凸壳上二分斜率即可。注意会有斜率分母为 0 的情况，所以比较的时候不要用除法。

Problem I

Solved by kblack. 02:10 (+)

Problem J

Solved by kblack. 01:27 (+1)

题意：墙上只有一个面板插座，手上有一堆拖线板，一堆用电器各自要求串联的拖线板不大于指定值，求最多接多少个用电器。

题解：首先观察，更大拖线板用在更接近墙插的位置一定更好，一个安全要求高的用电器可以替换成一个要求低的。也就是用电器一定可以是安全度要求最低的那些，我们二分这个边界（也就是用电器的量），这些用电器全部都要插上，再根据之前的结论，我们在能在最后一刻插上用电器的情况下，尽可能从大的开始用拖线板，判断够不够即可。