代码位于文末。
A
[Loading...]
B
[Loading...]
C
NULL
D
网络流集合划分板子。
不会的建议左转 更板子的板子。
E
[Loading...]
F
发现 \(n\leq 10^{18}\) 的时候，树高 \(h\leq 9\)。
然后通过一些数学，可以求出父亲节点和子树大小。
然后按位考虑。
在更新一个节点 \(x\) 的子树为 \(1\) 的时候，根据子树大小奇偶性，可以直接跳没有操作过的父亲更新维护的答案。
在查询的时候，一种是祖先有操作过，那么答案只和子树大小奇偶性有关，否则就和当前节点维护的答案有关。
复杂度 \(O(nh\log V)\)。
G
首先第一个串的串首一定是第一个 \(1\)，设位于 \(p\)。然后枚举第二个串的串首位于 \(q\)。
然后通过一些尝试，猜测，答案一定形如：第一个串一定是 \([p,q)\) 之间的 \(1\) 构成的串，第二个串是 \(q\) 之后的字符构成的串。
然后没拍出来锅，说明是对的。😓
H
NULL
I
感觉挺套路的。
首先第一问通过贪心求得。
第二问，按位考虑。注意到比较大小的时候，如果高位不同，那么和低位无关。
所以从高到低考虑。按位的独立性引导我们思考 dp。所以考虑区间 dp \(f(k,l,r)\) 表示当前 dp 区间 \([l,r]\)，在决策第 \(k\) 位的方案数。
然后枚举第 \(k\) 位为 \(1\) 的第一个位置 \(t\)，有 \(f(k,l,r)=f(k-1,l,t-1)f(k-1,t,r)\)。
复杂度 \(O(n^3m)\)。区间 dp 常数小所以可以通过。
J
因为是 \(\prod=2^{2t+1}\)，所以每项一定都是 \(2\) 的次幂。
然后考虑观察一下。发现 \(m=2,6\) 一定不行。
首先思考一下，发现 \(a\) 一定存在一个循环同构使得 \(a_1=a_n=2^x\)。
为啥呢。考虑从 \(m\) 左右两侧构造。
那么一定是 \(2^y-m\) 类型的。对 \(2^y-m\) 继续思考，发现如果一直操作，能到达 \(2\)，那么稍微想一下就发现一定是不合法的。
K
[Loading...]
L
首先公式的意义是 \(\sum_i(\text{avg }S_i)^2\)。所以如果 \(S_i,S_j\) 值域有交一定不优。所以看作是在排序后的 \(a\) 上做切分。
考虑若组数确定，那么一定是贪心地让切分点尽可能变大。因为一个切分位置向小的方向移动，两侧的 \(\text{avg }S\) 都会变小。
然后是组数的问题。发现组数一定越多越好。
然后考虑构造方案。
首先前面一定是一堆 \(|S|=l\) 的，后面一定是一些 \(|S|=r\) 的，中间会有一个 \(|S|\in [l,r]\) 的。
因为组数已知，所以左右两部分的个数和中间的大小都可以算出来。
然后考虑快速计算，预处理长为 \(d\) 的作为 \(l\) 的切分的前缀贡献，作为 \(r\) 的后缀贡献。
然后需要预处理的量级就是调和级数 \(O(n\log n)\) 的。
M
NULL