真服了发到灌水区了
OK今天也是来水一发题解好吧
总的来说，这次还算简单，但是最后一题莫队没写出来有点可惜
先说下个人认为的难度，大家可以参考下
> T1<T2<T5<T4<T3<T6
题目 官方难度 个人认为思维难度 个人认为代码难度 综合难度 T1 橙 红 红 红 T2 黄 橙 橙 橙 T3 绿 黄/绿 蓝 绿 T4 绿 蓝 橙 蓝 T5 蓝 绿 橙 绿 T6 蓝 紫 蓝 蓝
话不多说，正文开始
T1
题目大意：
用一个字符串映射成一个444进制数，要求转101010进制
解法：
没啥好说的，模拟即可，注意powpowpow函数的精度问题。我因为这个WA了一发
代码：
时间复杂度：O(N)O(N)O(N)
空间复杂度：O(N)O(N)O(N)
T2
题目大意：
有 nnn 家公司，每家公司对工作质量和工作速度有两个要求ai,bia_i,b_iai ,bi 。同时有 mmm 名面试者，每
名面试者有两个能力值xi,yix_i,y_ixi ,yi 。一名面试者能通过一家公司的面试当且仅当他的两个能力值都达
到该公司的要求。求每名面试者能通过的公司数量。
解法：
也没啥好说的，直接使用二维前缀和维护即可
代码：
时间复杂度：O(N2)O(N^2)O(N2)
空间复杂度：O(N2)O(N^2)O(N2)
T3
这道题我认为我的解法比官方题解更简单、直观
题目大意：
有两棵节点数均为 nnn 的树，根节点都是 111。给出每棵树节点的权值ai,bia_i,b_iai ,bi 。两棵树有相同的
mmm 个被标记的节点markimark_imarki ，对于每个markimark_imarki ，询问：如果只删除markimark_imarki ，那么树A剩余
节点的LCA权值是否大于树B剩余节点的LCA权值
解法：
这道题要用到一个小结论
多个点的LCA=其中DFS序最大的点和其中DFS序最小的点的LCA
至于怎么证明，太长了这里写不下其实是我不会
你们只能看这个了
所以这题只用维护两棵树的LCA和DFS序就做完了
我用了set来维护DFS序
这题连树链剖分都用不上，太水
代码：
不要被我的代码吓到！长只是因为我不会懒得封装起来
时间复杂度：O(能过)O(能过)O(能过)
空间复杂度：O(能过)O(能过)O(能过)
其实是O(NLOGN)O(NLOGN)O(NLOGN)(应该是)
T4
题目大意：
有 nnn 个太空站，起始在 111 号站，目标到达 nnn 号站。每个站 iii 有一个能源值 aia_iai ，表示
从站 iii 可以传送到的范围是[i+1,i+ai][i+1, i+a_i][i+1,i+ai ]（等概率随机传送）。
求两个人独立使用传送器，恰好用相同次数到达站 nnn 的概率（modmodmod 998244353998244353998244353 ）。
解法：
一眼概率/期望 DP
定义：dp[t][i]dp[t][i]dp[t][i]表示从i点走t次到n点的概率
初始化：
dp[n][0]=1dp[n][0]=1 dp[n][0]=1
状态转移方程很简单：直接推即可
dp[t][i]=1a[i]∑j=i+1min(n,i+a[i])dp[t−1][j] dp[t][i] = \frac{1}{a[i]} \sum_{j=i+1}^{\min(n, i+a[i])} dp[t-1][j] dp[t][i]=a[i]1 j=i+1∑min(n,i+a[i]) dp[t−1][j]
显然，这是O(n3)O(n³)O(n3)/O(n2)O(n^2)O(n2)的，我们可以预处理后缀和来优化：
后缀和：
lst[i][t]=dp[i][t]+lst[i+1][t]\text{lst}[i][t] = \text{dp}[i][t] + \text{lst}[i+1][t] lst[i][t]=dp[i][t]+lst[i+1][t]
于是：
dp[i][t]=lst[i+1][t]−lst[min(n,i+a[i])+1][t]a[i]\text{dp}[i][t] = \frac{\text{lst}[i+1][t] - \text{lst}[\min(n, i+a[i])+1][t]}{a[i]} dp[i][t]=a[i]lst[i+1][t]−lst[min(n,i+a[i])+1][t]
其中lst是后缀和。
最后预处理逆元即可
但是MLE，于是用滚动数组优化
注意一定要开滚动数组！！！8000*8000开不下！
代码：
时间复杂度：O(N2)O(N^2)O(N2)
空间复杂度：O(N)O(N)O(N)
T5
题目大意：
给定一个长度为 nnn 的括号子序列 aaa，要求构造一个长度为 mmm 的合法括号序列 bbb，使得
aaa 是 bbb 的子序列。求满足条件的 bbb 的数量（modmodmod 1e9+71e9+71e9+7）。
解法：
这题依然毒瘤，要开滚动
一眼dp
定义：dp[i][j][k]dp[i][j][k]dp[i][j][k]表示处理到第iii步时，已匹配了原字符串aaa的前jjj个字符，栈中有kkk个左
括号的方案数
方程并不难推
若添加左括号
dp[i+1][j′][k+1]←dp[i+1][j′][k+1]+dp[i][j][k]\text{dp}[i+1][j'][k+1] \leftarrow \text{dp}[i+1][j'][k+1] + \text{dp}[i][j][k] dp[i+1][j′][k+1]←dp[i+1][j′][k+1]+dp[i][j][k]
其中j′={j+1if j<n and a[j]=′(′jotherwise\text{其中} \quad j' = \begin{cases} j + 1 & \text{if } j < n \text{ and } a[j] = '(' \\ j & \text{otherwise} \end{cases} 其中j′={j+1j if j<n and a[j]=′(′otherwise
条件：k+1≤m2\text{条件：} k + 1 \leq \frac{m}{2} 条件：k+1≤2m
若添加右括号
dp[i+1][j′][k−1]←dp[i+1][j′][k−1]+dp[i][j][k]\text{dp}[i+1][j'][k-1] \leftarrow \text{dp}[i+1][j'][k-1] + \text{dp}[i][j][k] dp[i+1][j′][k−1]←dp[i+1][j′][k−1]+dp[i][j][k]
其中j′={j+1if j<n and a[j]=′)′jotherwise\text{其中} \quad j' = \begin{cases} j + 1 & \text{if } j < n \text{ and } a[j] = ')' \\ j & \text{otherwise} \end{cases} 其中j′={j+1j if j<n and a[j]=′)′otherwise
条件：k>0\text{条件：} k > 0 条件：k>0
然后就做完了。。。
代码：
口胡T6
题目大意：
给定一个长度为nnn的数组aaa（每盘饼干的数量），AliceAliceAlice和BobBobBob轮流操作（AliceAliceAlice先
手）。每轮操作包括两步：
1.选择一个非空盘子，取走正数个饼干。
2.对于该盘剩下的饼干，可以选择不动，或者全部合并到另一个非空盘子。
有 qqq 次询问，每次询问区间 [l,r][l, r][l,r]，问该区间有多少个连续子区间，使得在这个子区间上的游
戏AliceAliceAlice必胜。
解法：
经过分析样例，可以蒙到证出这题就是NimNimNim博弈
所以只要求给定区间内异或和为111的区间数量即可，
显然是个莫队但我没写出来
但看到全站没人AC我就放心了
12分暴力代码：
好了本次题解就到这儿了，打字不易，留个赞再走吧
@AC君加个精求求了
