AtCoder Regular Contest 075 简要题解
比赛地址Bugged如果所有数的和不是 $10$ 的倍数答案就是所有数的和，如果所有数都是 $10$ 的倍数答案是 $0$，否则答案为所有数的和减去最小的不是 $10$ 的倍数的数。代码Widespread二分答案 $mid$，那么相当于先把所有怪物的血量减去 $b\times mid$，再补 $mid$ 次伤害为 $a-b$ 的攻击。我们只要对减去 $b\times mid$ 血后仍然活着...
标签 搜索 下的文章
- 首页
- 搜索
CF107D Crime Management
CodeforcesLuogu分析不难想到 DP。设 $dp_{i,a_1,a_2,\cdots}$ 表示前 $i$ 个字符，字符 $c_j$ 的出现次数模 $m_j$ 等于 $a_j$ 时的方案数。转移枚举在后面填的字符即可。因为 $\prod m_i\leq 123$，所以后面的状态至多只有 $123$ 种，因此直接矩阵快速幂即可。实现时需要把后面的状态压成一个数。我的做法是压成 $\B...
洛谷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)...