2013-2014 Petrozavodsk Winter Training Camp, Saratov SU Contest

Problem A

Unsolved.

Problem B

Solved by kblack, translated by zerol. 03:51 (+)

题意：双倍汉诺塔，规定最后同大小饼的顺序。

题解：正常移动一堆需要两倍正常汉诺塔的时间，而且会导致移动的最下两个饼反向，多消耗一些操作可以修正，但小一号的饼会反向，往上逐层处理，注意特判最顶上的情况。

zerol: 没我啥事，就打了个暴力。

Problem C

Solved by ultmaster. 01:16 (+)

题意：把一种 CSS 翻译成另一种 CSS。

题解：根据题意模拟。比较好写的方法应该是：求出实际中心并绕 pivot 旋转、缩放，然后求出矩形实际长宽即可。

Problem D

Unsolved.

Problem E

Solved by zerol. 00:32 (+)

题意：给若干个字符串，要求两两配对，使得每一对的最长公共前缀的长度和最大。

题解：全部插入一棵 trie，如果某个结点有超过两个字符串，就两两一对用掉，如果剩下一个的话就丢给父节点。

Problem F

Solved by kblack. 01:33 (+)

题意：一堆点，可以对 $x = y$ 对称变换，要求变换后按横坐标是不降且纵坐标不升。

题解：先全部折到对称轴上方，然后从左上找一条符合要求的序列，剩下的再找一条，如果还剩那就完蛋了，两条的尾巴判断一下，如果两个可以共存那就构造好了，否则本来也是要完蛋的。

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by kblack. 00:54 (+)

温暖的枚举签到。

Problem K

Solved by ultmaster. 03:59 (+1)

题意：有一堆 task，第 $i$ 个需要在内核态上运行 $a_i$ 秒，然后（不支持抢占），在用户态上运行 $b_i$ 秒，要求完成时间是 $t_i$；内核态用户态切换开销为 $f$。求迟到得最久的 task 迟到了多久。

题解：显然二分答案，使得每个 task 都有一个 deadline。按照 deadline 排序，然后逐个加入。第一个毫无疑问肯定是内核态做完切换成用户态做。而 $a_2$ 就要考虑是跟 $a_1$ 合并一起做，还是另起炉灶。前者的好处是省掉了 $2f$ 的上下文切换开销；当然缺陷在于有可能第一个 deadline 很紧，再做个 $a_2$ 就赶不及了。如果能选择前者，我们贪心地选择前者；否则，另起炉灶，并且完全忘掉第一个的事情，因为我们已经有第二个这个炉灶了。（后续加入的时候跟后面的合并比跟前面的合并肯定更好，因为产生的开销是相同的，但放在前面容易导致更多的 deadline 崩掉。）如果发现另起炉灶也来不及，那就彻底凉凉了。

实现的时候要维护一个“当前炉灶最多还能承受多少的开销”，这个开销是由多个 deadline 一起决定的。U 在实现的时候很不幸地漏掉了维护，贡献了一个 dirt。