代码源挑战赛 Round 62 题解 - 代码源竞赛平台

T1

100%

直接比较大小然后输出即可。

时间复杂度 O(1)O(1) 。

T2

100%

由于不同位置的 ? 可以替换成不同的字母，因此只需要对每个位置判断是否能够相等即可。

遍历每个位置 ii，如果 S[i]S[i] 和 T[i]T[i] 都是小写字母且不相同，那么一定无法相同；否则若有至少一个 ? 或已经相同，则该位置可以相同。

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

T3

100%

由于只需要在所有操作结束后输出每个格子的印章状态，因此我们可以通过一个数组 dd （初始为0）来记录每个格子的印章状态被修改的次数，当机器人处于工作状态 1 并走到 ii 位置时，d[i]=d[i]+1d[i]=d[i]+1，最后 d[i]d[i] 为奇数表示该位置有印章，偶数表示没有。

接下来只需要模拟每个操作：移动机器人并更新 dd 数组；改变方向；改变工作状态。

需要注意的是更新 dd 数组时不能暴力枚举每个位置进行 +1+1，否则是 O(n∗Q)O(n*Q) 的时间复杂度。

由于我们需要做的是区间 +1+1 ，以及只需要在最后进行单点查询，因此可以通过差分数组来实现：对于区间 [l,r][l,r] 加1，在差分数组 diff[l]+1diff[l]+1，diff[r+1]−1diff[r+1]-1，最后做一遍前缀和即可得到 dd 数组。

时间复杂度 O(n+Q)O(n+Q)。

T4

100%

首先一个连续子串，通过至多 kk 次操作，使得子串中的所有字符相同，最终子串的字符一定是在原本子串中出现次数最多的字符，这样可以使用更少的操作次数。因此“好子串”的条件等价于：

len−maxcnt≤klen-maxcnt \leq k

其中 lenlen 为子串长度，maxcntmaxcnt 为出现次数最多的字符的次数。

暴力枚举所有子串需要 o(n2)o(n^2) 的时间复杂度，显然不行，考虑如何快速计算答案。

假设当前有一个“好子串”，当我们向右增加一个字符时，len−maxcntlen-maxcnt 的值要么不变（增加的是出现最多的字符），要么增加1（增加的不是出现最多的字符）。

因此对于固定的左端点 ll，可以找到一个最大的满足条件的右端点 rr，使得 [l,r0](l≤r0≤r)[l,r_0] (l \leq r_0 \leq r) 都是好子串，并且随着 ll 右移，rr 也是单调向右移动的。对于每个 ll 所对应的 rr，对答案的贡献为 r−l+1r - l + 1。

于是便可以利用双指针（滑动窗口）的方式，维护当前子串每个字符出现次数，即可快速统计答案。

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

T5

100%

我们需要统计树上所有简单路径中，点权和为偶数且 ≥2\geq 2 的路径数量。这是一个经典的树形 DP 问题，考虑每条路径在其最高点（LCA）处统计。

对于结点 uu，定义状态：

  • dp[u][0]dp[u][0] 表示从 uu 出发，向下的所有路径（包括 uu 自身）中，点权和为 0 的路径条数；
  • dp[u][1]dp[u][1] 表示从 uu 出发，向下的所有路径中，点权和为奇数的路径条数；
  • dp[u][2]dp[u][2] 表示从 uu 出发，向下的所有路径中，点权和为偶数（不包含 0）的路径条数；

转移时枚举 uu 的每个儿子 vv，然后根据 cuc_u 分类讨论：

如果 cu=1c_u=1：

  • dp[u][1]+=dp[v][0]+dp[v][2]dp[u][1]+=dp[v][0]+dp[v][2]
  • dp[u][2]+=dp[v][1]dp[u][2]+=dp[v][1]

如果 cu=0c_u=0：

  • dp[u][0]+=dp[v][0]dp[u][0]+=dp[v][0]
  • dp[u][1]+=dp[v][1]dp[u][1]+=dp[v][1]
  • dp[u][2]+=dp[v][2]dp[u][2]+=dp[v][2]

统计以 uu 为 LCA 的“好路径”可以在枚举 vv 的过程中计算：

在当前已合并的部分 dp[u] 与子树 v d的 dp[v]dp[v] 中各选一条路径，进行拼接。要统计点权和为偶数且不为 0 的方案数，有四种情况：

  • dp[v][2]×dp[u][0]dp[v][2] \times dp[u][0]
  • dp[v][2]×dp[u][2]dp[v][2] \times dp[u][2]
  • dp[v][1]×dp[u][1]dp[v][1] \times dp[u][1]
  • dp[v][0]×dp[u][2]dp[v][0] \times dp[u][2]

累加这四项到答案中，再对 vv 进行转移即可。

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

另外也可以先求出所有点权和为偶数的路径数，再减去点权和为 0 的路径数，这样 dp 只需要两个状态，但需要额外计算点权和为 0 的路径数。

T6

100%

由于 fnf_n 始终是 a!a! 和 b!b! 的乘积，因此可以写成：

fn=(a!)xn⋅(b!)ynf_n=(a!)^{x_n} \cdot (b!)^{y_n}

由递推式 fn=fn−1fn−2f_n=f_{n-1} f_{n-2} 得：

xn=xn−1+xn−2  ,  yn=yn−1+yn−2x_n=x_{n-1}+x_{n-2} \;,\; y_n=y_{n-1}+y_{n-2}

因此 xnx_n 和 yny_n 都是斐波那契数列，由于 n≤1014n \leq 10^{14}，因此需要利用矩阵快速幂计算，时间复杂度 O(log⁡n)O(\log n)。

接下来要求 fnf_n 的因子个数，需要将 fnf_n 分解质因子：

fn=∏ppcpf_n=\prod_p p^{c_p}

则正因子个数为：

d(fn)=∏p(cp+1)d(f_n)=\prod_p (c_p+1)

即我们需要知道 fnf_n 的每个质因子的指数。

对于 n!n!，质数 pp 的指数为：

$$v_p(m!)=\sum_{k=1}^{\infty} \left \lfloor \frac{m}{p^{k}} \right \rfloor$$

因此需要先筛出 max(a,b)max(a,b) 范围内的所有质数，即可快速计算每个质数的指数，然后：

$$d(f_n)=\prod_p (v_p(a!) \cdot x_n + v_p(b!) \cdot y_n +1) \;\bmod 998244353$$

根据模运算的分配律，可以对 xnx_n 和 yny_n 取模来进行计算，也就是将矩阵快速幂中的所有运算直接对 998244353 取模（不是对 a!a! 取模）。

时间复杂度 O(N)O(N) （线性筛）。