题解
深度优先搜索（DFS）
[NOIP2018 提高组] 旅行
题目大意
给定一棵树或基环树，从起点出发，找到一个字典序最小的遍历序列。
题解
可以用 STL set 来存储边，这样字典序排序比较好做。如此，树的部分就直接遍历一遍即可。
考虑基环树的情况，先找到环，然后枚举删除环的每一条边，总复杂度是 $\mathcal{O}(n^2)$ 的。
代码
const int N = 5e4 + 5;
inline ll R …
Jayun 发布于 2023-10-10 10:25:28
00
字典树Kruskal
题面
给定 $n$ 个结点的无向完全图。每个点有一个点权为 $a_i$ 。连接 $i$ 号结点和 $j$ 号结点的边的边权为 $a_i\oplus a_j$ 。
求这个图的 MST 的权值。
$1\le n\le 2\times 10^5$ ， $0\le a_i< 2^{30}$ 。
题解
点权 01 Trie 中，权值最小的边明显是 LCA 最深的两点的边，易知有 $ …
Jayun 发布于 2023-10-08 21:05:38
00
数位动态规划（数位 DP）
题面
给出 $n$ 个数字 $a_1 , a_2 , \ldots , a_n$ ，每次操作可以给其中一个数加上 $2$ 的非负整数次幂。求最少的操作次数，使得这 $n$ 个数相等。
题解
令 $a_i$ 升序，记 $\text{bit}(i)$ 表示 $i$ 二进制中 1 的个数，则要求一个 $x$ 使得
$$\sum_{i=1}^n\text{bit}(x+a_ …
Jayun 发布于 2023-10-08 15:51:13
00
字典树可持久化线段树
题目描述
定义：如果字符串 A 是字符串 B 的后缀，那么称 B 是 A 的 XQ 串。
小奇有 n 个只包含小写字母的字符串，编号为 1-n，表示为 Si。
接下来对于每个串 Si，小奇想知道：对于小奇拥有的 n 个字符串，所有是 Si 的 XQ 串的编号集合(包括 i）中第 Ki 小的编号。
对于 100%的数据 n<=100000，字符串总长<=300000。
题解
考虑处理 X …
Jayun 发布于 2023-10-08 11:57:18
00
线性动态规划（线性 DP）贪心二分答案
题面
题目描述
著名的植物学家 Alice 经过多年的探索，终于找到了传说中的璀璨花。璀璨花的生长速度非常迅猛，如果不加以合适的控制，璀璨花会因为过度内耗而死亡。璀璨花的生长趋势可以用序列 $a$ 表示，Alice 在研读前人对璀璨花的研究后总结出了一个控制序列 $b$ 。Alice 需要让璀璨花的生长趋势尽可能贴合控制序列，这样璀璨花就能尽可能快且安全地生长，以让更多人能欣赏到传说花卉的美 …
Jayun 发布于 2023-10-01 09:10:31
00
几何基础
题目大意
在平面直角坐标系中，有 $n$ 个圆。需要找到一个方向，使得从原点按该方向射出的一条射线，每隔距离 $d$ 为一个点，这些点落在圆的个数最大（同一个圆可以贡献多次）。
$n\leq2\times10^4,5\leq d\leq10.$
思路
考虑一个圆被以原点为圆心、半径为 $k\cdot d$ 的若干个圆交。如下图。
发现每一个在圆内的弧线的贡献都是 $1$ ，那么 …
Jayun 发布于 2023-09-17 16:26:59
00
线性动态规划（线性 DP）Hash
题目大意
记 $m_i=\underbrace{1\cdots1}_{i\text{ times}}$ ，即十进制下 $i$ 个连续的 $1$ 。
现在给定一个正整数 $n$ ，找到一个无限长的整数序列 $(x_1,x_2,\cdots)$ 满足：
$\sum_{i=1}^\infty m_ix_i=n$ 。
最小化 $\sum_{i=1}^\infty i|x_i|$ 。
…
Jayun 发布于 2023-09-17 16:22:39
00
后缀自动机（SAM）
题意
求字符串字典序第 $k$ 大子串（本质不同或位置不同）。
$n\leq 5\times 10^5$
题解
DP 求得结点大小（size），再 DP 求 DAG 子树（或子图？）的大小，像平衡树那样转移即可。
代码
const int N = 1e6 + 10;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
wh …
Jayun 发布于 2023-04-24 17:11:49
11
后缀自动机（SAM）基础线段树
题意
给定一个长为 $n$ 的字符串 $s$ 和 $m$ 个问题，每个问题均有 $a,b,c,d$ 四个参数，求子串 $s[a..b]$ 的所有子串和 $s[c..d]$ 的最长公共前缀的长度的最大值是多少。
$1\le n,m\le 100,000$ 。
题解
SAM 例题。直接算长度太难，考虑二分长度：若二分到长度为 $\mathrm{len}$ ，接着查询子串 …
Jayun 发布于 2023-04-24 11:53:49
00