小明の雜貨鋪

char ascii 0 48 9 57 A 65 Z 90 a 97 z 122 经典字典树 主机场 给定一组字符串 s1,s2,⋯ ,sns_1,s_2,\cdots,s_ns1​,s2​,⋯,sn​，任选 kkk 个 sa1,sa2,⋯ ,sak (ai≠aj)s_{a_1},s_{a_2},\cdots,s_{a_k}\ (a_{i}\ne a_{j})sa1​​,sa2​​,⋯,sak​​ (ai​=aj​)，最小化 max⁡1⩽i,j⩽k,i≠jlcp⁡(sai,saj)\max\limits_{1 \leqslant i,j \leqslant k,i\ne j}^{}\operatorname{lcp}(s_{a_i},s_{a_j})1⩽i,j⩽k,i=jmax​lcp(sai​​,saj​​)。其中 lcp⁡(p,q)\operatorname{lcp}(p,q)lcp(p,q) 是字符串 ppp 和字符串 qqq...

Manacher Algorithm Find the longest substring which is palindrome. 在搜索到 iii 时， cc,ll,rr 已经找到的右边界最大的回文串的中心、左端和右端。 p[i] 以 iii 为中心的最长回文串长度。如果 iii 在最长回文串之中，p[i] 至少是它对称位置的 p[mirror]。利用此性质快速计算 p[i]。 123456789101112131415161718vector<int> manacher(const string& s) { string t = "#"; for (auto c : s) t += c, t += '#'; const int n = t.size(); vector<int> r(n);  // 存储每个字符作为中心的最长回文子串的半径 for (int i = 0, j = 0; i < n; i++) { if (2...

两次 DFS 求树直径 时空复杂度 Θ(n)\Theta(n)Θ(n)。 123456789101112131415161718192021vector<int> p(n), path;auto find = [&](int s) { vector<int> dep(n, -1); auto dfs = [&](this auto&& dfs, int u) -> void { for (auto v : E[u]) { if (~dep[v]) continue; dep[v] = dep[u] + 1; // 如果带点权 dep[v] = dep[u] + val[v]; // 如果带边权 dep[v] = dep[u] + w; p[v] = u; dfs(v); } }; ...

判断无根树是否同构，时间复杂度 Θ(∑n)\Theta\left(\sum n \right)Θ(∑n)。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;mt19937_64 rng{ chrono::steady_clock::now().time_since_epoch().count() };const int N = 3e5 + 8;ull hsh[N];int main() { for (int i = 0; i < N; i++) { hsh[i] = rng(); ...

树链剖分 把一棵树分割成若干条链，以便于维护（路径、子树）信息。 重链剖分 重链剖分 (Heavy Path Decomposition) 从树上每个 轻节点 出发，不断向下走 重边，构成一条链。任意点恰好在一条重链中。任意点到根的路径为 Θ(log⁡n)\Theta(\log n)Θ(logn) 条重链和轻边交替形成。 使用两次 DFS 完成重链剖分，时空复杂度 Θ(n)\Theta(n)Θ(n)。 若 u,vu,vu,v 在同一条链上，LCA 是深度较小的那个节点；否则，将链头深度较大的节点跳转到其链头的父节点上，直至两点在同一条链上。复杂度 Θ(n)−Θ(log⁡n)\Theta(n) - \Theta(\log n)Θ(n)−Θ(logn)。 回忆 树的 DFS 序：每个节点在 DFS 中的进出栈的时间序列。每棵子树的 DFS 序都是连续的，且子树上根节点 DFS 序最小；而且，如果优先遍历重子节点，那么同一条链上的节点的 DFS 序也是连续的，且链头节点 DFS 序最小。因此，uuu 的子树上所有节点的编号介于 dfsn[u] 和 dfsnR[u] 之间，其中...

二叉树 先序遍历：先遍历根节点，然后遍历左节点，最后遍历右节点 中序遍历：先遍历左节点，然后遍历根节点，最后遍历右节点（大概可以理解为把树平面投影至二维从左到右） 后序遍历：先遍历左节点，然后遍历右节点，最后遍历根节点 树上差分 Adjacent Difference on Tree 问题 每次操作将树上 u→vu\to vu→v 路径上的所有点权增加 ddd，求每个点的点权。 思路 用类似前缀和的思想存储树上的点权。用 val[p] 存储 ppp 节点上方的点权增加值，对于上述操作，按差分思想，只需 12val[u] += d; val[v] += d;val[lca(u,v)] -= d; val[p[lca(u,v)] -= d; 复原时，从根节点开始一步步累加。 1234567void dfs2(int u, int p = 0) { for (auto& v : E[u]) { if (v == p) continue; dfs2(v, u); val[u]...

树具有天然的合并性质，即某节点的子树信息全部来自于它子节点的子树信息。因此先计算子节点，再计算父节点，在树上 DFS 的过程中，将子树的信息合并到父节点上。 线段树合并暂时不支持区间修改。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667template<class info>struct SMT { int L, R, pcnt; vector<info> t; vector<int> ls, rs; vector<int> rt; SMT() { init(0, 0); t.resize(N << 2); ls.resize(N << 2); rs.resize(N << 2); ...

在树上，我们可以任选一个节点作为根节点，从而定义出每个节点的深度和每棵子树的根。 在 DP 的状态表示中，第一维通常是节点编号，第二维代表状态基 。大多数时候，我们采用 递归 的方式实现树形动态规划。对于每一个节点 xxx，先递归它的每一个子节点上进行 DP ，在 回溯时，从子节点向节点 xxx 进行状态转移。 有根树的树形 DP 树背包 有根树，有点权。mmm 元点集 SSS 满足：若子节点 ∈S\in S∈S，则父节点 ∈S\in S∈S。最大化 SSS 点权和。 123456789101112int n, m, w[N], dp[N][M];auto dfs = [&](this auto&& dfs, int u) -> void { dp[u][1] = w[u]; for (auto& v : E[u]) { dfs(v); for (int k = m; k >= 1; --k) { for (int i = k; i...

DSU01 - Find by Optimized Path Compression 路径压缩优化 12345678910111213141516171819202122232425262728struct DSU { vector<int> p, siz; DSU(int n) : p(n + 1), siz(n + 1, 1) { iota(p.begin(), p.end(), 0); } int find(int x) { while (x != p[x]) x = p[x] = p[p[x]]; // 路径压缩 return x; } bool same(int x, int y) { return find(x) == find(y); } bool uno(int x, int y) { x = find(x), y =...

博弈 CF1991E. Coloring Game (1900) 有一个由 nnn 个顶点和 mmm 条边组成的无向图。每个顶点可以用三种颜色之一着色。初始时，所有顶点都未着色。 Alice 和 Bob 正在玩一个包含 nnn 轮的游戏。在每一轮中，都会发生以下两个步骤： Alice 选择两种不同的颜色。 Bob 选择一个未着色的结点，并用 Alice 选择的两种颜色之一为其着色。 如果存在连接两个相同颜色结点的边，则 Alice 获胜。否则 Bob 获胜。给你这个图。决定想扮演哪位玩家并赢得游戏，然后与交互库玩这个游戏。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475void eachT() { int n, m; cin >> n >> m; ...