TH911 Blog

动态 DP 详解

DDP | 例题：洛谷P4719,P4513 SPOJ GSS3

例题链接。本文参考了部分资料，参见文末。如果没有特殊声明，本文中所有的矩阵乘法均为广义矩阵乘法，请不要混淆。 DDP（动态 DP）可用于解决一类带修改操作的 DP 问题。一般用来解决树上带有点（边）权修改的 DP 问题。引入以较为简单的最大子段和问题来引入。例题：SPOJ GSS3 - Can you answer these quer...

Posted by TH911 on July 26, 2025

树状数组优化 DP

前/后缀最值

树状数组优化 DP 常规的区间和就不讨论了，本文主要讨论树状数组维护前后缀最值。 Acwing3662 最大上升子序列和 [NOIP 2013 提高组] 花匠树状数组可以用于维护前后缀最值。维护前缀最大值： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 struct bitPre{ int t[N+1...

Posted by TH911 on July 25, 2025

NOIP 二十年 DP 训练总结

2005 至 2024 NOIP 动态规划真题

持续更新中，对于较为简单的题目，会直接给出题解。对于较为复杂的题目，会给出核心摘要及详细题解的链接。题目主要来源于[此处](https://www.luogu.com.cn/problem/list?type=luogu&page=1&tag=3,129,139,141,144,152,323,435,443,444,4...

Posted by TH911 on July 25, 2025

题解：[ARC170C] Prefix Mex Sequence

AtCoder ARC170C

题目传送门题意分析对于 $s_i=1$ 的 $a_i$，显然 $a_i$ 时由 $a_1,a_2,\cdots,a_{i-1}$ 确定的唯一的数。当 $n\leq m$ 时，最大的 $\operatorname{mex}$ 的值一定不会超过 $m$。故此时所有 $s_i=0$ 的 $a_i$ 都可以在 $\set{0,1,\cdots,m}\setminus\set{\o...

Posted by TH911 on July 24, 2025

题解：[ROIR 2025] 寻找宝藏

洛谷P11700 | DP

题目传送门题意分析本文中记 $x_i$ 为第 $i$ 列的扫描结果，即 $x_i$ 为原题中 $b_i$。同时，以下推导均不考虑取模。 DP 状态设计注意到 $k\leq7$，且是计数类问题，因此考虑与 $k$ 有关的涉及状压的 DP。如图，扫描仪的扫描区域其实就可以视作一个类似于三角形的区域在图上向右滑动。而第 $i$ 列的扫描结果与第 $i-1$ 列的扫描结...

Posted by TH911 on July 23, 2025

题解：[POI 2015] LAS

洛谷P3584 | DP

题目传送门题意分析发现， $c_i$ 的限制比较多，因此针对此进行 DP。设 $\textit{dp}{i,j},j\in\set{1,2,3,4}$ 表示食物 $i$ 的状态为 $j$ 的合法状态是从 $\textit{dp}{i-1,\textit{dp}{i,j}}$ 转移得来。同时，规定 $\textit{dp}{i,j}$ 有值表示合法，没有值表示不合法。那...

Posted by TH911 on July 23, 2025

题解：Sam 数

洛谷P2106 | 矩阵快速幂优化 DP

题目传送门朴素数位 DP 一个显然的 DP：设 $\textit{dp}_{i,j},i\in[1,k],j\in[0,9]$ 为 $i$ 位且最高位为 $j$ 的 Sam 数的个数。则有： \[\textit{dp}_{i,j}=\sum_{\max(j-2,0)}^{\min(j+2,9)}\textit{dp}_{i-1,j}\] 最终答案 $\textit{an...

Posted by TH911 on July 22, 2025

题解：[HAOI2011] Problem b

P2522 | 莫比乌斯反演

题目传送门题意分析首先写出答案： \[\textit{ans}=\sum_{i=a}^b\sum_{j=c}^d[\gcd(i,j)=k]\] 这种涉及到 $\gcd$ 的题目，一般都考虑莫比乌斯反演。不妨令 $b<d$，有： \[\begin{aligned} \textit{ans}&=\sum_{i=\lceil\frac ak\rceil}^{...

Posted by TH911 on July 19, 2025

题解：Square Subsets

CF895C | 状压DP

题目传送门题意分析发现一个神奇的东西：$a_i\leq70$。值域如此之小，一定可以利用。因此考虑与值域有关的做法。寻找完全平方数，则其所有质因子的指数均为偶数。可以发现，$[1,70]$ 中的质数有且仅有 $19$ 个，可以考虑从此方面入手。考虑影响是否为完全平方数的仅仅是质因子的指数的奇偶性，因此可以考虑状压 DP。记第 $i$ 个质数为 $p_i,p_1...