题目大意

「NOI 2017」游戏（UOJ 317）

有一个长度为 $n$ 的字符串 $S$（包含 a，b，c，x）和 $m$ 组限制关系，要求构造一个只包含 A，B，C 的字符串 $T$，满足 $S_i \neq \text{lowercase}(T_i)$ 以及所有的限制关系。一组限制形如：如果 $T_{u_j} = a_j$，则 $T_{v_j} = b_j$。

数据范围：$n \le 5 \times 10^4, m \le 10^5$，x 的个数 $d$ 不会超过 $8$。

题目大意

「BZOJ 4699」树上的最短路

给定一棵 $n$ 个结点的树，第 $i$ 条边的长度为 $l_i$。还要额外地联结 $m$ 次边，第 $j$ 次对于任意 $u$ 在树上路径 $(a_j, b_j)$ 上，$v$ 在树上路径 $(c_j, d_j)$ 上，都从 $u$ 向 $v$ 连一条长度为 $e_j$ 的边。问每个点走到 $k$ 点的最短路。

数据范围：$n \le 2.5 \times 10^5, m \le 10^5$。

欧拉回路、欧拉图及其判定

在一张图上，一条从某个点出发，经过所有的边后回到原点的路径叫做欧拉回路。有欧拉回路的图叫做欧拉图。

容易发现，欧拉图一定是联通图。它还需要满足以下条件：

• 如果是无向图，那么每个结点的度数都是偶数。
• 如果是有向图，那么每个结点的入度和出度相等。

不难理解这是判断欧拉图的充要条件。

什么是最小树形图

无向图上有最小生成树，那么有向图上呢？有向图上的最小生成树称为 “最小树形图”，英文叫 Directed Minimum Spanning Tree。

如果把一个树形图的有向边替换成无向边，它会变成一棵生成树。但与生成树不同的是，树形图中会确定一个根，它必须满足根能够到达每个结点。最小树形图是所有树形图中边权和最小的一个。

题目大意

「十二省联考 2019」春节十二响（Luogu 5290）

给定一棵 $n$ 个结点的树，每个结点有权值 $M_i$。要求将树上的节点分组，每组的结点中的任意两个不是祖先 - 后代关系。一组的代价为包含的节点的权值的最大值，一个方案的代价是每组的代价之和，求最小代价。

数据范围：$n \le 2 \times 10^5$。

题目大意

「十二省联考 2019」字符串问题（Luogu 5284）

题太长了，自己读吧 QAQ。

令 $n = \vert S \vert$，则：

• 对于 $40 \%$ 的数据，$n_a \times n_b \le 2 \times 10^5$。
• 对于 $80 \%$ 的数据，$\vert A_i \vert \ge \vert B_i \vert$。
• 对于 $100 \%$ 的数据，$n, n_a, n_b, m \le 2 \times 10^5$。

题目大意

「十二省联考 2019」异或粽子（Luogu 5283）

给定一个长度为 $n$ 的数列 $a_1, a_2, \cdots, a_n$，问区间异或和前 $k$ 大的区间的异或和之和。

数据范围：$n \le 5 \times 10^5, m \le 2 \times 10^5, 0 \le a_i < 2^{32}$。

题目大意

从集合 ${ 1, 2, \cdots, n }$ 中选出一个子集，满足其中不存在两个数互相是两倍或三倍关系。求选的方案总数$\bmod 10^9 + 1$ 的结果。

数据范围：$n \le 10^5$。

题目大意

「Codeforces 865C」Gotta Go Fast

一个游戏有 $n$ 个关卡，每个关卡有三个参数 $F_i, S_i, P_i$，表示你有 $P_i \%$ 的概率使用 $F_i$ 个单位时间通关，有 $1 - P_i \%$ 的概率使用 $S_i$ 个单位时间通关。你的目标是在 $m$ 个单位时间内按顺序连续通过所有关卡。每打完一关以后，你可以根据当前用时来进行决策。你可以继续打关，也可以重启游戏，从第一关开始从新打。问在最优策略下，达成目标需要使用的期望时间。

数据范围：$n \le 50, m \le 5 \times 10^3, F_i < S_i \le 100, 80 \le P_i \le 99$.

题目大意

「APIO 2015」Jakarta Skyscrapers（Luogu 3645）

有 $n$ 个位置，$m$ 只 doge，第 $i$ 只在位置 $b_i$ 上。一开始给 $1$ 号 doge 传达信息，第 $i$ 只 doge 在收到信息后，可以进行如下操作：

• 自己向左后向右移动 $p_i$ 个位置，花费 $1$ 个单位时间。
• 将携带的信息传达给在同一个位置上的 doge，花费 $0$ 个单位时间。

问信息传达给 $2$ 号 doge 所需要的最少时间。

数据范围：$n, m \le 3 \times 10^4$。