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.

题意：给出$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)

Problem K

Upsolved by Weaver_zhu.

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

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