这是本文档旧的修订版！
补题情况
| 题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
|---|---|---|---|
| B | 2 | 0 | 0 |
| D | 0 | 0 | 0 |
| E | 2 | 0 | 0 |
| G | 0 | 0 | 0 |
| I | 0 | 0 | 0 |
| J | 2 | 0 | 0 |
| L | 2 | 0 | 0 |
题解
J. Jazz Journey
题意
给定固定路线 $a_1,a_2\cdots a_d(1\le a_i\le n)$，需要坐飞机依次经过各点。
接下来给定若 $m$ 种机票，每张机票有一个起点 $u$ 和终点 $v$ 以及费用 $w$。
机票分为单程票和双程票，其中每张单程票只能实现一次 $u\to v$，双程票可以实现一次 $u\to v$ 和一次 $v\to u$。
题解
由于只有 $d-1$ 次移动，所以不妨将所有移动按起点终点分类，其中 $u\to v,v\to u$ 视为同类。
例如，对路径 $12313121$，可以得到如下几类：
- $1\to 2,1\to 2,2\to 1$
- $2\to 3$
- $3\to 1,1\to 3,3\to 1$
然后对每类路径，单独考虑费用。不妨设某类路径的起点终点为 $u,v$，且 $u\to v$ 的双程票是最划算的。
考虑扫描该类型的所有移动，一旦出现 $u\to v,v\to u$ 则立刻购买 $u\to v$ 双程票，否则先保留。
最后剩余的移动一定是形如 $v\to u,v\to u\cdots v\to u,u\to v\cdots u\to v$，这个时候再考虑买 $v\to u$ 的双程票划算还是单程票划算即可。
最后不要忘了把双程票当单程票用比单程票便宜的情况。时间复杂度 $O\left(d\log d\right)$。
L. Lost Logic
题意
给定 $n$ 个变量以及三组解，要求构造若干条形如 $(!)x_i\to (!)x_j$ 的限制，使得方程只有给定的三组解。
题解
将所有变量在三组解中的取值分为 $8$ 类，分别是 $(0,0,0),(0,0,1)\cdots (1,1,1)$。
首先对于 $(0,0,0)$ 类变量，构造约束 $x\to !x$，类似处理 $(1,1,1)$ 类变量。
对于同属于 $(0,0,1)$ 类变量 $x,y$，构造约束 $x\to y,!x\to !y$。
于是现在自由变量最多只有 $6$ 个。然后处理对偶的自由变量，如 $x\in (0,0,1),y\in (1,1,0)$，构造约束 $x\to !y,!x\to y$。
现在只剩下最多 $3$ 个自由变量了。不难发现如果有 $3$ 个自由变量则无法进一步构造约束。
当有两个自由变量时，不妨考虑 $x\in (0,0,1),y\in (1,0,0)$ 的情况，只要去除 $x=1,y=1$ 的情况即可，可以构造约束 $x\to !y$，其他情况类似。
最后只剩下不超过一个自由变量，显然该变量任意取值后所有其他变量都取值固定，正好满足三组解。
