Linge_Zzzz's Boker

CDQ 分治看了很多次都没学明白，现在学明白了写个博客。 概念 CDQ 分治，旨在处理一系列序列上的统计问题。 序列中，如果特定的元素对之间存在贡献，那么我们可以考虑 CDQ 分治。 具体地，CDQ 分治是这样的： 假设当前在处理 $[l,r]$ 区间内互相的贡献。 令 $m=\lfloor\frac{l+r}{2}\rfloor$，把这个区间分成两部分：$[l,m]$ 和 $[m+1,r]$。 递归处理 $[l,m]$ 和 $[m+1,r]$ 区间内的贡献。 处理 $[l,m]$ 与 $[m+1,r]$ 之间的贡献。 可以看到，这样就能处理每一对之间的贡献。 那么到底是怎么做的呢？？ 三维偏序 有 $n$ 个元素，每个元素有属性 $a_i,b_i,c_i$。求有序对 $(i,j)$ 满足 $a_i\leq a_j,b_i\leq b_j,c_i\leq c_j$ 且 $i\neq j$的数量，元素互异，$a_i,b_i,c_i\leq2\times 10^5$。 不妨先以 $a_i$ 为关键字升序排序，现在条件就变成了 $i\leq j,b_i\leq b_j,c_i\leq c ...

