MiQiu

ZJ2020E - Easy DP Problem 1. 题面梗概 中译中: 给定一个长度为 nnn 的序列 aaa。定义一个 DP 过程： dp[i][j]={0(i=0)i2+dp[i−1][j](i>0,j=0)i2+max⁡(dp[i−1][j],dp[i−1][j−1]+b[i])(i>0,j>0)dp[i][j] = \begin{cases} 0 & (i

ABC441F - Must Buy 1. 题面梗概 给定 NNN 个物品和预算 MMM，每个物品有其价格 PiP_iPi​ 和价值 ViV_iVi​。 在保证总价值最大化的前提下，判断每个物品属于哪一类：必选 (CateA)、必不选 (CateC)、或者可选可不选 (CateB)。 2. 逻辑推导 乍一看，这不背包问题吗？只有一个？直接 0/1 背包启动！！！ 仔细品了品，发现问题不简单，简单的

[L4] 树状数组 1. 生态位 识别: 题目涉及“动态单点/区间修改”与“动态前缀/区间查询”。 信息满足结合律且可差分（如和、异或、乘积）。 不能维护( Max/Min )。 地位: 基础数据结构。相比线段树更轻量，常用于作为更复杂算法（如 CDQ 分治、扫描线）的底层贡献统计工具。 用途: 可以通过 O(log⁡N)O(\log N)O(logN) 的复杂度解决动

CF2162E - Beautiful Palindromes 1. 题面梗概 中译中: 给定一个长度为 nnn 的数组 aaa，你需要向其末尾追加 kkk 个范围在 [1,n][1,n][1,n] 的数。目标是使得最终数组中的回文子数组的数量最少。 2. 逻辑推导 从回文串的性质入手： 长度为 111 ：x | 长度为 222 ：xx | 长度为 333 ：xxx, xyx | 长度为 44

CF2163B - Siga ta Kymata 1. 题面梗概 给定一个排列 ppp。你可以进行最多 5 次操作：选定 l,rl,rl,r，将索引在 (l,r)(l,r)(l,r) 之间且其值在 (Pl,Pr)(P_l,P_r)(Pl​,Pr​) 之间的所有位置染色。现在给定一个目标染色需求串，要求写出一个合法的 555 步以内的构造方案。 2. 逻辑推导 观察公式 l<i<rl &

[L4] 构造策略 1. 生态位 识别: 题面要求输出满足某种约束的“任意一种方案”。 解空间巨大（如 2N2^N2N 或 N!N!N!），标准搜索/动态规划因复杂度过高而“失效”。 存在极其苛刻的边界限制，暗示了解的唯一性或某种强规律性。 地位: 偏数学构造思维，一般作为“掀桌用”。它不搜索解，它生成解。 用途: 绕过复杂的计算过程，直接利用数学性质（如奇偶性、对称性

[L4] 贪心策略 1. 生态位 识别: 目标函数为单峰或具有明显的局部单调性。 决策序列具有无后效性：当前的决策不会改变过去，也不受未来尚未发生决策的影响。 存在某种“排序”或“结构”，使得局部最优可以直接推导出全局最优。 定义: 在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致全局最优的算法范式。 地位: 是一种算法直觉。贪心不需要维护复杂的 DP 维

[L4] 排序体系 1. 生态位 识别: 题面要求统计“逆序对”或“偏序关系”。 需要对带有多个权值的对象进行“稳定排序”。 在 O(N)O(N)O(N) 期望时间内查询第 KKK 大数。 地位: 基础算法，本质是消除序列中的 逆序对。 用途: 归并排序: 解决“偏序计数”（如统计逆序对），是 CDQ 分治的原型。 快速排序: 原地排序，同样是基于分治的 Nlog⁡NN \log NNl

CF2183B Yet Another MEX Problem 1. 题面梗概（翻译） 给了一个长度为 nnn 的数组 aaa，以及 kkk。 需要进行 n−k+1n - k + 1n−k+1 次操作，计算出剩余 k−1k - 1k−1 个序列的最大 MEXMEXMEX。 操作为：找到大小为 kkk 的窗口，使得该窗口的 MEXMEXMEX 最大，然后删去其中一个数。 * MEX (minimum

CF2183D1 Tree Coloring (Easy Version) 1. 题面梗概（翻译） 给定一棵 nnn 个节点的树，求让所有节点染色的最小操作数。 操作限制：每次染色中，不能有两个节点连接，或者深度相同。 2. 逻辑推导 由于题目要求最小操作数，不妨从答案的下界入手。 什么节点不能同时染色呢？ 深度相同 或者 父子节点。 所以一种下界显然就是 max⁡(cnti)\max(cn