T1

100%

假设第 $i$ 名同学装弱，那么他的真实分数应为 $b_i+10$，其他同学的真实分数仍为报出的分数。

要使真实分数仍按排名非严格递减，需要满足：

• $b_i+10\le 10^6$，即真实分数没有超过满分；
• 若 $i>1$，则 $b_{i-1}\ge b_i+10$，即他的真实分数没有超过前一名。

不需要检查后一名，因为输入已经保证 $b_i\ge b_{i+1}$，增加 $10$ 后仍然满足 $b_i+10\ge b_{i+1}$。

枚举每个位置并检查上述条件，统计合法位置数即可。时间复杂度为 $O(n)$。

T2

50%

枚举每个位置作为一段连胜的起点，再向右找到第一个 L，可以求出从该位置开始的连续 W 数量。

时间复杂度为 $O(n^2)$。

100%

从左到右扫描字符串，维护当前连续出现的 W 数量 now 和历史最大值 ans：

• 遇到 W 时令 now 加 $1$，并用它更新 ans；
• 遇到 L 时令 now=0。

每个字符只处理一次。时间复杂度为 $O(n)$。

T3

100%

按从小到大的顺序枚举 $n$ 的每个因数 $k$。对于固定的 $k$，将序列依次划分为 $n/k$ 个长度为 $k$ 的连续段，并统计每段中支持款式 $1$ 的人数 $cnt$。

该组中支持款式 $2$ 的人数为 $k-cnt$，所以当且仅当

$$cnt>k-cnt$$

时，这一组支持款式 $1$。逐组判断并统计即可得到当前 $k$ 的答案。

因为只枚举 $n$ 的因数，每种分组都能恰好覆盖所有同学；又因为不同小组对应互不相交的连续段，所以每个小组都会被恰好统计一次。

设 $d(n)$ 为 $n$ 的因数个数。对于每个因数都扫描一次整个序列，时间复杂度为 $O(nd(n))$。

T4

30%

每个操作都有选择和不选择两种可能，可以用 DFS 枚举所有选择方案，并在递归过程中维护当前的 $x$。

时间复杂度为 $O(2^n)$，递归空间复杂度为 $O(n)$。

100%

令 $L_i$ 和 $R_i$ 分别表示只考虑前 $i$ 个操作时，能够得到的最小值和最大值。

初始时还没有处理任何操作，只能得到 $x=0$，因此

$$L_0=R_0=0.$$

若不选择第 $i$ 个操作，原来的结果仍然可达；若选择它，变换为

$$x\longmapsto 2a_i-x.$$

对于第 $i$ 个操作，有“不选择”和“选择”两种决策。不选择时，原来的两个极值保持不变；选择时，由于 $2a_i-x$ 关于 $x$ 单调递减，新的最小值由原最大值产生，新的最大值由原最小值产生。因此

$$\begin{aligned} L_i&=\min\bigl(L_{i-1},\ 2a_i-R_{i-1}\bigr),\\ R_i&=\max\bigl(R_{i-1},\ 2a_i-L_{i-1}\bigr). \end{aligned}$$

每一步都考虑了是否使用当前操作，因此所有合法的操作子序列都被包含在状态中；而一次跳跃是单调递减的线性变换，其变换后结果的极值只可能由变换前的两个极值产生，所以无需保存其他可达值。最终答案为 $R_n$。

时间复杂度为 $O(n)$。

T5

50%

固定一次询问的线路宽度 $w$。对于每个节点 $u$，从 $u$ 不断向父亲移动，同时维护路径上的最小、最大权值，就能找到满足路径宽度不超过 $w$ 的最浅祖先 $high_u$。

求出所有 $high_u$ 后，再自底向上贪心。直接逐级向上寻找的单次询问复杂度为 $O(n^2)$。

100%

先把树以 $1$ 为根，求出每个节点的父亲、深度以及一份父亲先于儿子的遍历序。以下是单次询问的做法。

对于节点 $u$，记 $high_u$ 为满足

$$\max_{v\in path(high_u,u)}a_v- \min_{v\in path(high_u,u)}a_v\le w$$

的最浅祖先。从 $u$ 向上加入更多节点时，路径最大值不会减小，最小值不会增大，因此路径宽度单调不降。

预处理倍增数组：

• $up_{u,j}$ 表示 $u$ 的 $2^j$ 级祖先；
• $mn_{u,j},mx_{u,j}$ 分别表示从 $u$ 到 $up_{u,j}$ 的路径上的最小、最大权值。

对于一次询问，从节点 $u$ 开始维护当前路径的最小值和最大值，按 $j$ 从大到小尝试向上跳 $2^j$ 步。若合并这一段后仍满足最大值减最小值不超过 $w$，就接受这次跳跃。最终停留的位置就是 $high_u$。

每个节点的 $high_u$ 可以在 $O(\log n)$ 时间内求出。

每条线路的下端点确定后，都把它的上端点放在能够到达的最浅祖先处，这不会减少它覆盖的节点。

