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(+)
题意:给出m个询问,每个询问给出$l_1,l_2,r_1,r_2$,求由多少个二元组(i,j)使得$l_1<=i<=r_1,l_2<=j<=r_2,a_i=a_j$ 题解:从$f(l_1,r_1,l_2,r_2)到f(l_1+1,r_1,l_2,r_2)$等曼哈顿距离为1的询问是可以$O(1)$转移的,加上或者减去改变的数作为二元组其中一个点即可。然而四维还不能直接使用莫队,需要用容斥转化成二维查询。$dp[i][j]$表示1到i,1到j两个区间的询问,则$solve(l_1,r_1,l_2,r_2)=dp[r_1][r_2]-dp[l_1-1][r_2]-dp[r_1-1][l_2]+dp[l_1-1][l_2-1] $。
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)
题意:给出两个素数a,b($<=10^{15}),求出只包含加减运算的的运算步骤,且中间值和加或减的数均为素数。 题解:奇数加奇数为偶数,而只有2不是奇数,所以运算的情况是相当少的。同时一个数最多加2两次,否则$x,x+2,x+4$模3的值均不同,有一个一定不是素数。如果一个数是奇数,则它只能加减2,或者是减到2。如果一个数是2,则它可以加或减到b-4~b+4。判素数应该使用`Miller-Rabin`,由于之前没怎么用过就被红书的板子坑了(大概是素数没选对,数据会卡。
Problem J
Unsolved.
Problem K
Solved by Kilo. 04:44(+)