OI集训 Day9
Content：DP (state, num) Date：2025.7.25 概览 数位 DP 状压 DP 内容 状压 DP 状压 DP，即状态压缩 DP，通常情况下和子集问题挂钩，以二进制的第 iii 位表示集合中的每个子集选还是不选。 有一种 O(3n)O(3^n)O(3n) 的子集枚举方式： [!Note] Code for (int i = 0; i < (1 << n); i++) { for (int j = i; j; j = (j - 1) & i) { // * j 即为 i 的子集 }} 数位 DP 数位 DP，即不是以数字为状态进行动态规划，而是和人一样，对于数字的每个数位作为状态，常见问题为： 常见问题 给定区间 [L,R][L,R][L,R]，求出在这个区间中满足某种条件的数的个数。 例题 洛谷-P1896 互不侵犯 思路 我们定义 dpi,s,jdp_{i,s,j}dpi,s,j 表示第 iii 行的放置状态为 二进制表示下的 sss 时的放置 jjj...
OI集训 Day8
Content：DP (Interval, Tree) Date：2025.7.24 概览 区间 DP 树形 DP 例题 洛谷-P4516 潜入行动 题目大意 题目大意 给定一颗树，要求在树上选取恰好 k\large kk 个节点 (不得重复)，每个选取的节点可以覆盖它的邻居，但是不能覆盖自己本身。要求选取的这 k\large kk 个节点覆盖所有的 n\large nn 个节点。求方案数。 数据范围 n≤105,k≤100\large n \le 10^5, k \le 100n≤105,k≤100。 思路 我们考虑树形动态规划。定义状态 fu,i,0/1,0/1\large f_{u,i,0/1,0/1}fu,i,0/1,0/1 表示以 u\large uu 为根的子树内，选取了 i\large ii 个节点，其中点 u\large uu 放了/不放，被/不被覆盖的方案数。初始状态为： fu,0,0,0=1fu,1,1,0=1\large \begin{aligned} f_{u,0,0,0} = 1 \\ f_{u,1,1,0} = 1 \\ \end{alig...
OI集训 Day7
Content：Competition Date：2025.7.23 T1：宝宝巴士之小猫数数 赛时思路 开始题意理解错了，以为是倒数第二位开始的连续的 000，后面也没有什么新的思路，就用 python 打了个 n≤5000n \le 5000n≤5000 的表，拿了 505050 分的部分分。 正解 其实就是赛时的思路，根据那个方法打表，但是每次只维护前面几位 (根据样例可以知道答案很小)，然后就没有然后了。 T2：宝宝巴士之换一换 赛时思路 以为时分治，每次合并跨过 midmidmid 的区间，维护一个双指针，每次往结果大的方向移动，同时用不在所选区间内的最大值替换所选区间内的最小值，但其实这个贪心是不对的。 正解 其中有一个 Subtask 3 对问题的思考是很有帮助的。 Solution For Subtask 3 我们发现问题的答案是 最长的连续的一的个数 和 最长的连续的二的个数 ×\times× 2 中的最大值。 我们由此受到启发。观察原式 (r−l+1)min{al,al+1,al+2,…,ar}(r-l+1)\min\{a_l, a_{l+1}, a_{...
OI集训 Day6
Content：Data Structures; Date：2025.7.22 概览 可持久化线段树 虚树 具体内容 可持久化线段树 可持久化线段树实现可持久化数组 我们对每一个版本维护一颗线段树，这样显然空间复杂度是 Θ(nm)\Theta(nm)Θ(nm) 的，肯定不对。 接下来我们通过观察可以发现，其实新版本线段树上的很多节点与原线段树 上的节点是重复的，极大地浪费了空间。 我们考虑对那些不用修改的节点进行空间上的优化，具体如下： 假设线段树节点 kkk 维护的区间为 [l,r][l,r][l,r]，其中点为 midmidmid。 我们对新版本新建了一个节点 k′k'k′，接下来分两种情况讨论： 如果区间 [l,mid][l, mid][l,mid] 包括我们要修改的位置，则 lc(k′)=cnt+1lc(k') = cnt + 1lc(k′)=cnt+1，rc(k′)=rc(k)rc(k') = rc(k)rc(k′)=rc(k)。即我们继承不用修改的节点。 对于区间 [mid+1,r][mid + 1, r][mid+1,r] 同...
OI集训 Day5
Content: Problem on Tree Date：2025.7.21 概览 树的重心 树上启发式合并 树链剖分 左偏树 点分治 具体内容 树的重心 定义 树的重心 树的重心是满足如下条件的点 uuu: 树上不存在其他节点 vvv，使得 max{siz(sonv)}<max{size(sonu)}\max\{\operatorname{siz}(son_v)\} < \max\{\operatorname{size}(son_u)\}max{siz(sonv)}<max{size(sonu)}。 性质 树的重心 GGG 有如下性质： 树的重心的性质 当以 GGG 为根节点时，不能存在 vvv 满足 max∀v∈son(u){size(v)}>N2\max_{\forall v \in \operatorname{son}(u)}\{\operatorname{size}(v)\} > \frac{N}{2}max∀v∈son(u){size(v)}>2N (NNN为整棵树的大小)。反之亦然。 树中所有...
OI集训 Day4
Content：Math Date：2025.7.20 内容 矩阵 线性方程组 行列式 矩阵树定理 线性基 具体内容 矩阵 矩阵定义 定义 将一些元素排列成若干行，每行放上相同数量的元素，就是一个矩阵 (Matrix)。 对于矩阵 AAA 的第 iii 行，第 jjj 列，我们记作 ai,ja_{i,j}ai,j 或 aija_{ij}aij。 对于举证 Am×nA_{m \times n}Am×n，如果 m=nm = nm=n，则我们称矩阵 AAA 为方阵。 矩阵基本操作 矩阵加法：对于矩阵 Am×nA_{m \times n}Am×n, Bm×nB_{m \times n}Bm×n, 我们定义矩阵加法为：Ci,j=Ai,j+Bi,j C_{i,j} = A_{i, j} + B_{i, j} Ci,j=Ai,j+Bi,j 即矩阵对应位置上的元素之和。 注意 只有当两个矩阵的大小相同时，才可以进行矩阵加法。 标量乘法：对于矩阵 Am×nA_{m \times n}Am×n 和标量 xxx, 我们定义矩阵的标量乘法为： Ci,j=Ai...
OI集训 Day3
Content： Data structs Date：2025.7.19 内容 三维偏序问题 CDQ分治 整体二分 分块 莫队算法 具体内容 三维偏序问题 问题描述 给定一些三元组 (ai,bi,ci)(a_i, b_i, c_i)(ai,bi,ci)，询问对于三元组 (aj,bj,cj)(a_j, b_j, c_j)(aj,bj,cj)，有多少个三元组满足 ai≤aja_i \le a_jai≤aj 且 bi≤bjb_i \le b_jbi≤bj 且 ci≤cjc_i \le c_jci≤cj。 首先对于这个问题，我们考虑先去重，然后排序。排序规则如下： 如果 ai≠aja_i \ne a_jai=aj，则返回 ai<aja_i < a_jai<aj 如果 bi≠bjb_i \ne b_jbi=bj，则返回 bi<bjb_i < b_jbi<bj 否则返回 ci<cjc_i < c_jci<cj 这样我们就把 ai<aja_i < a_jai<...
OI集训 Day2
Content：Segment Tree Date：2025.7.18 主题 线段树进阶 关于线段树 区间操作 对于区间开根号我们可以记录最大值和最小值，然后维护极差，由此将区间开根号转化为区间加和区间覆盖问题，减小修改操作的复杂(度，均摊后复杂度为 Θ(nlognlog2V)\Theta(n \log n \log^2 V)Θ(nlognlog2V)。（题目：HDU 5828） 对于区间取模的操作，我们依然记录最大值，对于 max<Pmax < Pmax<P 的区间不做修改，从而降低复杂度。（题目：CodeForces 438D） 对于区间 gcdgcdgcd 操作，我们可以对原数组进行差分，得到差分数组 ddd，而区间 [l,r][l, r][l,r] 的 gcdgcdgcd 即为 gcd(al,dl+1,dl+2,…,dr)gcd(a_l, d_{l + 1}, d_{l + 2}, \dots, d_{r})gcd(al,dl+1,dl+2,…,dr)。（题目：洛谷 P10463） 二维数点问题 二维数点问题是在一个平面中，有若干...
