Educational Codeforces Round 175 (Rated for Div. 2) A/B/C/D/E

A

题意

给定$n$，问从$0$到$n$中有多少个整数满足对$3$取模后与对$5$取模后相等

解法

假设这个数为$x$，对$3$取模和对$5$取模后均为$y$，那么$x-y$显然是$15$的倍数，而对$3$取模后结果只能为$[0,2]$中的一个，因此每$15$个数字只有前$3$个符合条件
复杂度$O(1)$

B

题意

有一个机器人，一开始在一根数轴上，位置是$x$，并且$x\ne 0$，给定一个长度为$n$的行动序列，包括两种行动，向左移动一步和向右移动一步，每秒执行一步。当机器人移动到原点时，行动序列将重置，下一步会从第一步开始。若一直没走到原点，则行动序列执行完后将在原地不动。问在接下来$k$秒中，机器人经过几次原点

解法

将这个过程拆解为两部分：从$x$第一次走到原点，和从原点出发再次走到原点。分别从这两个点开始模拟一遍行动序列，看第一次走到原点是第几步。之后计算在$k$秒中经过几次即可
复杂度$O(n)$

C

题意

有一块地毯，分为$n$格，一开始每个格子的颜色都是红色的。你有一个刷子，可以选择一段连续的区间，将区间中的格子变为蓝色。你最多可以执行这个操作$k$次，也可以不执行。现在每个格子有一个最终目标颜色和一个惩罚值，当你执行完操作后，这块地毯的惩罚值是所有颜色和最终目标颜色不一致的格子的惩罚值的最大值。求最后地毯的最小惩罚值。

解法

看到最终结果是惩罚值的最大值，很容易想到二分答案，二分之后，对于惩罚值小于等于答案的格子，我们不关心它是什么颜色的
显然，任意两次刷颜色之间的区间不会有交集，否则使用他们的并集来刷一次就可以达到刷两次的效果
考虑我们模拟一个刷子，这个刷子的状态有抬起和放下两种，从左到右遍历这块地毯，对于惩罚值大于答案的格子，如果目标是红色且当前笔刷是放下，则需要将笔刷抬起，如果目标是蓝色且笔刷是抬起，则需要将笔刷放下，这样我们最后观察笔刷放下了几次，就知道至少需要几次操作才能满足条件，看看是否小于等于$k$即可
复杂度$O(nlog_{2}(n))$

D

题意

给定一颗$n$个点的树，其中$1$是根节点，每个节点有一个编号，问有多少个节点序列满足：
1、从$1$开始
2、从第二个节点开始（如果有），每个节点的深度是上一个节点的深度$+1$
3、从第三个节点开始（如果有），每个节点不是上一个节点的儿子

解法

BFS+DP，记录以每个节点为结尾的合法序列数量和以每个深度为结尾的合法序列数量，转移就是当前节点的深度$-1$的合法序列数量减去当前节点的父亲为结尾的合法序列数量
复杂度$O(n)$

E

题意

两人在一个$01$串上玩游戏，每一步必须选择两个相邻的数字（将串考虑为环，也就是头尾两个数字也视作相邻）去掉，并且有额外条件：
1、先手玩家只能选择两个$0$
2、后手玩家不能选择两个$0$
当某个玩家没有合法的操作时，他输掉游戏
现在给定一个长度为$n$的$01$串，问有多少个子串满足在这个子串上玩游戏是先手必胜的

解法

非常恶心的一个题
首先考虑对于一个$01$串，先手必胜的条件是什么
经过手动模拟或者推导，可以发现，先手是否必胜只和$0$和$1$的数量有关，和具体的排列无关
我没严格证明，需要严格推导证明的可以参考cf官方的题解
进一步可以知道，先手必胜的条件为$cnt_{0}\ge 3\times cnt_{1}+2$或$cnt_{0}=3\times cnt_{1}-1$
于是我们的目的转化为，计算有多少个子串满足上面的条件
将这个条件移项一下就可以得到$cnt_{0}-3\times cnt_{1}\ge 2$或$cnt_{0}-3\times cnt_{1}=-1$
我们计算一个前缀和，其中遇到$0$时$+1$，遇到$1$时$-3$，这样满足条件的子串就是区间按这个前缀和计算后满足结果大于等于$2$或者恰好等于$-1$的子串，因此可以使用线段树或树状数组在前缀和的值域上维护有多少个前缀，就可以得出答案
复杂度$O(nlog_{2}(n))$