文章目录
Solutions
A
最优区间 [ l , r ] [l,r] [l,r] 必然满足 l + 1 = r l+1=r l+1=r。
因此答案为
max i = 1 n { a i × a i + 1 } \max_{i=1}^n \{a_i \times a_{i+1}\} i=1maxn{ai×ai+1}
可以通过反证法来证明。复杂度 O ( ∑ n ) O(\sum n) O(∑n)。
B
考虑枚举 a i ∣ a j = x a_i|a_j=x ai∣aj=x。此时， a i , a j a_i,a_j ai,aj 均为 x x x 的子集，即 a i ∈ x , a j ∈ x a_i \in x,a_j \in x ai∈x,aj∈x。
此时，我们只需要保证 a i ∈ x , a j ∈ x a_i \in x,a_j \in x ai∈x,aj∈x 而不需保证 a i ∣ a j = x a_i|a_j=x ai∣aj=x。这是因为， a i , a j a_i,a_j ai,aj 只会在恰好枚举到 x = a i ∣ a j x=a_i|a_j x=ai∣aj 时产生最大的候选值，不会影响答案。
因此，我们只需要对于每一个 x x x，求出所有 a i a_i ai 是 x x x 子集的最大 i i i 以及严格次大 i i i。
考虑 dp \text{dp} dp。
令 f S f_S fS 为集合 S S S 的最大值与严格次大值组成的二元组。
转移的时候，初始化 f S = ( − ∞ , − ∞ ) f_S=(-∞,-∞) fS=(−∞,−∞)，枚举所有属于 S S S 的位置 p p p，并用 f S − { p } f_{S-\{p\}} fS−{p} 来更新 f S f_S fS。最后，我们再用 ( x S , y S ) (x_S,y_S) (xS,yS) 更新 f S f_S fS 即可。其中 x S , y S x_S,y_S xS,yS 表示原序列中所有值为 S S S 的位置编号的最大值以及严格次大值。
时间复杂度 O ( ∑ n log n ) O(\sum n \log n) O(∑nlogn)。
C
考虑二分答案。
令当前二分到了 v v v，我们需要判断 n ⊕ 0 , n ⊕ 1 , ⋯ , n ⊕ m n \oplus 0,n \oplus 1,\cdots,n \oplus m n⊕0,n⊕1,⋯,n⊕m 是否覆盖了 [ 0 , v ] [0,v] [0,v] 中的所有数。答案即为最终的 v v v 加上 1 1 1。
根据 ⊕ \oplus ⊕ 的运算法则，我们只需要判断
max i = 0 v { n ⊕ i } ≤ m \max_{i=0}^v \{n \oplus i\} \le m i=0maxv{n⊕i}≤m
我们只需要按位试填即可。时间复杂度 O ( ∑ log 2 n ) O(\sum \log^2 n) O(∑log2n)。
将二分改为倍增即可做到 O ( ∑ log n ) O(\sum \log n) O(∑logn)，二者都可以通过。
D
这道构造题已经被我喷死了。
- 若
n
=
1
n=1
n=1，
a
n
s
=
ans=
ans=
A。 - 若
n
≡
0
(
m
o
d
2
)
n \equiv 0 \pmod 2
n≡0(mod2)，先输出
n
2
\frac n 2
2n 个
a，然后输出b，然后再输出 n 2 − 1 \frac n 2-1 2n−1 的a。 - 若
n
≡
1
(
m
o
d
2
)
n \equiv 1 \pmod 2
n≡1(mod2)，先输出
n
−
1
2
\frac {n-1} {2}
2n−1 个
a，然后输出b,c，最后再输出 n − 1 2 \frac {n-1} {2} 2n−1 个b。
E
好题，性质非常强，缺了最后一步只会 O ( n 2 ) O(n^2) O(n2) 算法。
看到 gcd \gcd gcd，不难想到容斥。即，令 f i f_i fi 表示满足 i ∣ a 1 , i ∣ a 2 , ⋯ , i ∣ a n i|a_1,i|a_2,\cdots,i|a_n i∣a1,i∣a2,⋯,i∣an 的可达 a a a 的数量，那么可以在调和级别的复杂度内递推出答案。所以关键在于求出每一个 f f f。
首先考虑求出 f 1 f_1 f1。为方便叙述，令第 x x x 个被删去的节点 y y y 的权值为 x x x，记做 w y = x w_y=x wy=x。不难发现，只要钦定了每一条边的两端的权值大小，就唯一确定了序列 a a a。具体来说， a i a_i ai 就是所有与 i i i 相邻且权值比 i i i 大的节点数量。因此，不难得到，不同的序列 a a a 共有 2 n − 1 2^{n-1} 2n−1 个。即， f 1 = 2 n − 1 f_1=2^{n-1} f1=2n−1。
再考虑对于每一个超过 1 1 1 的 i i i 求出 f i f_i fi。我们先不考虑计数，先考虑构造出一个合法解。可以得到下面的算法——对树进行一遍 dfs \text{dfs} dfs。当搜索完了以 u u u 为根的子树后，我们考虑钦定 w u w_u wu 与 w p w_p wp 的大小关系，其中 p p p 为 u u u 的父亲。于是有：
- 若当前 u u u 的度数为 i i i 的倍数，则须 w p < w u w_p<w_u wp<wu。
- 若当前 u u u 的度数模 i i i 等于 − 1 -1 −1，则须 w p > w u w_p>w_u wp>wu。
- 否则无法构造出一组合法解。
仔细观察我们的构造方案，发现只要树的形态固定，每一个 u u u 对应的情况也是固定的。从而得到，对于所有 [ 2 , n ] [2,n] [2,n] 中的 f i f_i fi 均为 0 0 0 或 1 1 1。总而言之，我们只需要对于 f [ 2 , n ] f[2,n] f[2,n] 分别尝试构造，并令 f 1 = 2 n − 1 f_1=2^{n-1} f1=2n−1 即可得到 f f f。
然而，这样的时间复杂度是 O ( n 2 ) O(n^2) O(n2) 的，无法接受。
此时此刻，就非常容易跑偏了；比如我就在用各种各样的神仙数据结构来尝试维护这些 f f f 的转移。我们需要跳出这些性质以及做法，直接着眼于最终的答案中，有哪些位置是无效的，是不需要跑的。
观察到，树上所有的边均会让恰好一端的 a a a 加上 1 1 1。换言之， ∑ i = 1 n \sum_{i=1}^n ∑i=1n 就是边数，即 n − 1 n-1 n−1。因此，对于那些无法整除 n − 1 n-1 n−1 的 i i i 而言， f i f_i fi 的值总是 0 0 0。
综上所述，我们只需要考虑那些是 n − 1 n-1 n−1 约数的 i i i。
总复杂度 O ( m n + n ln n ) O(mn+n \ln n) O(mn+nlnn)，其中 m m m 为 n − 1 n-1 n−1 的约数个数。