Difference between revisions of "2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest"
Jump to navigation
Jump to search
Line 18: | Line 18: | ||
Solved by zerol. 00:34 (+3) | Solved by zerol. 00:34 (+3) | ||
+ | |||
+ | 签到失败,背锅。我能把 product 看成 sum 也是很厉害的。 | ||
== Problem H == | == Problem H == |
Revision as of 13:02, 14 October 2018
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)
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 (+)
Problem J
Solved by kblack. 01:27 (+1)