Educational Codeforces Round 60 (Rated for Div. 2)
比赛链接: https://codeforces.com/contest/1117
A
题意是给定一个数组 $a$，问算术平均值 $(\frac{1}{r-l+1}\sum_{i=l}^{r}a_i)$ 最大的最长连续段长度是多少. $(1 \le n \le 10^5)$
这个连续段上的值肯定都是数组的最大值 $Max$，那么只需要求出连续最长的 $Max$ 就行了.
AC代码: A.cpp
B
题目给了 $n$ 个能量包，可以选 $m$ 次，选过的能量包不会消失，唯一的限制是同一个能量包最多连续选 $k$ 次，问最多能收获的能量是多少. $(2 \le n \le 2·10^5,1 \le k \le m \le 2·10^9)$
假设 $n$ 个能量包的最大能量是 $Max$，如果有两个 $Max$ 的能量包，只需要来回选这两个能量包就是最优的，答案是 $m·Max$.
如果只有一个 $Max$ 能量包，只需要每选 $k$ 个最大的能量包之后选一个次大的能量包即可. 答案是 $\lfloor \frac{m}{k+1} \rfloor · (Max1·k+Max2)+Max1·(m\%(k+1))$.
AC代码: B.cpp
C
题意是给定起点 $(x_1,y_1)$ 和终点 $(x_2,y_2)$，每天飞船可以选择向四个方向移动一步或者静止不动，同时有一个周期性为 $n$ 的风，每天会使飞船向一个方向移动一步，问飞船最少需要几天到达终点.
假设飞船在第 $k$ 天到达终点，那么 $k$ 天以后飞船只需要反风向移动就能保持在原地，因此可知答案满足单调性.
考虑二分天数 $k$，可以算出 $k$ 天风对于飞船的影响，判断移动后的位置与终点的曼哈顿距离是否 $\le k$ 即可.
AC代码: C.cpp
D
题意是用一定数量的占 $1$ 个空间的物品 $a$ 和一定数量的占 $m$ 个空间的物品 $b$ 来组成一个占 $n$ 个空间的新物品，询问方案数.
可以考虑一个 $dp$，$dp[i]$ 表示构成占 $i$ 个空间的物品的方案数，$dp[i]=dp[i-1]+dp[i-m]$ 表示可以从 $i-1$ 的状态加多一个 $1$ 空间的 $a$ 或者从 $i-m$ 的状态加多一个 $m$ 空间的 $b$ 转移过来.
因为 $n$ 比较大，所以需要用矩阵快速幂来优化这一过程.
AC代码: D.cpp
E
有趣的交互题2333
题意是原本有一个字符串 $s$，经过不超过 $n$ 次的字符交换操作变成 $t$. 现给出字符串 $t$，允许询问三个由小写字母组成的字符串，程序会返回做了相同字符交换操作的结果，问原串 $s$ 是什么?
可以考虑询问字符串:
1、abcdefghi..uvwxyzabc…
2、abcdefghi..uvwxyabc…
3、abcdefghi..uvwabc..
假设结果字符串位置 $i$ 是由原位置 $j$ 移动过来.
可知:
$j \% 26 = ans[1][i] - ‘a’$
$j \% 25 = ans[2][i] - ‘a’$
$j \% 23 = ans[3][i] - ‘a’$
根据中国剩余定理，可以保证在 26*25*23 的范围内一定有一个唯一解，于是得到了 $j$ 到 $i$ 的映射.
从而可以反过来得到原串 $s$.
不一定要采用模数 $23$, $25$, $26$，只要使用的模数两两互质，且乘积大于字符串长度即可.
AC代码: E.cpp
F
To be continued…
G
To be continued…