引入相信各位小学都学过容斥原理的三元版本，这里就不多赘述了。 模型我们关注容斥原理的本质，其实就是求多个集合的并的大小。 令 $U$ 为全集，所有的 $S_i\subset U$。 下面把它拓展到 $n$ 元： |\bigcup_{i=1}^n S_i|=\sum_{m=1}^n(-1)^{m-1}\sum_{|a|=m,a_i

？？？神秘性质数数题。 Descr对于一个字符串，若其每个字符出现不超过 $2$ 次，则称其是 $\operatorname{beautiful}$ 的。 共有 $k$ 种字符，字符串 $S$ 长为 $n$，$T$ 长为 $m$，定义 $f(S,T)$ 为 $T$ 在 $S$ 中不重叠出现的次数。求： \sum_S \sum_{T \operatorname{is}\operatorname{beautiful}}f(S,T)Sol看到字符串 $T$ 这么奇怪，肯定先从 $T$ 入手。尝试发掘一下 $T$ 的性质。 注意到 $f(S,T)$ 和字符串匹配的规则有些相似，不妨从 $T$ 的 的 $\operatorname{border}$ 发掘一下。 Observation若 $T$ 有 $\operatorname{border}$，则其有且仅有这一个 $\operatorname{border}$。 简要说明一下，若其有两个或以上的 $\operatorname{border}$，容易发现其第一个字符出现超过 $2$ 次。 所以我们可以把一个 $T$ 唯一地表示为 $wxw$ 的形 ...

选自 SDSC2024 Day1 数论选讲。 Descr给定一个 $h\times w$ 的网格图，从左上角的点 $(0,0)$ 开始，你可以在每个格子选择往下或往右走，走出边界会循环，问哈密顿路径条数。 $h,w \leq 10^6$。 Sol本题解分步讲解。因为较为抽象，建议读题解同时自己画图理解。 Observation #1考虑“哈密顿路径”这一条件。 所谓哈密顿路径，就是不重不漏走每个点恰好一次的路径。 假设有一个点 $(x,y)$ 选择了往下走到 $(x+1,y)$，那么因为每个点只能走一次，所以 $(x+1,y-1)$ 就不能选择往右走到 $(x+1,y)$，只能选择往下走。 假设这个点 $(x,y)$ 选择了往右走，那么 $(x+1,y)$ 这个点只能从 $(x+1,y-1)$ 走过来，即从 $(x+1,y-1)$ 向右走，否则没有点能走到这里。 归纳下去，所有的左下-右上的对角线的方向的选择都相同。 再考虑“循环”这一条件。 假设有一个位于底部的点 $(h-1,y)$ 其选择了往下走到 $(0,y)$，那么 $(0,y-1)$ 就不能向右走，否则会重复走到一个点，所以 ...

引入众所周知，Trie 是维护一堆字符串的数据结构，那么如果我们把数看做二进制字符串，用 Trie 维护，会得到什么呢？ 答案是 01-Trie。 01-Trie 利用贪心思想，能够方便地维护异或最大、最小、第 $k$ 大以及相关信息。 基础操作在大多数 01-Trie 中，我们按照数的二进制位从高到低建立。 插入同普通 Trie。 123456789101112struct node{ int e[2];}t[N*T];int tot=0;void ins(int x){ int p=0; for(int i=T;i>=0;i--){ int c=(x>>i)&1; if(!t[p].e[c])t[p].e[c]=++tot; p=t[p].e[c]; }} 异或最大下面实现一种最常用的操作：查询在这些数中异或值 $x$ 最大的异或值。 我们知道异或时，当两位不相同时为 $1$，否则为 $0$。 现在就有了一个基本思路：尽量在 Tri ...

这是我 OI 生涯中举办的第一场比赛！！1 全部文件下载链接：link。 Sol Accelerator 暴力1 直接枚举即可。 正解 暴力统计 $b\geq 3$ 时的结果，拿 std::map 去重的同时统计这些数里有多少个完全平方数。 考虑到所有的 $a^b\leq n$ 且 $b=2$ 时共有 $\lfloor \sqrt{n} \rfloor$ 种 $a^b$，所以拿上面的结果加上 $\lfloor \sqrt{n} \rfloor$ 再减去统计有多少个完全平方数即可做到不重不漏统计答案。 实现的时候注意不要使用 sqrt，会爆精度，应该使用 sqrtl。 考点解析：sqrtl、枚举、人类智慧。 Kuriko 暴力1 暴力连边跑暴力 Dijkstra。 暴力2 暴力连边跑 01-BFS。 暴力3 建模跑暴力 Dijkstra。 正解 建模跑 01-BFS。 具体地，每个 $u$，从 $u$ 向 $a_u$ 连边，边权为 $0$。 每个 $a_u$ 枚举其为 $0$ 的二进制位 $x$，向 $a_u \operatorname{or} x$ 连边，边权为 $0$。 建图时间复 ...

qyc 讲题汇总。先讲我听懂的。 动态图连通性 题意简述 维护一张点数为 $n$ 的无向简单图，$m$ 次操作，加入或删除一条边及查询两个点是否连通。 $n\leq 5\times 10^3,m\leq 5\times 10^5$。 解法一：线段树分治（离线） 在时间轴上，每条边都有自己存在的时间段。我们在操作的时间轴上建立一棵线段树，每条边插入进其所完全包含的线段树上 $O(\log m)$ 个区间上。 在线段树上进行 DFS，同时维护一个表示连通块的并查集。这个并查集被要求是支持撤销操作的，为此我们使用按秩合并，每次修改时记录 fa 变化的那个点。每当我们进入一个线段树节点时，把节点里的所有边加入到并查集中，离开时撤销掉。当递归到叶子节点时计算询问。 容易证明这是正确的，因为当我们递归到叶子节点的时候，所有包含这一时间点的边都已经被加入到并查集中，同时撤销操作保证了没有包含这一节点的边不在并查集中。 分析一下时间复杂度。单个询问处理 $O(\log n)$，并查集合并 $O(\log n)$，撤销 $O(1)$。因为在线段树上，原来的 $O(m)$ 条边被拆分成了 $O(m\log ...

引入 给你 $n$ 个点的一棵树，每条边有边权。从中选取一些关键结点，你需要切断一些边，使得没有任何关键节点与 $1$ 号点联通，最小化切断边的总边权。 $O(n)$ 做法是显然的。考虑树形 DP。我们设 $f_u$ 为以 $u$ 为根的子树内（不包括 $u$）切断一些边使得没有任何关键结点与 $u$ 联通的边权和最小值。容易得到转移方程。 设 $v$ 是 $u$ 的一个儿子，$w$ 为 $u$ 到 $v$ 的边权。 若 $v$ 是关键结点，$f_u=f_u+w$，否则 $f_u=f_u+\min\{f_v,w\}$。 现在把问题升级一下。$q$ 组询问，每次给定一些关键结点，求答案。所有询问中关键结点个数的和与 $n$ 同阶。 我们把上面的算法跑 $q$ 次，就得到了一个 $O(nq)$ 的算法，这是远远不够的。 但是所有询问中关键结点个数的和与 $n$ 同阶，在关键点数量比较少的时候，总会有一些其他结点是无用的。我们有没有一种方法把这棵树的信息浓缩呢？答案是有的。 虚树 不要被名字吓到。所谓虚树，不过是一个重构树，在这个重构树上进行 DP 和在原树上 DP 是等价的。这个重构树 ...

树的直径 定义 所谓树的直径，就是树上一条最长的链。 注意到这条链不唯一。 我决定在讲解例子的过程中穿插性质。 直径的求法 两次搜索 引理：一棵树上以任意一个点开始的最长简单路径的终点一定是直径两个端点之一。 证明： 若不是端点，可分为两种情况讨论： 第一种，这条路径不与直径相交，则让直径改道过来这条路径显然比原来的直径更长，矛盾。 第二种，这条路径与直径相交，则让直径在交点处顺着这条路径走显然比原来直径更长，矛盾。 得证。 所以我们可以两次搜索。 第一次任选一个点当做起点，找到距离这个点最远的一个点，则这个点一定是直径的其中一个端点。 第二次再把这个端点当做起点，找到另一个端点。 这种方法的好处在于可以求具体方案。但是注意一棵树可能有多条直径，且这种方法不适用于负权边存在的情况。 树形 DP 在树形 DP 中，我们对于每个点维护两个值：在以这个点为根的子树中，从这个点往下走的链的最长长度和次长长度。转移直接由儿子的最长长度加上到儿子的边权即可。 直径就是每个点最长长度和次长长度加起来的最大值。 这种方法可以用于负权边情况。 [SDOI2011] 消防（树网的核 加强版） 题意不再 ...

定义 在一个 DAG（有向无环图中），选择其中的一些简单路径，若图中每个点都恰好在其中一条路径上，则称这些路径是一个路径覆盖。 所有路径覆盖中，路径条数最小的路径覆盖叫做最小路径覆盖。 例如在上图中，$\{\{1\},\{2,3\},\{4,5\}\}$ 是一个路径覆盖，$\{\{1,2,3,4,5\}\}$ 是一个最小路径覆盖，只用了一条路径。 任务是找出 DAG 上的最小路径覆盖，且输出方案。 建模 考虑二分图最大匹配。 我们对原图中每个点 $u$ 拆成两个点，记为左部点 $L(u)$ 和右部点 $R(u)$。 对于原图中每条边 $(u,v)$，连接 $L(u)$ 到 $R(v)$。 则答案为原图中点数减去最大匹配数。 正确性 假设开始时图上的每个点都自成一条路径，我们要做的是尽可能多地把路径合并。 考虑一下路径合并的隐藏条件： 首先，路径合并是可以传递的，简单来说，如果 $x$ 能跟 $y$ 合并，$y$ 能跟 $z$ 合并，那么 ${x,y,z}$ 可以合并成一条路径。所以我们可以只考虑点与点之间的合并关系，再利用传递性求方案。 其次，每条路径只能向一个路径合并，也只能被 ...