2013-2014 Petrozavodsk Winter Training Camp Saratov SU Contest

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Solved by Weaver_zhu. 01:59 (+)

题意：告诉旋转中心，缩放中心，矩形长宽高和缩放比例，求出一个css的样式表使得两种方式的矩形最后一样。

题解：先求出真矩形的中心然后转回去。坑的是这个坐标系y轴是反的，不能直接套背的坐标变换矩阵。

Problem D

Unsolved.

Problem E

Solved by Xiejiadong. 00:54 (+2)

题意：两个字符串可以匹配成一队，他们的价值是他们的公共前缀，求最大价值。

题解：把所有的字符串丢进 Trie ，如果当前结点的单词结尾数量大于 $1$ ，那么就两两匹配，他们的价值就是当前结点的深度。

如果匹配完以后还有剩下的，丢给父亲。

两发罚时是因为煞笔 queue 导致了我 MLE 。

Problem F

Upsolved by Weaver_zhu.

题意：给出$n$个二元组$(x_i,y_i)$，求出一个排序使得$x_i$不减，$y_i$不增。

题解：场上思维僵化忘记了偏序问题的套路，就是按$x_i$从小到大插入，如果遇到两个冲突，就换当前这个，因为当前这个$x_i$更大，换到$y_i$去能贪心的让限制更宽。当然，同一个不能被换两次（否则是徒劳的），所以一个二元组遇到两次要转的时候就完蛋了。

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by Kilo_5723. 04:53 (+3)

题意：一开始，完成第一个工作的时间花费是 $1$，之后每一个工作比前一个工作花的时间多 $1$。现在可以在工作中花 $k$ 时间吃巧克力，使得完成下一个工作的时间花费重置为 $1$，但是接下来每个工作多花的时间要 $+1$。你可以吃无限多次巧克力，求完成所有工作需要的最少时间。

题解：从小到大枚举吃巧克力的次数，花费时间和吃巧克力的次数应该是一个凹函数。从 $k$ 块巧克力推到 $k+1$ 块巧克力，我们只需要维护 $k$ 个数列，代表当前第 $k$ 次吃巧克力时最后一次工作花费的时间，如果把花费时间最多的工作放到新的巧克力上能让总时间减少的话就这么放，每次判断答案是不是比原来好了，一旦比原来差就输出上一步的答案。

Problem K

Upsolved by Weaver_zhu.

题意：一个题要想$a_i$写$b_i$，切换到想模式需要额外$f_1$，写模式$f_2$。每个问题完成时间$r_i$要使得$r_i-t_i$最小，求方案。

题解：按$t_i$排序，可以证明排序后一定更不差。然后一个个插贪心让切换尽可能少。