MiQiu

[L4] 线性状态动态规划 线性状态 DP 指一类具有自然处理顺序的动态规划。状态通常描述某个有序过程已经处理到哪里，并从更早的状态向后递推。 “线性”修饰的是状态 DAG 的展开方式，而不是状态数组的维数，也不代表时间复杂度一定是 O(n)O(n)O(n)。 题目中的处理顺序可能来自：序列或时间轴上的先后关系，两个序列各自处理到的位置，网格中的坐标或步数，以及区间长度、拓扑序等人为构造的递推

按时间整理随笔、信笺、总结与游记。

G - 221 Subsequence 1. 题面梗概 中译中：定义一种 “221 序列” ，每个数字 xxx 必须连续出现恰好 xxx 次。给一个长度为 NNN 的数组 AAA，求其中有多少个不同的 221 子序列。 N≤5×105N \leq 5 \times 10^5N≤5×105，答案对 998244353998244353998244353 取模。 2. 逻辑推导 221 序列的本质

F - Reachable Set 2 1. 题面梗概 中译中：给一个有向图。对于每一个 k∈[1,N]k \in [1, N]k∈[1,N]，问最少删掉多少个点，能保证从 111 号点出发，无论怎么走都走不出 {1,…,k}\{1, \dots, k\}{1,…,k} 。 N,M≤3×105N, M \leq 3 \times 10^5N,M≤3×105 2. 逻辑推导 给定 NNN 次查询

[L3] 降维技巧 一、单调性相关 双指针 双指针：是一种使用两个指针来维护一段序列区间的方法，可以解决涉及 “连续区间” 的寻找或统计。 核心原理：队列，右指针增加相当于入队，左指针增加相当于出队。 相关例题：P1638 逛画展 | P3143 钻石收藏家 单调栈 单调栈：是一种内部元素具有单调性的栈，可以解决求 “以某个值为最值的最大区间” 等问题。 核心原理：单调性

E - Multiple-Free Sequences 1. 题意梗概 给定一组 M,A,BM, A, BM,A,B，对于所有 0≤x,y≤M−10 \leq x, y \leq M - 10≤x,y≤M−1，统计有多少对 (x,y)(x, y)(x,y) 满足条件： 条件：序列中不包含 MMM 的倍数。 序列：s1=x,s2=y,sn=Asn−1+Bsn−2s_1 = x, s_2 = y, s

最短路体系 题目 P5304 旅行者 多源最短路的应用，染色法 / 二进制分组。 P9751 旅游巴士 类同余最短路，状态扩展的最短路问题。 一、单源最短路 Dijkstra Dijkstra：一种求解单源最短路径的算法．无法处理 有负权图。 核心原理：贪心。每次锁定当前代价最小的点，它一定是最优的。 复杂度：朴素 O(n2+m)O( n^2 + m )O(n2+m)，堆优化 O(

分治思维 1. 生态位 分治 把一个复杂的问题细分成若干结构相同但规模更小的子问题，然后将每个子问题的解合并起来，就得到了复杂问题的解。 地位：分解问题的一种思维方式。 识别： 可以把原问题划分为多个无关的子问题，这里的划分一般都是人为给定的。 子问题的答案可以高效合并，也就是知道了子问题的答案可以高效计算其对全局的答案会产生什么影响。 当前问题的答案可以高效求出，在这里