Rating+=78 ovo

但这个数字怎么感觉好熟悉。。。

T1 箭头走廊

送分题一道。

但是这种题目真的是CSP-S会放的吗。。。ZR我怎么感觉不对劲呢qwq

其实这题都算好的了，看看某道A开头的题目就知道ZR的S模拟赛到底有多水。。。

鉴于本题思路还是比某道A开头的题目难一点点的。。。

所以还是讲一下思路吧qwq

本题正解思路小总结：

• 首先，机器人所在房间的箭头方向是能够确定机器人最终要从哪个出口出的，因为很容易发现，机器人如果要走另一个出口必然会经过起始房间，而起始房间的箭头方向是相反的，故不可能走另一个出口。（若当前房间的箭头为 L 则走左边出口，若当前房间的箭头为 R 则走右边出口。）
• 接着，很容易发现，若路径上有一个箭头指向相反方向的房间，那么机器人是不可能出去的，因为它被两个相反方向的箭头包夹了。
• 那么，对于每个房间，只要判断这个房间箭头所指方向是否有箭头方向与之相反的房间，如果有的话，该房间的机器人是无法出去的。
• 那么如何 $O(n)$ 判断每个房间的机器人是否可出去呢？创建一个布尔变量。先从左到右遍历一遍字符串。判断当前字符是否为 R，如果出现了 R 代表之后的所有 L 都无法出去，使用布尔变量存该房间左侧是否有 R 即可，若该房间为 L 且布尔变量表示之前出现了 R，说明该房间的机器人无法出去。从右往左遍历时同理。

100pts

T2 灯带

全机房只有我一个人感觉这题很难想吗。。。

看到这题是真的很懵啊。虽然后面想出来了。

本题正解思路小总结：

• 由题意，连续亮灯段数等价于环上相邻位置中 $0 \to 1$（或 $? \to 1$）状态转移的次数，特判全亮情况。
• 预处理 $2^k$，其中 $k$ 为字符串中 ? 的总数，用于快速计算组合方案数。
• 遍历每个位置 $i$ 及其前驱 $pre$，根据两者字符类型累加对应方案数：0->1 贡献 $2^k$，0->? 贡献 $2^{k-1}$，?->1 贡献 $2^{k-1}$，?->? 贡献 $2^{k-2}$。
• 若字符串中无 0 且无 1（全为 ?），则全亮方案额外贡献 $1$。
• 统计所有 $0 \to 1$ 边界处的方案数总和，即为所有补全方案中亮灯段数的总和。
• 时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

100pts

T3 覆色

这道题还是有难度的（ZR放过我们吧我再也不说题目水了。。。）

连xyz都没能过掉。。。（%%%）

20pts

本题正解思路小总结：

• 特判无解情况：每次操作最多覆盖2个格子，若 $2m < n$，则无法覆盖所有格子，直接输出 $0$。
• 动态规划：dp[i][j] 表示长度为 $i$ 的序列划分为 $j$ 段且每段长度不超过 $2$ 的方案数，转移方程为 dp[i][j] = 2*j*dp[i-1][j] + (i-2*j+2)*dp[i-1][j-1]。
• 预处理阶乘和逆元，实现常规组合数 $C(a,b)$ 计算；由于 $m$ 很大，组合数 $C(m-1, i-1)$ 通过循环累乘计算。
• 枚举最终序列的颜色段数 $i$（范围从 $(n+1)/2$ 到 $n-1$），因为每段长度最多为2，且最后一次操作必定留下颜色 $m$。
• 对于固定的段数 $i$，枚举 DP 状态 $j$，累加 dp[j][i] * C(i-j, n-i-j) 计算满足条件的长度分配方案数。
• 由于最后一种颜色必定是 $m$，需从 $m-1$ 种颜色中选出剩余的 $i-1$ 种，方案数为 $C(m-1, i-1)$，最后累加所有方案并取模输出。

订正

T4 树上追逐

T3都是xzy打不出来的题，T4肯定是更难的。。。

这题连打暴力都难打。。。

不过还好是打出来了qwq

10pts

（暂无订正）