洛谷3825 [NOI2017]游戏
LuoguLOJ分析没有 x 时显然是 2-SAT。将每张图拆成两个点表示能填的两种赛车。为了方便，设 $(i,a)$ 表示 $i$ 填 $a$ 所对应的点，$(i,\neg a)$ 表示 $i$ 不填 $a$（即填另一种赛车）对应的点。对于每个条件 $(i,a,j,b)$如果 $s_i\neq a$，忽略。如果 $s_j\neq b$，连边 $(i,a)\to (i,\neg a)$，表示...
标签 搜索 下的文章
- 首页
- 搜索
LOJ6043 「雅礼集训 2017 Day7」蛐蛐国的修墙方案
LOJ分析为啥 LOJ 上有返回值的函数不写 return 会 RE 啊 /jk我们把 $i$ 向 $p_i$ 连边，这样子会有很多环。可以发现，如果有奇环则无解，所以我们只考虑偶环。显然一个偶环上只会是一个 (、一个 )、……，但是如果直接搜的话复杂度最大会达到 $\mathcal{O}(2^{\frac{n}{2}})$，无法接受。考虑一个大小为 $2$ 的偶环，显然小的那个填 (、大的...
CF293B Distinct Paths
CodeforcesLuogu分析显然当 $n+m-1>k$ 时无解，直接判掉即可。那么现在 $n,m$ 的规模变得比较小，于是我们就可以爆搜了。因为颜色数很少，可以用状压记录之前的路径上的颜色。然后有一些剪枝：如果还需要填的格子比剩的颜色还多，则无解。如果某些可填的颜色没有出现过，则填它们中的某个的方案数是相同的。感觉这个好玄学啊？代码// =====================...
洛谷4397 [JLOI2014]聪明的燕姿
Luogu分析你们这是什么输出格式啊，你们真是害人不浅啊你们这个输出格式！若搜索，对于每个 $p_i$ 枚举它的 $c_i$。注意到这里至多有一个 $p_\sqrt{S}$，因此我们只需要枚举 $\sqrt{S}$ 内的质数，再特殊处理剩下的那一个就好了。代码// =================================== // author: M_sea // webs...
洛谷1312 Mayan游戏
Luogu分析显然可以直接爆搜，我们只要按字典序顺序搜就好了。然后是一些剪枝：不交换两个颜色相同的方块。（这个根据对题意的理解有争议？）向左移时如果左边不是空的就不移。（因为你显然可以让左边那个右移，字典序更小。）如果任何时候某种有的颜色 $\leq 2$，显然无解。然后就是码码码了。其实也不是很码代码// =================================== // a...
洛谷3452 [POI2007]BIU-Offices
Luogu分析考虑到如果两个点之间没有边，那么这两个点一定会分在一个集合里。也就是说我们要求的实际上是补图的连通块。但是直接连边去求边数是 $n^2-m$ 级别的，显然存不下。考虑一个很暴力的想法：每次找一个还没有找连通块的点，然后 BFS 找连通块。具体就是扩展 $u$ 时，先标记 $u$ 的所有出点，然后所有没有找到连通块的没有被标记的点都和 $u$ 在一个连通块中。问题就是怎么维护还没...
洛谷2567 [SCOI2010]幸运数字
Luogu分析发现自己容斥太菜了，于是来刷几道容斥题。首先预处理出 $[1,b]$ 范围内的所有幸运号码。这个 dfs 一下就行了。考虑到 $[a,b]$ 范围内 $x$ 的倍数个数为然而两个不同的幸运号码的倍数可能是会重复的，于是可以容斥。设 $f(i)$ 为 $[a,b]$ 内 $i$ 个幸运号码的 $\operatorname{lcm}$ 的倍数的个数，那么答案为 $f(1)-f(2)...
洛谷5362 [SDOI2019]连续子序列
LuoguLOJ分析事实上这个序列叫做 $\text{Thue-Morse}$ 序列，在 OEIS 上可以查到。它的一种构造方法是：设 $\mathbf{T.M.}=\{0\}$ ，然后每次把序列中的 $0$ 替换成 $01$ ，把序列中的 $1$ 替换成 $10$ 。我们反着做这个过程，即 $01\to 0$ ，$10\to 1$ 。可以发现这个过程等价于把每两个相邻的字符分成一组，然后替...
洛谷5279 [ZJOI2019]麻将
LuoguLOJUOJ分析雀魂+自动机+动态规划+九条可怜。首先我们并不需要整副牌，我们只需要每种牌的出现次数，也就是说只需要一个长度为 $n$ 的串。考虑怎么判一副牌能不能和。可以去做一下 这道题 。我们把第一维去掉，强制 $\mathrm{dp}$ 值不超过 $4$ 、雀头数不超过 $7$ ，这样子就会有大量重复状态。爆搜可以搜出本质不同的状态只有 $2091$ 种。那么我们 $\mat...