2016-2017 Codeforces Trainings Season 3 Episode 7(CT S03E07)

Problem A

Unsolved.

Problem B

Solved by Kilo. 00:10(+)

Problem C

Solved by Kilo. 00:50(+)

Problem D

Solved by Weaver_zhu && Kilo. 03:43(+)

Problem E

Solved by Xiejiadong. 00:20(+)

题意：给第一匹马找一个匹配，询问是否存在第一匹马的匹配代价大于其他所有的匹配。

题解：贪心。显然给第一匹马找最大的匹配。

其余的肯定是最大的和最小的匹配，依此类推。

直接排序，暴力判断即可。

Problem F

Solved by Xiejiadong. 03:23(+8)

题意：$f_i = f_{i-1} + a_{i \bmod n}$, $f_0 = 0$; $g_n = h - \frac{n(n+1)}{2}$。求第一个 $n$ 满足 $f_n \ge g_n$。

题解：$f_i$分别变成$f_i+i$可以在保证$|f_i-g_i|$不变的情况下，把$g_i$矫正成直线。题目变成询问$f_i$的前缀和第一个超过常数$g$的位置。

二分判断在哪一个周期超过了常数$g$，判断的方法是找一个周期的最高点。

对于第$x$个周期，前$x-1$个周期的前缀和可以直接得到，然后暴力计算本周期的前缀和，判断最大的是否超过了常数$g$。

对于第一个超过的周期，暴力寻找位置即可。

这道题目会爆long long，然后各种玄学的方法来调整判断，于是自闭了。

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Solved by Weaver_zhu. 02:10(+12)

Problem J

Unsolved.

Problem K

Solved by Kilo. 04:44(+)