挑战赛29题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 午枫的字符串移动3 入门 T2 午枫的染色游戏 普及- T3 小枫的X 普及/提高- T4 小午的哈希表 普及/提高- T5 午枫的邻居 普及/提高- T6 小安的新数组 普及/提高-
T1 午枫的字符串移动3
题目大意
给定两个长度相同的字符串 sss 和 ttt ，sss 的每个字符都可以循环右移，判断是否可以将 sss 变为 ttt 。
解题思路
直接判断 sss 和 ttt 的每位字符的差值是否相同即可。
参考代码
T2 午枫的染色游戏
题目大意
在一个 n×mn\times mn×m 的透明网格中双方进行染色，问谁最后会赢。
解题思路
先说结论：如果 nnn 和 mmm 都为奇数时，小午必胜，否则小枫必胜。
* 当 nnn 和 mmm 都为奇数时，小午先手只要在中心位置染色，接下来不管小枫怎么染，小午只要在小枫的中心对称位置上染上相同的颜色即可，最后一定是小午获胜。
* 当 nnn 和 mmm 有一个不为奇数时，那么小枫就可以在小午染色的对称位置进行染色，最后一定是小枫获胜。
参考代码
T3 小枫的X
题目大意
有一个仅包含 . 和 X 的字符串，最多替换 kkk 的 . 为 X ，问最多能使多少个 X 连续。
解题思路
本体可以使用双指针或二分答案。
考虑双指针，优先滑动右端点 rrr ，记录区间内 . 的数量，当数量大于 kkk 时，移动左端点 lll 直至区间内 . 的数量小于等于 kkk 。时间复杂度为 O(n)O(n)O(n) 。
考虑二分，我们可以用前缀和维护 X 的数量，二分求区间长度，遍历是否可以构成长度为 midmidmid 的字串即可。时间复杂度为 O(nlogn)O(n\log n)O(nlogn)
参考答案
方法一：双指针
方法二：二分
T4 小午的哈希表
题目大意
有一个 n=220n = 2^{20}n=220 大小的数组，其实所有位置都为 −1-1−1 ，有 qqq 次操作，每次操作会给出两个整数 opopop 和 xxx ，如果 op=1op=1op=1 ，则从 x%nx\%nx%n 的位置开始向右寻找第一个为 −1-1−1 的位置，找到后将此位置的值设置为 xxx ；如果 op=2op=2op=2 ，则输出数组 x%nx\%nx%n 的值。
解题思路
首先，n=220=1048576n = 2^{20} = 1048576n=220=1048576 ，这是数组可以开到的大小，所以我们可以用数组 aaa 存储所有位置具体的数字。另外，还可以用 set 存储值为 −1-1−1 的位置。
查询时，如果 op=2op=2op=2 ，则直接输出 a[x%n]a[x\%n]a[x%n] 即可；如果 op=1op=1op=1 ，则可以在 set 中通过二分 lower_bound 函数找到第一个大于等于 x%nx\%nx%n 的位置，如果没找到，则再用二分找第一个大于等于 000 的位置。
参考代码
T5 午枫的邻居
题目大意
判断是否存在一种将编号为 111 到 nnn 的 nnn 个人的排列方式，使得以下 mmm 个条件全部成立。
* 条件：第 aia_iai 个人与第 bib_ibi 个人必须相邻。
解题思路
简单来说，题目就是要求我们构造一条链，满足所有点对相邻的条件。
如果要构成一条链，需要满足：
* 每个点的度最大为 222 。
* 不存在环。
我们只需要判断以上两个条件是否都满足即可。对所有的点对关系建图，第一个条件直接记录每个点的度，判断是否存在点的度大于等于 333 的；第二个条件用 dfsdfsdfs 或并查集判断图中是否存在环即可。
参考代码
T6 小安的新数组
题目大意
给定两个非递减数组 a,ba,ba,b 满足 ai≤bia_i\leq b_iai ≤bi ，求非递减数组 ccc 满足 ai≤ci≤bia_i\leq c_i\leq b_iai ≤ci ≤bi 的个数，并对 998244353998244353998244353 取模。
解题思路
考虑 DPDPDP。
状态表示：令 fi,jf_{i,j}fi,j 表示在数组 ccc 的前 iii 个中且 ai≤ci≤ja_i\leq c_i \leq jai ≤ci ≤j 的数量。
状态计算：显然，fi,jf_{i,j}fi,j 一定包含 fi,j−1f_{i,j−1}fi,j−1 和 fi−1,jf_{i−1,j}fi−1,j 。所以转移方程如下（注意：jjj 需要满足 j≤bi−1j\leq b_{i−1}j≤bi−1 ）：
{fi,j=fi,j−1+fi−1,j if j≤bi−1fi,j=fi,j−1+fi−1,bj−1 if j>bi−1\begin{cases} f_{i,j}=f_{i,j-1}+f_{i-1,j} & \text{ if } j\leq b_{i-1}\\ f_{i,j}=f_{i,j-1}+f_{i-1,b_{j-1}} & \text{ if } j>b_{i-1} \end{cases} {fi,j =fi,j−1 +fi−1,j fi,j =fi,j−1 +fi−1,bj−1 if j≤bi−1 if j>bi−1
在递推之前先处理一下 i=1i=1i=1 的状态，即递推起点。
最终结果为 fn,bnf_{n,b_n}fn,bn 。
参考代码
