Solutions
Linear Dynamic Programming (Linear DP)Polar Sort
Satanic Panic
收录在 u 群漫游记，详见那，这里放代码。
代码
const int N = 310;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '- …
Jayun 发布于 2023-10-12 09:41:23
00
Adaptive Algorithm
k 部图判定
题面
正在打集的 Displace_ 瞅了一眼U群，发现大家在讨论 NPC 问题，看着集成战略的地图，他突然想到了一个经典 NPC 问题：图染色。
经典的图染色问题是一个 $n$ 个点 $m$ 条边的无向连通图，用 $k$ 种颜色来给每个点染色，使得任意有边连接的两个点颜色不同，构造一个方案。
$k=1$ 是简单的，当 $k=2$ 时问题的难度就骤增了，所以仁慈的 …
Jayun 发布于 2023-10-11 16:09:17
00
Largange Interpolation Polynomial
tyvj 1858 XLkxc
题意
给定 $k,a,n,d$ 。定义：
$$f(n)=\sum_{i=1}^ni^k
$$
$$g(n)=\sum_{i=1}^nf(i)
$$
求 $\left(\sum_{i=0}^ng(a+id)\right)$ 在模 $1234567891$ 意义下的值。
题解
嗟乎！逝者如流，滚滚而去！已经忘记多项式了。
总之，根据 CF622F， $f(n) …
Jayun 发布于 2023-10-10 21:16:27
00
Constructive Algorithm
游戏
题面
Alice 和 Bob 又在一起在玩游戏，这次游戏的规则是：
Alice 先手，Bob 后手，轮流进行操作，共有 $m$ 轮操作，有一个集合初始为 $S=\{a_1,a_2,\cdots,a_n\}$ 。
第 $i$ 轮操作有一个参数 $b_i$ ，当前轮的操作者有以下两个选择：保留 $S$ 中所有是 $b_i$ 倍数的数字，或者保留 $S$ 中所有不是 $ …
Jayun 发布于 2023-10-10 15:09:13
00
TarjanDisjoint Set
连通块
题面
小 X 有一张 $n$ 个节点的图，每个节点有一个点权。但让小 X 感到生气的是，这张图上并没有任何的边，于是他决定钦点一些边。
小 X 喜欢 gcd 和合数，所以小 X 的钦点规则与 gcd（最大公约数）和合数有关。具体来说，对于 $2$ 个点，如果它们点权的最大公约数为合数，那么 小 X 就会钦点它们之间连一条边。
小 Y 看到了小 X 幼稚的行为，决定把他批判一番。他知 …
Jayun 发布于 2023-10-10 11:12:47
00
Depth First Search (DFS)
[NOIP2018 提高组] 旅行
题目大意
给定一棵树或基环树，从起点出发，找到一个字典序最小的遍历序列。
题解
可以用 STL set 来存储边，这样字典序排序比较好做。如此，树的部分就直接遍历一遍即可。
考虑基环树的情况，先找到环，然后枚举删除环的每一条边，总复杂度是 $\mathcal{O}(n^2)$ 的。
代码
const int N = 5e4 + 5;
inline ll R …
Jayun 发布于 2023-10-10 10:25:28
00
TrieKruskal
题面
给定 $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
Digital Dynamic Programming
题面
给出 $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
TriePersistent Data Structure
题目描述
定义：如果字符串 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
Linear Dynamic Programming (Linear DP)GreedyBinary Answer
题面
题目描述
著名的植物学家 Alice 经过多年的探索，终于找到了传说中的璀璨花。璀璨花的生长速度非常迅猛，如果不加以合适的控制，璀璨花会因为过度内耗而死亡。璀璨花的生长趋势可以用序列 $a$ 表示，Alice 在研读前人对璀璨花的研究后总结出了一个控制序列 $b$ 。Alice 需要让璀璨花的生长趋势尽可能贴合控制序列，这样璀璨花就能尽可能快且安全地生长，以让更多人能欣赏到传说花卉的美 …
Jayun 发布于 2023-10-01 09:10:31
00