分析 \(t\) 时刻还有城镇没有被淹没，\(t+1\) 时刻所有城镇将要被淹没。 一个思路是求出最后一个城镇被淹没的时刻 \(D\)，然后通过魔法调整使得所有城镇至少会在 \(D\) 时刻被淹没。显然 \(D\) 就是 \(1\) 到每一个点所有的路径中的最大边权取最小值，猜都能猜到是最小生成树中的最大边权，证明略。 求出 \(D\) 后，我们的目标是使得 \(1 \rightarr

CF1714. 最近摸得有点厉害，主要是被自己菜到了，心态有点差…… 老年人也就看看 Div 3 了。 A. Everyone Loves to Sleep 转化成分钟乱搞即可。 #include<bits/stdc++.h> using namespace std; #define int long long int t, n, H, M, D, ans, h[15], m

关于置换 根据《数学奥林匹克小丛书·组合数学》上关于置换的定义： 给定集合 \(X = \{1,2,3,\ldots ,n \}\)，置换 \(\varphi\) 是从 \(X\) 到 \(X\) 上的一一映射，通常记为 \[ \varphi = \begin{Bmatrix} 1 & 2 & \ldots & n \\ \varphi(1) &

分析 本题的关键是 \(\gcd_{i=1}^n \{a_i\}\) 就是所有出现过的质因数，是所对应的最小次幂之积。 原序列可以看作依次插入。将 \(a_x\) 修改为 \(y\)，本质上是除去所有在 \(a_x\) 分解中的质因数的幂次，然后再将 \(y\) 插入并更新。 所以用std::map来维护某个 \(a_i\) 中所有质因数的幂次，用std::set来维护某个质因数的所有

分析 即求 \[ (x-1)d + y \equiv (y-1)d + x \pmod w \] 满足 \(x < y\) 的解 \((x,y)\) 的个数。 化简 \[ xd + y \equiv yd + x \pmod w \] \[ yd - xd - x -y \equiv 0 \pmod w \] \[ (y-x)(d-1) \equiv 0 \pmod w

分析 为了方便起见，用 \(n\) 代替 \(x\)，\(m\) 代替 \(y\)。 不难发现无论 \([1,m-1]\) 这些数字的符号是什么样的，只要恰当安排最后一位就一定能使结果是正数。由于每一位正负都可以选，所以这部分的方案数为 \(2^{m-1}\)。 考虑到值域不大，可以单独考虑每个质因子。 对于一个质因子 \(p_i\)，它的次数为 \(a_i\)。问题转化为在 \(

分析 首先将 \(n\) 分解为 \(n= \prod_{i=1}^m p_i^{a_i}\)。那么 \(n\) 的约数个数为 \(d(n) = \prod_{i=1}^m (a_i +1)\)。 考虑每个质因子的贡献。 首先对于 \(p_i\)，它的整数次幂作为独立的一个约数时，一定有 \(p_i^1 p_i^2 \ldots p_i ^{a_i} = p_i^{\frac{a_i(a

中国剩余定理（CRT） 由于扩展中国剩余定理和中国剩余定理没啥关系，所以我们先来复习一下中国剩余定理。 同余方程组 \[ \begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \quad \vdots \\ x \equiv a_n \pmod {m_n} \end{cases} \] 当

Solution 1 设 \(f_i\) 为从 \(1\) 问到第 \(i\) 个镜子，且通过了第 \(i\) 个镜子的期望天数。 \(f_0 = 0\) 设 \(P_i = \frac{p_i}{100}\) \[ f_i = f_{i-1} + P_i \cdot 1 + (1-P_i) \cdot (1 + f_i ) \] \[ f_i = \frac{f_{i-1}+ 1

杂题选讲。 CF1548A Web of Lies 分析 发现编号为 \(i\) 的节点只会对编号大于 \(i\) 的节点造成影响。 设 \(cnt_x\) 为与 \(x\) 相连且编号大于 \(x\) 的点的数量。如果 \(x\) 是所在连通块编号最小的节点，那么只要 \(cnt_x\neq 0\)，\(x\) 就一定被删除。发现最终剩下的一定是满足 \(cnt_x = 0\)