$n$ 个人来做实验，有 $m$ 个房间，一开始所有人都在 $1$ 号房间里，有两个操作：

1. 让第 $i$ 个人去房间 $j$
2. 让区间 $[l,r]$ 的房间做实验

实验会获得一些实验信息点数，点数为房间里的人数（不会重复增加点数），求每次操作获得的点数。

给定一个初始集合和目标集合，有两种操作：

1. 合并集合中的两个元素，新元素为两个元素之和
2. 分裂集合中的一个元素，得到的两个新元素之和等于原先的元素

要求用最小步数使初始集合变为目标集合，求最小步数。

给定一棵以 $1$ 为根的有根树，初始所有节点颜色为 $1$，每次将距离节点 $a$ 不超过 $l$ 的 $a$ 的子节点染成 $c$，或询问点 $a$ 的颜色。

题意很清晰，直接给链接。

链接

BZOJ 3337

Pine 开始了从 $ S $ 地到 $ T $ 地的征途。
从 $ S $ 地到 $ T $ 地的路可以划分成 $ n $ 段，相邻两段路的分界点设有休息站。
Pine 计划用 $ m $ 天到达 $ T $ 地。除第 $ m $ 天外，每一天晚上 Pine 都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine 希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助 Pine 求出最小方差是多少。

设方差是 $ v $，可以证明，$ v \times m ^ 2 $ 是一个整数。为了避免精度误差，输出结果时输出 $ v \times m ^ 2 $。

给出一些数字串作为模式串，求 $[l, r]$ 中第 $k$ 个包含至少一个模式串的串。

求 $[l, r]$ 中平衡数的个数，平衡数就是一某一位为支点，两侧的力矩相等。

给出一个 $n$ 的排列，进行 $m$ 次操作，每次操作是将一个区间升序或降序排序。
请你输出 $m$ 次操作后第 $p$ 个位置的值。

给定相离的两个圆（圆心坐标以及半径）以及圆外的一个定点 $P$，求出过点 $P$ 的且与已知的两个圆外切的所有圆。

求

$G$ 系共有 $n$ 位同学，$M$ 门必修课。这 $N$ 位同学的编号为 $0$ 到 $N - 1$ 的整数，其中 $B$ 神的编号为 $0$号。这 $M$ 门必修课编号为 $0$ 到 $M - 1$ 的整数。一位同学在必修课上可以获得的分数是 $1$ 到 $U_i$ 中的一个整数。如果在每门课上 $A$ 获得的成绩均小于等于 $B$ 获得的成绩，则称 $A$ 被 $B$ 碾压。在 $B$ 神的说法中，$G$ 系共有 $K$ 位同学被他碾压（不包括他自己），而其他 $N-K-1$ 位同学则没有被他碾压。$D$ 神查到了 $B$ 神每门必修课的排名。这里的排名是指：如果 $B$ 神某门课的排名为 $R$，则表示有且仅有 $R-1$ 位同学这门课的分数大于 $B$ 神的分数，有且仅有 $N-R$ 位同学这门课的分数小于等于 $B$ 神（不包括他自己）。我们需要求出全系所有同学每门必修课得分的情况数，使其既能满足B神的说法，也能符合 $D$ 神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。你不需要像 $D$ 神那么厉害，你只需要计算出情况数模 $10 ^ 9 + 7$ 的余数就可以了。

求斐波那契数列 $\text{mod }n$ 的循环节长度。

求一个回文串，使得这个回文串的一半也是回文串，输出其最长长度。

给出 $N$ 个圆，求其面积并。

P 教授有编号为 $1 \sim N$ 的 $N$ 件玩具，第 $i$ 玩具经过压缩后变成一维长度为 $C_i$ 为了方便整理，P 教授要求在一个一维容器中的玩具编号是连续的。如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中，那么容器的长度将为 $$x = j - i + \sum\limits_{k = i} ^ j C_k$$。如果容器长度为 $x$。其制作费用为 $(x - L) ^ 2$。其 $L$ 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。但他希望费用最小。

矩阵树定理的学习笔记和部分线性代数的知识，记录三道经典题目及变元矩阵树定理。

求其第 $n$ 项。

给定一个 $N$ 个点 $M$ 条边的有向图。统计无序对 $(X, Y)$ 的个数，其中 $(X, Y)$ 满足存在一条从 $1$ 到 $X$ 的路径，和一条 $1$ 到 $Y$ 的路径，且两路径除 $1$ 外无公共点。

一棵 $n$ 个点，边带权的树，$m$ 次询问，每次给出 $k$ 个关键点，求割掉最小代价的边使 $1$ 号点不能到达任何关键点。

给定一棵有 $n$ 个节点的无根树和 $m$ 个操作，操作有 $2$ 类：

1. 将节点 $a$ 到节点 $b$ 路径上所有点都染成颜色 $c$
2. 询问节点 $a$ 到节点 $b$ 路径上的颜色段数量

游戏中有 $N$ 个剧情点，由 $1$ 到 $N$ 编号，第 $i$ 个剧情点可以经过不同的支线剧情，前往 $K_i$ 种不同的新的剧情点。当然如果为 $0$，则说明 $i$ 号剧情点是游戏的一个结局了。

