比赛地址Bugged如果所有数的和不是 $10$ 的倍数答案就是所有数的和,如果所有数都是 $10$ 的倍数答案是 $0$,否则答案为所有数的和减去最小的不是 $10$ 的倍数的数。代码Widespread二分答案 $mid$,那么相当于先把所有怪物的血量减去 $b\times mid$,再补 $mid$ 次伤害为 $a-b$ 的攻击。我们只要对减去 $b\times mid$ 血后仍然活着...
CodeforcesLuogu分析不难想到 DP。设 $dp_{i,a_1,a_2,\cdots}$ 表示前 $i$ 个字符,字符 $c_j$ 的出现次数模 $m_j$ 等于 $a_j$ 时的方案数。转移枚举在后面填的字符即可。因为 $\prod m_i\leq 123$,所以后面的状态至多只有 $123$ 种,因此直接矩阵快速幂即可。实现时需要把后面的状态压成一个数。我的做法是压成 $\B...
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)$,表示...
不想写计算几何,告辞。
LOJ分析为啥 LOJ 上有返回值的函数不写 return 会 RE 啊 /jk我们把 $i$ 向 $p_i$ 连边,这样子会有很多环。可以发现,如果有奇环则无解,所以我们只考虑偶环。显然一个偶环上只会是一个 (、一个 )、……,但是如果直接搜的话复杂度最大会达到 $\mathcal{O}(2^{\frac{n}{2}})$,无法接受。考虑一个大小为 $2$ 的偶环,显然小的那个填 (、大的...
CodeforcesLuogu分析显然当 $n+m-1>k$ 时无解,直接判掉即可。那么现在 $n,m$ 的规模变得比较小,于是我们就可以爆搜了。因为颜色数很少,可以用状压记录之前的路径上的颜色。然后有一些剪枝:如果还需要填的格子比剩的颜色还多,则无解。如果某些可填的颜色没有出现过,则填它们中的某个的方案数是相同的。感觉这个好玄学啊?代码// =====================...
Luogu分析你们这是什么输出格式啊,你们真是害人不浅啊你们这个输出格式!若搜索,对于每个 $p_i$ 枚举它的 $c_i$。注意到这里至多有一个 $p_\sqrt{S}$,因此我们只需要枚举 $\sqrt{S}$ 内的质数,再特殊处理剩下的那一个就好了。代码// =================================== // author: M_sea // webs...
Luogu分析显然可以直接爆搜,我们只要按字典序顺序搜就好了。然后是一些剪枝:不交换两个颜色相同的方块。(这个根据对题意的理解有争议?)向左移时如果左边不是空的就不移。(因为你显然可以让左边那个右移,字典序更小。)如果任何时候某种有的颜色 $\leq 2$,显然无解。然后就是码码码了。其实也不是很码代码// =================================== // a...
Luogu分析考虑到如果两个点之间没有边,那么这两个点一定会分在一个集合里。也就是说我们要求的实际上是补图的连通块。但是直接连边去求边数是 $n^2-m$ 级别的,显然存不下。考虑一个很暴力的想法:每次找一个还没有找连通块的点,然后 BFS 找连通块。具体就是扩展 $u$ 时,先标记 $u$ 的所有出点,然后所有没有找到连通块的没有被标记的点都和 $u$ 在一个连通块中。问题就是怎么维护还没...
Luogu分析发现自己容斥太菜了,于是来刷几道容斥题。首先预处理出 $[1,b]$ 范围内的所有幸运号码。这个 dfs 一下就行了。考虑到 $[a,b]$ 范围内 $x$ 的倍数个数为然而两个不同的幸运号码的倍数可能是会重复的,于是可以容斥。设 $f(i)$ 为 $[a,b]$ 内 $i$ 个幸运号码的 $\operatorname{lcm}$ 的倍数的个数,那么答案为 $f(1)-f(2)...