CF107D Crime Management
Codeforces Luogu 分析 不难想到 DP。设 $dp_{i,a_1,a_2,\cdots}$ 表示前 $i$ 个字符，字符 $c_j$ 的出现次数模 $m_j$ 等于 $a_j$ 时的方案数。转移枚举在后面填的字符即可。 因为 $\prod m_i\leq 123$，所以后面的状态至多只有 $123$ 种，因此直接矩阵快速幂即可。 实现时需要把后面的状态压成一个数。我的做法是压...
Codeforces Luogu 分析 不难想到 DP。设 $dp_{i,a_1,a_2,\cdots}$ 表示前 $i$ 个字符，字符 $c_j$ 的出现次数模 $m_j$ 等于 $a_j$ 时的方案数。转移枚举在后面填的字符即可。 因为 $\prod m_i\leq 123$，所以后面的状态至多只有 $123$ 种，因此直接矩阵快速幂即可。 实现时需要把后面的状态压成一个数。我的做法是压...
LOJ 分析 我们把 $i$ 向 $p_i$ 连边，这样子会有很多环。可以发现，如果有奇环则无解，所以我们只考虑偶环。 显然一个偶环上只会是一个 (、一个 )、……，但是如果直接搜的话复杂度最大会达到 $\mathcal{O}(2^{\frac{n}{2}})$，无法接受。 考虑一个大小为 $2$ 的偶环，显然小的那个填 (、大的那个填 ) 更优，因此我们只需要搜大小 $\geq 4$ 的环...
Luogu LOJ 分析 首先我们并不需要整副牌，我们只需要每种牌的出现次数，也就是说只需要一个长度为 $n$ 的串。 考虑怎么判一副牌能不能和。可以去做一下这道题。 我们把第一维去掉，强制 $f$ 值不超过 $4$ 、雀头数不超过 $7$ ，这样子就会有大量重复状态。爆搜可以搜出本质不同的状态只有 $2091$ 种。 那么我们把所有状态预处理出来，然后预处理出对于每个状态追加 $x\...
Luogu 分析 先考虑平面上的这种问题：平面上有一些方块，你每次可以覆盖长度为 $x$、宽度为 $y$ 的一个区域，代价是 $\min(x,y)$，求覆盖所有点的最小代价。 显然每次染一个 $1\times k$ 的区域是最优的。于是让每个方块的 $x$ 向 $y$ 连边，然后求二分图最小点覆盖即可。 现在把这个扩展到三维。 注意到一定有一维 $\leq\sqrt[3]{5000}$ 也...