题目大意

「BZOJ 2169」连边

给定一个 $n$ 个点 $m$ 条边的图，要在图上加 $k$ 条互不相同的边（新边可以和旧边相同），使得新图的每个点的度数都是偶数。求方案数 $\bmod 10^4 + 7$ 的结果。

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

题目大意

「Codeforces 888G」Xor MST

给定一个长度为 $n$ 的数列 $a_1, a_2, \cdots, a_n$，构造带权完全图 $G$，边 $(i, j)$ 的边权是 $a_i \oplus a_j$，其中 $\oplus$ 表示异或运算。求图 $G$ 的最小生成树。

数据范围：$n \le 2 \times 10^5, a_i \le 2^{30}$。

弦图

弦图是一类特殊的无向图。弦图上的所有简单环上都至少有一条弦，其中弦是联结环上两个不相邻的点的边。

这个限制等价于图中存在至少一个完美消除序列。

（好像学了一个没啥用的东西）

目录

• 按时间分治
• CDQ 分治
• 整体二分

题目大意

「LOJ 6686」Stupid GCD

求下列式子的值：

数据范围：$n \le 10^{30}$。

题目大意

「Luogu U71500」星空夜

「EOJ 191C」最小公倍数 2

有 $n$ 颗星星，每颗可以用有序数对 $(a_i, b_i)$ 表示，意为它会在时刻 $a_i + k \times b_i (k \in N)$ 闪烁。给定 $q$ 组询问，每次指定一个区间 $[l, r]$，询问编号在这个区间中的星星是否可能在某时刻同时闪烁一次。

数据范围：$n, q \le 10^6, b_i \le 10^7$。

预计难度：提高组（？）。

题目大意

「BZOJ 3580」冒泡排序

对于长度为 $n$ 的排列 $a$，给定如下的冒泡排序的代码：

1

for (int i = 1; i < n; i++) {

2

	for (int j = 1; j <= n - i; j++) {

3

		if (a[j] > a[j + 1]) {

4

			swap(a[j], a[j + 1]);

5

		}

6

	}

7

}

问第 $k$ 次 swap 操作过后的 $a$。

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

题目大意

「Codeforces 1187D」Subarray Sorting

给定长度为 $n$ 的两个数列 $A, B$，问是否可以做若干次「将 $A$ 的某个区间升序排序」把 $A$ 变为 $B$。

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

题目大意

「HNOI 2010」Planar（BZOJ 1997）

给定一个 $n$ 个结点 $m$ 条边的无向图，保证它有哈密尔顿回路。给定它的一个哈密尔顿回路，问它是不是平面图。

数据范围：$T \le 100, n \le 200, m \le 10^4$。

题目大意

「BZOJ 2438」杀人游戏

给定一个 $n$ 个点 $m$ 条边的有向无向图，每个点代表一个人，每条单向边代表一组认识关系。已知有一个人是杀手，每个人是杀手的概率都是 $\frac{1}{n}$。有一个警察，每次可以询问一个人，他如果是杀手就会把警察杀掉，如果不是的话他会告诉警察他认识的人中谁是杀手或没有杀手。问警察选择最优策略，查到杀手后还存活的概率。

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