浅念づ昔夜's Blog

传送门

Solution

树上 dp，设 $f_u$ 为以 $u$ 为根的子树中好的非空子集数量。若 $u$ 为叶节点， 则 $f_u=1$。下面假设 $u$ 非叶节点，$v$ 为 $u$ 的子节点：

传送门

Solution

设 $A_0$ 所有元素之和为 $sum$。

若 $sum \le 0$ ，答案为 $0$。

传送门

Solution

初始化 $V_1=1$，其余 $V_i=0$，? 1 2 加入询问队列。

每次从队头取出询问 ? u v （保证 $V_u=1$，$V_v=0$），返回的结果是 $u$，$v$ 路径的中点 $p$。

传送门

Solution

用 mt19937 重新给 $1\sim 2\times 10^5$ 随机赋权为 $1\sim 10^9+7$ 中的一个数，然后判断两个区间内的元素之和是否相等即可。区间和保证在 long long 范围内。

传送门

Solution

设 $f_{i,k}$ 表示经过 $2^k$ 次操作后，位置 $i$ 上的数字为 $a_{f_{i,k}}$。初始化 $f_{i,0}=x_i$。转移方程

$f_{i,j}=f_{f_{i,j-1},j-1}$

传送门

Solution

首先拆环成链，令 $a_{i+n}=a_i$。

然后求出 $a_i$ 的前缀和 $s_i$。当 $s_i\equiv s_j\pmod M$ 时，说明 $M | a_{i+1}+\cdot \cdot \cdot + a_j$。

传送门

Solution

取出的 $a_i$ 若 $i>\lfloor \dfrac{n}{2} \rfloor$，则 $\text{median}(c_i)=a_{\lfloor \frac{n}{2} \rfloor}$。否则 $\text{median}(c_i)=a_{\lfloor \frac{n}{2} \rfloor + 1}$。

传送门

Solution

$k$ 进制下不进位加法的本质是，若两数第 $i$ 位相加后超过了 $k^i$，则减去 $k^i$。所以 $a+b \ge c$ 时问题有解，且当 $a+b>c$ 时，有 $k|(a+b-c)$。

前置知识

扩展欧几里得算法（辗转相除法）

对 $\forall a,b \in \mathbb{N^+}$，有

$\gcd(a,b)=\gcd(b, a\bmod b)$

传送门

Solution

设两个二进制串有 $k$ 位不同，那么它们的距离 $d=k$。设与串 $i$ 的距离为 $d_i$，题目即求使得 $\min\{d_1,d_2,d_3\}$ 最大的串。