逆序处理节点。令 $top_u$ 表示当前已经选择且下端点位于 $u$ 子树内的所有线路中，上端点的最小深度；若还没有这样的线路，则令 $top_u=+\infty$。

先合并所有儿子：

$$top_u=\min_{v\text{ 是 }u\text{ 的儿子}}top_v.$$

• 若 $top_u\le depth_u$，对应线路的下端点在 $u$ 的子树中、上端点是 $u$ 或 $u$ 的祖先，所以这条线路已经覆盖 $u$；

• 若 $top_u>depth_u$，当前没有任何已选线路覆盖 $u$。新建线路 $high_u\to u$，答案加 $1$，并令

  $$top_u=\min(top_u,depth_{high_u}).$$

这个贪心是最优的。处理到未覆盖的 $u$ 时，任何完整方案都必须再加入至少一条覆盖 $u$ 的线路。若这条线路的下端点是 $u$ 的严格后代，把它替换成 $high_u\to u$ 不会破坏已经完成的子树覆盖；同时，原线路从某个祖先到 $u$ 的前缀也是合法的，所以 $high_u$ 不会比原线路的上端点更深。也就是说，在同样新增一条线路的前提下，选择下端点 $u$ 对后续祖先的覆盖不会更差。

倍增预处理的时间和空间复杂度均为 $O(n\log n)$。每次询问求所有 $high_u$ 需要 $O(n\log n)$，贪心需要 $O(n)$，所以总时间复杂度为 $O(n\log n+qn\log n),$

T6

20%

当 $n\le15$ 时可以直接按照定义拼接出 $S_3,S_4,\ldots,S_n$，再遍历 $S_n$ 统计答案。

60%

设 $C_i$ 表示 $S_i$ 中 wow 的出现次数。由

$$S_i=S_{i-2}+S_{i-1}$$

可知 $S_i$ 中的 wow 分为三类：完全位于 $S_{i-2}$ 中、完全位于 $S_{i-1}$ 中、跨越两个字符串的拼接位置。记第三类的数量为 $E_i$，则

$$C_i=C_{i-2}+C_{i-1}+E_i.$$

由于 wow 的长度为 $3$，跨界出现只可能有以下两种形式：

• 左侧字符串的最后一个字符与右侧字符串的前两个字符组成 wow；
• 左侧字符串的最后两个字符与右侧字符串的第一个字符组成 wow。

因此只需保存每个字符串长度为 $2$ 的前缀和后缀，就能在 $O(1)$ 时间内求出 $E_i$，再按照递推式计算 $C_i$。这一做法的时间复杂度为 $O(n)$。

100%

由于 $S_1,S_2$ 均非空，所以 $|S_3|\ge2$。对于 $i\ge4$，$S_i$ 的末尾来自 $S_{i-1}$，且 $|S_{i-1}|\ge2$，因此

$$suf_i=suf_{i-1}.$$

也就是说，从 $S_3$ 开始，所有字符串长度为 $2$ 的后缀都相同。类似地，对于 $i\ge5$，$S_i$ 的开头完整来自 $S_{i-2}$，因此

$$pre_i=pre_{i-2}.$$

所以长度为 $2$ 的前缀按照下标奇偶交替。跨界贡献 $E_i$ 只由 $S_{i-2}$ 的后缀和 $S_{i-1}$ 的前缀决定，故从 $i=5$ 开始也只会在两个常数之间交替。记

$$E_i= \begin{cases} p,&i\text{ 为奇数},\\ q,&i\text{ 为偶数}, \end{cases} \qquad(i\ge5).$$

只需构造长度很小的 $S_3,S_4$，便可直接求出 $C_3,C_4$。其中 $p$ 是拼接 $S_3+S_4$ 时的跨界贡献；$q$ 是下一次拼接的跨界贡献。计算 $q$ 时不必构造完整的 $S_5$，因为 $S_5$ 的前两个字符与 $S_3$ 相同。

为处理递推中的加法常数，定义

$$V_i= \begin{pmatrix} C_{i-1}\\ C_i\\ 1 \end{pmatrix}.$$

若下一次拼接的跨界贡献为 $c$，则

$$V_{i+1}= M(c)V_i, \qquad M(c)= \begin{pmatrix} 0&1&0\\ 1&1&c\\ 0&0&1 \end{pmatrix}.$$

令

$$A=M(p),\qquad B=M(q).$$

从 $V_4=(C_3,C_4,1)^T$ 出发，第一次转移到 $V_5$ 使用 $A$，第二次转移到 $V_6$ 使用 $B$，之后不断交替。因此可以把相邻两次转移合并为 $BA$。

设 $t=n-4$。若 $t$ 为偶数，则

$$V_n=(BA)^{t/2}V_4;$$

若 $t$ 为奇数，则

$$V_n=A(BA)^{\lfloor t/2\rfloor}V_4.$$

$V_n$ 的第二项就是 $C_n$。当 $n\le4$ 时直接构造字符串并统计即可。

矩阵大小固定为 $3\times3$，每组数据的时间复杂度为 $O(\log n)$。