开始处在 $1$ 号剧情点。任何一个剧情点都是从 $1$ 号剧情点可达的。从任意剧情点出发，都不能再回到这个剧情点。要想回到之前的剧情点，唯一的方法就是开始新的游戏，回到 $1$ 号剧情点。可以在任何时刻退出游戏并重新开始。求花费最少的时间，看完所有不同的支线剧情。

给出一个长度为 $3n$ 的序列，规定连续 $n$ 个数字中不能选择超过 $k$ 个，问最多能取出的数的权值和是多少。

给出一个 $n * n$ 的黑白方阵，问能否通过交换行或交换列使得主对角线均为黑色。

有 $X, Y$ 两类卡牌，分别有 $n_1, n_2$ 张，每张卡牌有三个属性值：$A, B, C$。
两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。
游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。

给出一个 $n$ 个点 $m$ 条边的无向图，每个边有一正一反两个权值；现要从点 $1$ 出发，对每条边经过且仅经过一次；求一种方案使经过的最大权值最小。

给定一个字符串，要求支持两种操作，在当前字符串后加入一个字符串，询问字符串 $s$ 在当前字符串中出现了几次？

后缀自动机的做法相信大家都会，这里记录一下后缀数组做法。

给定一个数 $k$，要求构造一个非负整数序列，使得操作 $k$ 次后，最大数 $\leq n - 1$，每次操作选序列中最大值，将其 $-n$，其余数 $+1$。

给出一个 $1 \sim n$ 的排列，$p_0, p_2, \cdots, p_{n - 1}$，每次从中选相邻两数删去，加入 $q$ 的前面，求最小字典序的 $q$。

维护一棵树，子树修改，询问 $k$ 条链并的权值和。

链接

BZOJ 3589

T1 连环

给定一个长度为 $n$ 的字符串 $S$ 和一个长度为 $m$ 的字符串 $T$，现在有 $k$ 个询问，每个询问是给出两个整数 $l, r$，询问任选一对 $(i, j)$ 满足 $0 \leq i \leq l, n \geq j \geq r$，删去 $S$ 的 $[i + 1, j - 1]$ 这个区间的子串，剩下两块拼在一起，$T$ 在其中匹配数的期望。

给定两个由 A，B 组成的字符串 $S, T$，其中字符 A 可以变为 BB，B 可以变为 AA，AAA 和 BBB 可以被删掉，询问 $S$ 中的一个给定子串能否变为 $T$ 中的一个给定子串。

二维坐标系中有 $n$ 个矩形，第 $i$ 个矩形在水平方向上覆盖 $[l_i, r_i]$，在竖直方向上覆盖 $[i - 1, i]$，我们要水平移动这些矩形使得它们全部连通，水平移动的花费是移动的距离，求最小费用。

求

链接

BZOJ 3028

链接

POJ 3734

题意

有一排砖，数量为 $n$，有红蓝绿黄 $4$ 种颜色，其中染成红和绿颜色的砖块的数量必须为偶数个，求可有多少种染色方案。

链接

UOJ 221
BZOJ 4652
LOJ 2085

Fibonacci 数列是这样一个数列：

pty 忽然对这个古老的数列产生了浓厚的兴趣，他想知道：对于某一个 Fibonacci 数 $F_i$，有多少个 $F_j$ 能够整除 $F_i$ ($i$ 可以等于 $j$)，他还想知道所有 $j$ 的平方之和是多少。

给定一颗由 $n$ 个节点 $n - 1$ 条边构成的树，在所有路径长度不超过 $R$ 且不低于 $L$ 的路径中，对于任意一条路径，将其每条边权值从大到小排序，取第 $\lfloor \frac {len} {2} \rfloor + 1$ 个权值，求使此权值最大时，从哪个节点出发，到哪个节点结束。

关于数论的总结和专题练习….

点分治专题。

使用 streambuf 使 cin / cout 效率高于 fread / fwrite。
iostream 翻身了!!!

一些 2-SAT 题目。

dp 太弱，先补动规专题…

后缀平衡树是一种基于重量平衡树的非常有价值的数据结构，它可以在线维护 $sa$。

在 OI 中，我们手写的数据结构几乎都是静态内存的，而 STL 中的容器由于内存动态化的原因在做题中容易 TLE，这里介绍几种常见容器静态化内存的方法。

后缀数组的一些应用和题目，这里所有的时间复杂度均针对 SA-IS 算法。

模拟退火是一种通用概率算法，用来在固定时间内寻求在一个大的搜寻空间内找到的最优解。

一些常见的计算几何。

k-d 树（k-dimensional tree）是在 $k$ 维欧几里德空间组织点的数据结构。k-d 树可以使用在多种应用场合，如多维键值搜索（例：范围搜寻及最邻近搜索）。k-d 树 是空间二分树（Binary space partitioning）的一种特殊情况。而在算法竞赛中，k-d树往往用于在二维平面内的信息检索，这里主要指二维 k-d 树。