Gym 101964 题解

A

讨论位数相不相同,然后 2^n 枚举每一位是否进位。位数相同那么位与位之间相互不影响,直接算答案。位数不同可以直接把所以位置推出来判。

B

n(n-1)(n-2)-3n(n-\frac{n}{2}-1)(n-\frac{n}{2}-2)

C

直接暴力。

D

一条边走 \ge 3 次肯定不优,走一次还是走两次只与子树里跳跃次数的奇偶性有关。一个点跳跃多次也不优,所以子树内跳跃次数是 O(\mathrm{size}) 的,树形背包。

E

算每个点贡献区间。

F

b 中每个位置 i 找出这个颜色的来源位置 t_i,显然所有 t_i \to i 的连线关系是不交叉的,不然会覆盖掉。将 t_i 的颜色染到 i 上只需两步(先染 t_ii 除了 t_i 的部分,然后染 t_ii),所以总步数 \le 2n。染的时候注意顺序,t_i<i 的从右往左染,反之亦然。

G

一个 2^k\times 2^k 的矩阵如果不全相同则贡献 4。子矩阵全相同当且仅当行状态全相同且列状态全相同。对这 n 种大小的矩阵分别维护完全相同的矩阵数。

H

考虑贪心,硬点一条边两个端点不同色后,剩下的点依次贪心染色,那么两端不同色的边数至少是 \left\lfloor\frac{m}{2}\right\rfloor+1。此时如果 0\to1 的边数不足 1\to0 的边数的话将所有点反色即可保证 0\to 1 边至少有这个值的一半,即至少是 \left\lfloor\frac{m}{4}\right\rfloor+1

I

FLOJ 340。

J

跑最短路后按题意模拟。

K

cdq 分治。

发表评论

电子邮件地址不会被公开。 必填项已用*标注