每一个少年终将梦醒

参加了最后一次 OI 系列的考试，终于也 AFO 了。几年伴随我的 OI 历程也在此结束。梦结束了。

接下来 whk 加油！

题意描述

平面直角坐标系的第一象限内有一块左下角为 \((0,0)\) 右上角为 \((10^{100},10^{100})\) 的矩形区域，区域内有正偶数个整点，试求出这样一条从 \((0,0)\) 出发，到 \((10^{100},10^{100})\) 的在区域内部的折线：

• 折线的每一部分都平行于 \(x\) 轴或 \(y\) 轴。
• 折线不能经过给定的整点。
• 折线将整块区域分成包含给定整点个数相等的两块。
• 折线拥有尽可能少的折点。

可以证明一定存在一条满足限制的折线，你只需要输出满足限制的折线的折点数即可。

注意折点的坐标可以不是整数。

每组测试点有 \(T\) 组数据，对于所有测试点，\(1 \leq T \leq 10^4\)，\(1 \leq \sum n \leq 5 \times 10^5\)，\(1 \leq n \leq 10^5\)，\(1 \leq x_i,y_i \leq n\)，保证 \(n\) 为正偶数，每组数据中不存在两个坐标相同的整点。

题意描述

洛谷链接

Farmer John（又）想到了一个新的奶牛晨练方案！
如同之前，Farmer John 的 \(N\) 头奶牛站成一排。对于 \(1\le i\le N\) 的每一个 \(i\)，从左往右第 \(i\) 头奶牛的编号为 \(i\)。他告诉她们重复以下步骤，直到奶牛们与她们开始时的顺序相同。

给定长为 \(N (1 \le N \le 10^4)\) 的一个排列 \(A\)，奶牛们改变她们的顺序，使得在改变之前从左往右第 \(i\) 头奶牛在改变之后为从左往右第 \(A_i\) 头。
例如，如果 \(A=(1,2,3,4,5)\)，那么奶牛们总共进行一步。如果 \(A=(2,3,1,5,4)\)，那么奶牛们总共进行六步。每步之后奶牛们从左往右的顺序如下：

0 步：\((1,2,3,4,5)\)
1 步：\((3,1,2,5,4)\)
2 步：\((2,3,1,4,5)\)
3 步：\((1,2,3,5,4)\)
4 步：\((3,1,2,4,5)\)
5 步：\((2,3,1,5,4)\)
6 步：\((1,2,3,4,5)\)
求所有正整数 \(K\) 的和，使得存在一个长为 \(N\) 的排列，奶牛们需要进行恰好 \(K\) 步。

由于这个数字可能非常大，输出答案模 \(M\) 的余数（\(10^8\le M\le 10^9+7\)，\(M\) 是质数）。

题意描述

洛谷连接

一共有 \(n\) 个飞行员，其中有 \(m\) 个外籍飞行员和 \((n - m)\) 个英国飞行员，外籍飞行员从 \(1\) 到 \(m\) 编号，英国飞行员从 \(m + 1\) 到 \(n\) 编号。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

对于 \(100\%\) 的数据，保证 \(1 \leq m \leq n < 100\)，\(1 \leq u \leq m < v \leq n\)，同一组配对关系只会给出一次。

网络流是一个图论中很大的知识点，这里只涉及部分内容。本篇只涉及最大流、最小割和费用流的相关知识。

概念

一张有向图 \(G = (V, E)\)，对于每条边 \((u， v) \in E\) 都有一个权值 \(c(u, v) > 0\)，称为边的 容量。且对于图上没有的边 \((u， v) \notin E\)，\(c(u, v) = 0\)，则这张图叫做一个 网络，图中有两个特殊的点 \(s \in V\) 和 \(t \in V\)，这两个点称为 源点 和 汇点。

题意描述

LibreOJ 链接

给定一个有 \(n (n \le 2000)\) 个节点的有向无环图，图中某些节点上有棋子，两名玩家交替移动棋子。

玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。

对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。

题意描述

POJ 链接

有一张 \(w \times h (2 \le w, h \le 200)\) 大小的矩形网格纸片，两名玩家轮流行动。在每一次行动中，任选一张纸片，沿着某一行或某一列的格线剪成两部分。首先剪出 \(1 \times 1\) 大小纸片的玩家获胜。两名玩家均以最优策略行动，问先手是否有必胜策略。

SG 函数是解决博弈论问题的一种方法。

博弈论概念

公平组合游戏

首先我们需要了解以下几个概念。

公平组合游戏指的是一类满足下列条件的游戏：

1. 有两名玩家交替操作；
2. 每名玩家可用的操作与玩家的先后无关；
3. 无法移动的玩家判负。

题意描述

洛谷链接

从山顶上到山底下沿着一条直线种植了 \(n\) 棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。

木材只能朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建这两个锯木厂，使得运输的费用总和最小。假定运输每公斤木材每米需要一分钱。

你的任务是编写一个程序，从输入文件中读入树的个数和他们的重量与位置，计算最小运输费用。

数据范围：\(n \le 20000\)。

题意描述

Codeforces 链接

你有一个长度为 \(n (1 \le n \le 2 \times 10^5)\) 的整数序列 \(a\)。

你需要回答 \(q (1 \le q \le 2 \times 10^5)\) 个独立的问题，每次询问如下：

给定 \(l\) 和 \(r\)，你可以对序列做若干次操作（也可以不做），每次操作，你需要选择两个数 \(L\) 与 \(R\)，其中必须满足 \(l\le L\le R\le r\) 且 \(R-L+1\) 为奇数。然后将 \(a_L\sim a_R\) 的所有数改为 \(a_L\sim a_R\) 的异或和，即 \(a_L\oplus a_{L+1}\oplus \sim \oplus a_R\)。

你的目标是将 \(a_l\sim a_r\) 的所有数变为 \(0\)。每次询问完后，序列复原。

询问的答案即为最小操作数。如果总是不能达到目标，则答案为 \(-1\)。