2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest

ECNU Foreigners

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 (+)

题意：若干个要求，要求是从第 $i+1$ 个位置开始，第 $a_j$ 位置上的值是第一次出现的，求字典序最小的解。

题解：可以转化为，对于每个值要求他在前面一个区间里没有出现过，我们从小到大贪心求每一位上的值。假设第 $i$ 个值要求在 $[x, i-1]$ 没有出现过，我们只要求最小的最后一次出现在 $[1, x-1]$ 的值，这个可以用线段树维护最小值（非最后一次出现的用 inf 无效化），如果没有可以选的，就新开一个。

Problem J

Solved by kblack. 01:27 (+1)

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

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

Problem K

Upsolved by zerol.

题意：可以将边权均为 1 树上长度至多为 k 的一段的边权置为 0，求直径的最小值，如果直径一样，需要使修改的长度最小，要求输出方案。

题解：https://zerol.me/2018/10/15/CF-100886K/

One,Two,Three,AK

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by dreamcloud. 00:35:21(+1)

Problem H

Solved by dreamcloud. 05:00:00(+1)

Problem I

Solved by Xiejiadong. 04:04:11(+)

题意：给出一个乱序还有缺的表，还原数列。

题解：显然，就是给你了一些数在某些区间里面没有出现过，然后求最小的字典序。

考虑用线段树维护每一个数最后出现的位置，维护min。然后直接在线段树上二分，查找那个区间里面没有出现过的最小数即可。

Problem J

Solved by Xiejiadong. 02:43:05(+2)

题意：有插头和插线板，电器对距离主插头的距离有要求，求最多能插上的电器。

题解：显然，插头是按照座位数量从小到大排序着来插的。

如果我们按照电器的安全等级排序的话，显然肯定是按照前缀来做最优。

二分前缀的长度，然后贪心的插插头。

Problem K

Unsolved.