Thy's Blog

树链剖分 树链剖分的基本思想 通过将树分割成链的形式，从而把树形变为线性结构，减少处理难度。 树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作「实链剖分」），大多数情况下（没有特别说明时），「树链剖分」都指「重链剖分」。 树链有如下几个特征： 一棵树上的任意一条链的长度不超过 log⁡2n\log_2 nlog2​n，且一条链上的各个节点深度互不相同（相对于根节点而言）。 通过特殊的遍历方式，树链剖分可以保证一条链上的 DFS 序连续，从而更加方便地使用线段树或树状数组维护树上的区间信息。 重链剖分 重链剖分的基本定义 重链剖分，顾名思义，是一种通过子节点大小进行剖分的形式，我们给出以下定义： 重子节点：一个非叶子节点中子树最大的子节点，如果存在多个则取其一。 轻子节点：除了重子节点以外的所有子节点。 重边：连接任意两个重儿子的边。 轻边：除了重边的其他所有树边。 重链：若干条重边首尾相连而成的一条链。 我们将落单的叶子节点本身看做重子节点，不难发现，整棵树就被剖分成了一条条重链。 需要注意 ...

这里是一份不怎么优雅的暴力模拟。 Solution 由于只有三个人参与了分配，通过排列原理可知可能的顺序有 3!3!3! 种可能，通过定义函数对每种可能模拟即可，一旦合法输出相应方案。 AC Code 123456789101112131415161718void solve(){ sum = 0, aver = 0; // 记录总数和平均值 cin >> n; for (int i = 1; i <= 3; i ++) for (int j = 1; j <= n; j ++) cin >> f[i][j]; // 使用二维数组方便后面的函数分讨 for (int i = 1; i <= n; i ++) sum += f[1][i]; aver = (sum + 2) / 3; for (int a = 1; a <= 3; a ++) for (int b = 1; b <= 3; b ++) f ...

Before 由于数的位数很大，我们用 ∑i=0nai×10i{\textstyle \sum_{i = 0}^{n} a_i \times 10^i}∑i=0n​ai​×10i 来表示一个 n+1n + 1n+1 位的数，那么 D(num)=∑i=0naiD(num) = {\textstyle \sum_{i = 0}^{n} a_i}D(num)=∑i=0n​ai​​ 就是这个数的数位之和。 Solution 敲份暴力代码不难发现以下结论： 对于任意的 num∈[10l,10r)num \in \left [ 10^l, 10^r \right )num∈[10l,10r)，当且仅当 num×knum \times knum×k 的任意一位上没有发生进位，满足 D(k×num)=k×D(num)D(k \times num) = k \times D(num)D(k×num)=k×D(num)。 证明：因为 D(num)=∑i=0naiD(num) = {\textstyle \sum_{i = 0}^{n} a_i}D(num)=∑i=0n​ai​，k×D(num)=∑i= ...

题目大意 给定一个长度为 nnn 的数列 aaa，求 ⊕i=1n⊕j=i+1n(ai+aj)\oplus_{i = 1}^{n} \oplus_{j = i + 1}^{n} (a_i + a_j) ⊕i=1n​⊕j=i+1n​(ai​+aj​) 其中 1≤n≤4×1051 \le n \le 4 \times 10^51≤n≤4×105，∀i,1≤i≤n,1≤ai≤107\forall i,1 \le i \le n,1 \le a_i \le 10^7∀i,1≤i≤n,1≤ai​≤107。 Solution 简单的双重暴力显然是会超时的，问题的关键在于如何将两重循环减少一层。 对于异或等位运算操作，其特殊的性质在于按位运算，即每一位的影响不会改变下一层。 因此不难想到将答案二进制后的每一位进行讨论，最后统计答案。 对于第 kkk 位： 讨论两个数之和的二进制表示在第 kkk 位上是否为 111，根据加法的性质，我们只需要得知这两个数的前 kkk 位是多少。 定义数组 bbb，对于 ∀bi\forall b_i∀bi​，都有 b_i \gets a_i \and (2 ^ {k ...

Solution 一道博弈题，从操作的性质方面入手。 对于依次操作的位置，受到影响的就是其两边的硬币，无非分为以下几种情况： 两边都是 U，删去元素后两边都变成 D，U 的个数少了 333个（包括操作的那一个）。 一边是 U，一边是 D，操作后 U 的个数少了 111 个。 两边都是 D，操作后 U 的个数增加了 111 个。 不难发现无论怎么操作，U 的个数的奇偶性始终不会改变。对于最后一种操作，如果 U 的个数便为 000，那么游戏结束。 我们可以统计出初始状态 U 的个数，如果 U 为奇数，则 Alice 获胜，否则 Bob 获胜。 AC Code 12345678void solve(){ int res = 0; cin >> n >> s + 1; for (int i = 1; i <= n; i ++) res += s[i] == 'U'; cout <<( (res & 1) ? "YES\n" : "NO\n&qu ...

题目大意 给定一个长度为 nnn 的序列 aaa，花费不同代价进行一下若干操作： 选择其中一个元素 aia_iai​（0≤i<n0 \le i \lt n0≤i<n） 增加一，花费 ppp 的代价。 选择其中一个元素 aia_iai​（0≤i<n0 \le i \lt n0≤i<n） 删除，花费 qqq 的代价（序列长度不可为 000）。 选择其中两个元素 ai,aja_i,a_jai​,aj​（0≤i<j<n0 \le i \lt j \lt n0≤i<j<n）进行交换，花费 rrr 的代价。 最小化代价，使得 ∃k0(0≤k0<n)\exists k_0(0 \le k_0 \lt n)∃k0​(0≤k0​<n)，将子序列 a0∼ak0−1a_0 \sim a_{k_0 - 1}a0​∼ak0​−1​ 拼接在原序列后端，当前序列任意前缀和非负。 Solution 定义 sumsumsum 表示整个序列元素之和，不难看出，对于任意一个序列，若 sum≥0sum \ge 0sum≥0，必然至少存在一个 k0k_0k0​ 使 ...

有向图的强连通分量 定义 对于一张有向图 G=(V,E)G = (V, E)G=(V,E)，对于两点 u,v∈Vu,v \in Vu,v∈V，都存在一条路径可以使得 uuu 达到 vvv，vvv 也可以达到 uuu，则称该两个点是互相可达的。 如果一张有向图上的任意两个节点之间可以互相可达，则称这张图是 强连通的（Strongly Connected）。 对于一张子图 H∈GH \in GH∈G，并且不存在其他的连通图 FFF 使得 H∉F∈GH \notin F \in GH∈/F∈G，则称子图 HHH 是有向图 GGG 的一个 强连通分量（Strongly Connected Component，SCC），叫做极大的连通分量。 应用 对于一个较为复杂的图论问题中，利用强连通分量的缩点技巧，将每一个强连通分量中的所有点看作一个点，最终使得图转化为 有向无环图（DAG），大大的减少了时间复杂度和解题难度。 Tarjan 算法 DFS 生成树 对于一张图的深度优先遍历，根据节点的先后遍历顺序，我们可以生成出一棵树，这棵树即为 DFS生成树，它的性质有如下几点： 深度优先遍历的第一个点 ...

图的存储与遍历 直接存边法 做法 建立三个数组 u[N]，v[N]，w[N]，对于每一次读入的起点，出点和权值存储即可。 初始化 12struct Edge { int u, v, w; };vector<Edge> graph; 存储 1234void add(int a, int b, int c){ graph.push_back({a, b, c});} 遍历 123456789void dfs(int ver){ if (vis[ver]) return; vis[ver] = true; for (auto t : graph) if (t.u == ver) dfs(t.v);} 复杂度 查询两点之间是否连通：O(m)O(m)O(m)。 遍历一个点所有出边：O(m)O(m)O(m)。 遍历整张图：O(n×m)O(n \times m)O(n×m)​。 适用于最小生成树 Kruskal 算法。 邻接矩阵 做法 ...

最近公共祖先（LCA） 定义 最近公共祖先（Lowest Common Ancestor）简称 LCA。对于一个树上的两个节点的最近公共祖先，是这两个点中的公共祖先里面离根最远的一个。性质可见 OI Wiki。 向上标记法 过程 在两点中取得深度较大的一个点，让它不停的向上跳，同时标记所经过的每一个点，直到根节点，接着让另一个点不断向上跳，跳到的第一个被标记的点就是这两个点的 LCA。 时间复杂度 预处理树的深度的时间复杂度为 O(n)O(n)O(n)，单次查询的时间复杂度最坏情况下为 O(n)O(n)O(n)。 倍增算法 过程 我们可以定义一个数组 prei,kpre_{i, k}prei,k​ 表示编号为 iii 的点向上跳 2k2^k2k 次所到达的点。不难看出 prei,0pre_{i, 0}prei,0​ 表示的是节点 iii 的父亲。对于任意的 k≥1k \ge 1k≥1，prei,kpre_{i, k}prei,k​ 都相当于连续上跳两次 2k−12^{k - 1}2k−1，满足以下的递推式： prei,k=preprei,k−1,k−1pre_{i, k} = pre_ ...

解题思路 先看到第一个条件 ai+aj≡0 (mod x)a_i + a_j \equiv 0\ ({\rm mod}\ x)ai​+aj​≡0 (mod x)，可以推出如下性质： ai mod x+aj mod x≡0 (mod x)a_i \ {\rm mod} \ x + a_j \ {\rm mod} \ x \equiv 0 \ ({\rm mod} \ x) ai​ mod x+aj​ mod x≡0 (mod x) 这样我们就可以在范围为 0∼x−10 \sim x - 10∼x−1 中查找满足条件的值，及对于每一个 aia_iai​，符合条件的 aja_jaj​ 为 (x−(ai mod x)) mod x(x - (a_i \ \rm mod \ x)) \ \rm mod \ x (x−(ai​ mod x)) mod x 而对于条件 ai−aj≡0 (mod y)a_i - a_j \equiv 0\ ({\rm mod}\ y)ai​−aj​≡0 (mod y)，只需要让 aia_iai​ 和 aja_jaj​ 同余即可。即： ai≡aj (mod y)a_i ...