RainAir
My OI Blog
RainAir

2-SAT
文章归档

「NOI2017」游戏

建议大家去 UOJ 交题:链接 题目描述 有 $n$ 场游戏和三种车,每个游戏可以选择用一种车,每个游戏可能要求不能使用某种车,也可能没有要求。 给出 $m$ 个要求,表示如果第 $u$ 个游戏用了 $x$ 车,那么第 $v$ 个游戏要用 $y$ 车。求一种合法方案。 $n \leq 5 \times…

   107   2019-10-12   107 去吊打作者

2-SAT 学习笔记

定义 SAT 维基百科——Boolean_satisfiability_problem 2-SAT SAT 的简化版本:每个等式中只有两个变量参与。 有 $n$ 个 $0/1$ 变量和 $m$ 个等式,每个等式形如 $x_i \text{op} x_j =k$,其中 $op$ 是一个位运算。 你要求出一组可行解。 求解 将每个 $x_i$ 拆成两…

   112   2019-10-12   112 去吊打作者
标签
近期评论