RainAir
My OI Blog
RainAir
「NOI2017」游戏

建议大家去 UOJ 交题:链接

题目描述

有 $n$ 场游戏和三种车,每个游戏可以选择用一种车,每个游戏可能要求不能使用某种车,也可能没有要求。
给出 $m$ 个要求,表示如果第 $u$ 个游戏用了 $x$ 车,那么第 $v$ 个游戏要用 $y$ 车。求一种合法方案。
$n \leq 5 \times 10^4,m \leq 10^5$,没有要求的游戏个数 $d$ 不超过 $8$。

题解

前置小知识:2-SAT

建图

首先考虑如果没有没有要求的游戏个数的话是不是一个经典的 2-SAT 问题。
注意到三个字母的状态其实是假的,每个游戏其实只有两个状态。
然后我们就可以对于每一个限制 $(u,x,v,y)$ 分类讨论了:
1. $u$ 游戏不能选 $x$
直接忽略掉就好了,对答案无影响。
2. $u$ 可选 $x$,$v$ 游戏不能选 $y$
意思就是 $u$ 不能选择 $x$,(不存在对应的 $v$)在图上对应着边 $u_{x} \to u_{\lnot x}$
3. $u$ 可选 $x$,$v$ 可选 $y$
就是限制当 $u=x$ 时 $v=y$,直接连边$u _ x \to v _ y,v _ {\lnot y} \to u_{\lnot x}$。

发现没有要求的游戏个数很小,选择 $O(2^d)$ 枚举,时间复杂度 $O(2^d(N+M))$

小优化

然后交到 BZOJ,惊奇的发现:
https://blog.aor.sd.cn/wp-content/uploads/2019/10/200394AB-CA74-44E4-8E73-5CB0B1CED048-1024x18.jpg
然后你按照博主的指引交到了 UOJ,发现:
https://blog.aor.sd.cn/wp-content/uploads/2019/10/QQ20191012-132034-1024x36.png
仔细一看 原来被人叉了。有人构造了一组非常大的无解数据,这样会跑满,运算量大概是 $7.68\times 10^7$。并且 UOJ 限时 $1s$ 直接 T 了。
我们猜想满足条件的 $x$ 应该是很多的,于是我们枚举改为随机,然后卡时,然后加上 Ofast,用上关流的 cin,找个吉时就过了!https://blog.aor.sd.cn/wp-content/uploads/2019/10/QQ20191011-112317.png

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/877
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「NOI2017」游戏
建议大家去 UOJ 交题:链接 题目描述 有 $n$ 场游戏和三种车,每个游戏可以选择用一种车,每个游戏可能要求不能使用某种车,也可能没有要求。 给出 $m$ 个要求,表示如果第 $u$ 个游戏…
扫描二维码继续阅读
2019-10-12
标签
近期评论