题目大意

「GXOI / GZOI 2019」特技飞行（Luogu 5302）

给定 $n$ 条线段，它们的起点和终点的 $x$ 坐标分别为 $Sx$ 和 $Tx$，$y$ 坐标在输入中给定。在两条线段 $l_1, l_2$ 交点，可以交换 $l_1, l_2$ 接下来的部分（变成两条折线）。交换或不交换分别可以获得固定的分数 $a$ 和 $b$。要求最后在 $x = Sx$ 处和 $x = Tx$ 处，折线保持相同的顺序。

另外有 $m$ 个观测点可以观测到一定范围内情况（曼哈顿距离），在观测范围内的点额外获得 $c$ 分。问如何交换可以获得最高的得分。保证交点小于等于 $k$ 个。

$n, m \le 10^5, k \le 5 \times 10^5$。

Pollard-Rho 算法可以用期望 $O(\sqrt[4]{n})$ 的时间找到合数 $n$ 的一个非平凡因子。

算法流程

这里讲解改进后的 Pollard-Rho 算法变种。

在一次 Pollard-Rho 中，我们随机一个数 $c$，并设定阈值 $k$，初始为 $2$，每次循环后加倍。

对于每一次循环，令 $y$ 等于当前的 $x$，然后进行 $k$ 次，每次让 $x \leftarrow f(x) = (x ^ 2 + c) \bmod n$，然后检查 $\vert x - y \vert$ 和 $n$ 是否有非平凡的 $\gcd$，如果有则退出循环。

Miller-Rabin 素数测试算法是一种能够快速检验一个数是否为素数的算法。

算法流程

费马小定理：如果 $n$ 为素数，那么对于 $\forall 1 \le a \le n - 1$，都有 $a^{n - 1} \equiv 1 \bmod n$。

二次探测法：如果 $n$ 为素数，那么方程 $a^2 \equiv 1 \bmod n$ 只有两个解：$a_1 = 1, a_2 = n - 1$。

于是我们可以设计一个算法，对于一个特定的 $a$ 来检验。

题目大意

「GXOI / GZOI 2019」旅行者（Luogu 5304）

给定一个有 $n$ 个结点，$m$ 条边的带权有向图和 $k$ 个关键点，求 $k$ 个点两两之间最短路长度的最小值。

$n \le 10^5, m \le 5 \times 10^5$。

题目大意

我们所可以自慰的，想来想去，也还是所谓对于将来的希望。
希望是附丽于存在的，有存在，便有希望，有希望，便是光明。

「十二省联考 2019」希望（LOJ 3053）

给定一棵 $n$ 个结点的树以及两个数 $L, k$。对于树上的一个连通快 $S$，定义 $R(S)$ 为在 $S$ 中且离 $S$ 中的每个点距离都不超过 $L$ 的点集。问任选 $k$ 个联通快 $S_1, S_2, \cdots, S_k$，使得 $R(S_1), R(S_2), \cdots, R(S_n)$ 有交的方案数 $\bmod 998244353$ 的结果。

数据范围：$n, L \le 10^6$。

题目大意

「WF 2012」Chips Challenge（UVA 1104）

给定一个 $n \times n$ 的棋盘，有些格子已经放上了黑色或白色的棋子。要求你在剩下的格子中摆放棋子，满足条件：

• 第 $i$ 行的黑子个数等于第 $i$ 列的黑子个数。
• 每行的黑子个数不大于总黑子个数的 $\frac{A}{B}$。

求最多再放多少黑子。

数据范围：$n \le 50$。

题目大意

「Codechef SKIRES」Ski Resort

给定 $n \times m$ 的网格图，每个格子有一个高度 $h_{i, j}$。给一个格子的高度增加 $x$ 需要花费 $x$ 的代价。你要调整某些格子的高度，使得不存在高度单调不下降的，从起点到终点的路径。求需要花费的最小代价。

数据范围：$n, m \le 50$。

题目大意

「清华集训 2017」某位歌姬的故事（UOJ 346）

求满足下列条件的，长度为 $n$ 的正整数序列 $a$ 数量 $\bmod 998244353$ 的结果：

• $\forall a_i \le A$
• $\forall i \in [1, Q], \max { a_{l_i}, a_{l_i + 1}, \cdots, a_{r_i} } = m_i$

数据范围：$n, A \le 9 \times 10 ^ 8, Q \le 500$。