这是本文档旧的修订版!
题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
---|---|---|---|
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 |
给定固定路线 $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$,可以得到如下几类:
然后对每类路径,单独考虑费用。不妨设某类路径的起点终点为 $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)$。
给定 $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$,其他情况类似。
最后只剩下不超过一个自由变量,显然该变量任意取值后所有其他变量都取值固定,正好满足三组解。