[CF1155 Educational Codeforces Round 63]题解合集

2小时6道题,所以请记住,对于cf比赛,犹豫就会败北,果断就会白给

CF1155A Reverse a Substring

如果字符大小非严格单增,显然无解,如果出现前面字符大于后面的字符的情况,输出它们的位置即可。

CF1155B Game with Telephone Numbers

一开始还以为是博弈论(我傻了)……结果一个简单的贪心就OK了

一轮游戏会将数字取到只剩11个,如果序列中前 $n-10$ 个元素中,8的数量大于其他的数量,那么显然先手会把其中不是8的取完,先手必胜。如果不大于,后手会把所有的8取完,先手必败。

CF1155C Alarm Clocks Everywhere

我们要找到一个 x和d 使得 $x+kd = a_i$ k为正整数

如果我们的时间累积到 $a_i$ 了,那么我们其实就是要满足 $a_i+kd=a_{i+1}$ 即 $a_{i+1}-a_i=kd$

所以我们就是要用一个间隔来遍历到所有时间点,这个间隔显然是所有相邻时间间隔的gcd,记为d

然后看看第二行里面有没有d的约数,有的话就输出

CF1155D Beautiful Array

其实就是最长连续子串的变形。

变量名 变量作用
$s$ $s_i$ 表示整个序列乘上 $x$ 后的前缀和
$L$ $L_i$ 表示 $i$ 位置往前的最大连续子串和
$R$ $R_i$ 表示 $i$ 位置往后的最大连续子串和

假如我们选择了 $i$ 到 $j$ ($j\le i$) 这一段乘上 $x$ 那么答案就为 $$s[i]-s[j-1]+R[i+1]+L[j-1]$$

我们可以枚举 $s[i]+R[i+1]$ ,用 $max(L[j-1]-s[j-1])$ 来更新答案

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注