A

手玩一下可以发现大于等于2时， 的答案为 中 1 的数量和长度的和减去 2

原理是开头的 1*可以用一次 +2实现

当然我们也可以dp求出一定范围的答案，然后对 反复执行 -1 , /2的操作,直到落到范围内

B

显然所有的点和边构成了一个基环树森林,只要判断每一棵基环树,取最长的链加上环即可

C

二分图 匈牙利即可

D

数位dp

设计一个dp计算小于等于x的所有数含有1的和, 只用计算

我们从高位往低位枚举 的二进制位

假如这一位是 1 , 那么

​ 当这位取0, 后面的 位都可以随便取,直接加上 中的 1 的个数即可

​ 当这位取1,这个 1 的贡献为后面可以跟的数的个数, 显然就是后 位的值

假如这一位是0, 那么直接枚举到下一位即可

E

确定一个位置有没有贡献只用看相邻的两个点即可,修改子树时只用考虑子树根和其父亲节点

查询用树链剖分维护即可

F

总共的取值为

这个东西是调和级数 直接枚举即可

G

从 1 到 n 枚举, 使用神力的地点一定是消耗最大的k个点,因此从 1 到 n 枚举, 用 set 或者堆维护最大的k个即可

H

枚举对每一位操作的贡献, 取最大的加到原数组即可

I

显然是把最大的数移到最前面最大, 相同大小取操作次数少的

J

我们可以计算每个点的最大值

首先看 1 的限制, 每个点的最大值为往上,往右,往右上的最大距离的最小值,这个通过前缀和可以解决

接着看 0 的限制,每个点延长出的三条线会把右上的矩形分为两块,上面半块决定了最大高度,下面半块决定了最大宽度,同样可以前缀和维护

总复杂度O(n^2)

注意数组不要开太多, 题目内存有限,会mle

常数较小的O(n^2log) 也能通过,实现就是把 0 的限制换成二分

K

因为可以任意删边, 所以最后的联通块可以任意组合 显然是两个连通块数量最接近时最大

L

相当于删去所有桥, 我们关心的是删完后每个块有多少点

然后我们要尽量构造点数接近 (n >> 1) 的块, 这样才能让答案最大

显然类似01背包可以完成, 但是01背包的复杂度无法通过

考虑优化, 通过二级制组合, 把同样大小的块分组计算, 因为 本质不同的块的数量是 O(sqrt(n)) 的

所以总过程优化到 O(nsqrt(n))