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

Upsolved by ultmaster.

题意：求给定的数列是否存在一个排列是模 $n$ 意义下的等差数列。

题解：目标就是要找到一个合适的公差。我们先假设这个公差存在（即数列合法）。众所周知，等差数列有一个性质，就是其任意前缀、任意后缀都是等差数列。那么我们任意找一个点 $c$，然后我们找到尽可能多的 $(x,y)$ 满足 $x+y=2c$（在模意义下，$x$ 和 $y$ 关于 $c$ 对称），然后把这些对连同 $c$ 一起删掉。我们就删掉了这个等差数列的某个前缀或者某个后缀。可以感受一下：如果它真的是一个等差数列的话，一次删除有很大可能会删除很大一段，如果没有做到，那就再试一次。比如说要求删掉原序列的至少 10%，重试次数 20 次，如果 20 次还是不能做到，我们就认为它大概不是等差数列了。最后删剩的部分（比如长度小于 20 时）用暴力判断。注意 $n=1$ 的情况，和满的情况（比如 1 3 5 模 6，0 1 2 3 4 模 5）要特判。

ultmaster: 感谢 神犇的题解，虽然我真的。。。没看懂。

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。