day6 字符串

A

• 如果有解，则都能通过最多一次操作把它变成目标串
• 我们可以先预处理出所有换位置后可以达到目标串的位置，进行 DP

B

• KMP板子

D

• 使用字符串哈希
• 枚举'+'和'='位置，验证是否满足 $a + b = c$
• 检查是否有前导零
• 需要选择一个特殊的模数防止被卡

D

• 使用 Manacher 算法处理字符串
• 预处理回文半径
• 贪心从左往右折叠，由于回文的性质保证答案正确

day7 dp(1)

A

• 状态定义：$f_{i,c}$ 表示将前 $i$ 个元素染色，且第 $i$ 个元素值为 $c$ 时的最小硬币数
  • 直接染色：f[a[i]][i] = min(f[0/1/2][i-1] + 1)
  • 传递染色：f[a[i]-1][i] = min(f[0/1/2][vis[i]-1] + 1)
• 使用滚动数组优化空间

B

• 动态规划求解最优选择问题
• 状态定义：$f_{j,k}$ 表示选 $j$ 个杯子，总容量为$k$ 时的最大水量
• f[j][k] = max(f[j][k], f[j-1][k-b[i]] + a[i])

C

• 动态规划求解最大美丽值问题
• 状态定义：$f_{i,j}$`表示前 $i$ 张图片选择 $j$ 张时的最大美丽值
• 使用单调队列优化区间最大值查询
• 转移方程：f[i][j] = max(f[i-k..i-1][j-1]) + a[i]

day9 dp(2)

A

• 状态定义：$f_{i,j}$表示前 $i$ 次睡眠，当前时间为$j$ 时的最大好睡眠次数
• 每次选择 $a_i$ 或 $a_{i-1}$小时后的时间点， f[i][j] = max(f[i-1][(j-a[i])%mod], f[i-1][(j-a[i]+1)%mod]) + C(j)

B

• 状态定义：$f_{i,j}$ 表示前 $i$ 个矩形获得 $j$ 分的最小操作次数
• 对每个矩形枚举可能获得的分数 $k$, f[i][j] = min(f[i][j], f[i-1][j-kk] + cost)

day10 dp(3)

A

• 状态定义：$f[1/2/3/4]$ 分别表示匹配到h/a/r/d时的最小代价
• 关键转移：
  • 遇到 h 时累计代价
  • 遇到 a/r/d 时取保留或删除的最小代价

C

• 状态定义：$f_{l,r}$ 表示构建 $l$ 到 $r$ 的方案数
• 关键转移：
  • 当前字符添加到前端：if (s[len]==t[l]) f[l][r] += f[l+1][r]
  • 当前字符添加到后端：if (s[len]==t[r]) f[l][r] += f[l][r-1]
• 初始化：单字符方案数为 $2$（前后加为不同方案）

day11 组合数学(1)

A

• 模拟二分过程，统计需要满足：
  • $a_i < x$ 的元素数 $cnt1$
  • $a_i > x$ 的元素数 $cnt2$
• 计算合法排列数： $\binom{x-1}{cnt1} \cdot cnt1! \cdot \binom{n-x}{cnt2} \cdot cnt2! \cdot (n-cnt1-cnt2-1)!$

C

• 每个白格$(x,y)$的贡献为$\binom{x+y}{x}$
• 总操作数为所有白格的组合数之和： $\sum_{x=0}^n \binom{x+a_x}{x+1}$
• 利用组合数性质 $\sum_{y=0}^{k-1}\binom{x+y}{x} = \binom{x+k}{x+1}$

D

• 总方案数计算：$\frac{(l+1)(l+2)(l+3)}{6}$
• 非法方案数计算（不满足三角形不等式）：
  • 对每种排序$(x,y,z)$计算$x+y \leq z+k$的情况
  • 非法数：$\sum_{k=0}^l \frac{(k-d+1)(k-d+2)}{2}$，其中$d=z-x-y$
• 最终合法方案数：总方案数 - 三种非法情况之和

E

• BST 性质：左子树小于根小于右子树
• 动态规划计算方案数：
  • 对未知节点区间$[l,r]$，方案数为$\binom{r-l+sum}{sum}$
• 最终答案：$\prod_{\text{}} \binom{r-l+sum}{sum} \bmod 998244353$

day13 组合数学(2)

A

• 整体方案数：$\binom{n/3}{n/6}$（选择 $n/6$ 组染 $2$ 红 $1$ 蓝，其余染 $1$ 红 $2$ 蓝）
• 每组内部方案数乘数：
  • 若三边权相同：有 $3$ 个方案
  • 若最小两边权相同：有 $2$ 个方案

day14 图论(1)

A

• 将同一组连边，端点一定只有一条边
• 从端点开始 DFS 构建排列链

B

• 反向 Dijkstra 从所有出口出发
• 能挡就挡因为决策点当前最优
• 输出起点 $1$ 的最短逃生时间

H

• 二分图建模：每个泥地连接对应的行列节点，行编号为左部，列编号为右部
• 网络流求解最小点覆盖

day15 图论（二）

A

• 二分 $mid$，构建满足 $a_i \leq mid$ 的子图
• $dis_i$ 记录到 $i$ 点的最长路径
• 存在长度 $\geq k$ 的路径或环

day17 树上问题(1)

A

• 重链剖分线段树维护节点深度贡献值
• 贪心选择贡献最大节点
• 更新路径贡献 $-1$

B

• 选择 $n-k$ 个节点, 从叶子节点开始BFS扩展
• 答案为 $mx$ 即为最小化最大距离

day18 树上问题(2)

A

• 构建极值，应该在每个子树内构造几值，每个子树的权值形成连续区间
• 答案为 dfs 序

B

• 结合题意，必须是一条链
• 暴力枚举并搜索可行方案

day19 数论

A

• 前一个数的范围一定是 $[x - p + 1, x - 1]$，$p$ 为最大质因数
• 枚举 $x1$ 判断是否合法

B

• 预处理质数，计算每个数的质因数个数
• 答案为 $2^{cnt}$

C

• 考虑将数分组，且相邻数相除为 $k$, 组内数不可以连续取，递推求解（斐波那契数）
• 观察求出长度为 $i$ 的个数