CSP2024 前做题情况 3

· · 个人记录

CSP2024 前做题情况 2。

P10391

康复题。

树上数颜色数量问题。然后树上莫队秒了。时间复杂度 O(n\sqrt{n})。

注意到不寻常的颜色范围 c_i\le 20。考虑树剖。我们通过状压可以将一个区间的颜色出现情况维护出来，然后放到线段树上维护即可。时间复杂度 O(n\log^2 n)。

P7810

考虑 DP。定义状态函数 f_{i} 表示前 i 个数划分，最多能分多少段。那么有转移方程：f_i=\max\{f_{j-1}|1 \le j <i\land a_j <a_i\land \gcd(a_j,a_i)>1\}+1。

考虑枚举 d|a_i(d \ne 1)，如果有：d|a_j，那么 \gcd(a_i,a_j) >1。那么对 a_i 分解质因数，得到 d_1,d_2,\dots ,d_k。那么有：f_i=\max\limits_{w=1}^{k}\max\limits_{j=1\land d_w|a_j\land a_j<a_i}^{i-1} f_{j-1} +1。注意到 \sqrt{10^9} 内，一个数的不同质因数数量不会超过 10 个。那么直接值域线段树优化 DP 可以做到 O(nω(V)\log n)。

AT_abc236_f

康复板子题。

考虑将代价从小到大排序。因为我们要将 [1,2^n-1] 这些数全部凑出来，而线性基刚好是维护这个的，所以直接用线性基板子。如果一个数 x 成功插入，则将代价加上即可。

接下来给出最优性证明。根据线性基的性质，可知在能够凑出 [1,2^n-1] 的情况下，所使用的数的数量是最少的。那么，如果有另一种方案 S' 的代价小于当前方案 S 的代价，对其进行分类讨论：

所以该算法一定能够求解最小代价。时间复杂度 O(2^nn)。

P6225

考虑对于一个区间 [l,r]，第 i 个数的贡献。不难发现，这只跟其奇偶性有关。那么有：v_i=a_i\times [((i-l+1)\times (r-i+1))\bmod 2=1]。展开一下，有：v_i=a_i \times [(i\times (l+r)-i^2-l\times r-l+r+1)\bmod 2=1]。

对 l,r 的奇偶性进行分类讨论：

也就是说，我们只需要维护出区间下标为奇数的数的和，为偶数的数的和就能直接求解了。使用树状数组维护的复杂度为 O(n\log n)。

P6278

考虑对于 i 的贡献。我们记 k 为原序列的逆序对数量。因为我们将所有 A_j \ge i 的数都变成 i 了。且对于 A_j <i，因为 A_k \ge A_j\land A_k \ge i \land i > A_j。所以实际影响的只有 A_j \ge j 的数的逆序对。所以只需要维护出 A_i=x 的逆序对数量，然后求个后缀和就行了。使用树状数组可以做到 O(n\log n)。

P1642

考虑 0/1 分数规划。

对于形如求：\frac{\sum\limits_{i\in S}a_i}{\sum\limits_{i\in S}b_i} 的最值问题，就可以使用 0/1 分数规划。具体的，如果要求最大值，我们二分答案 x。那么只需要判断是否存在 S，使得 \frac{\sum\limits_{i\in S}a_i}{\sum\limits_{i\in S}b_i}\ge x，即：\sum\limits_{i\in S}(a_i-x\times b_i) \ge 0。

对于这题，定义状态函数 f_{i,j} 表示 i 为根的子树中，删掉 j 个的最大价值。那么有：f_{u,j}=\max(f_{u,j},f_{u,j-k}+f_{v,k})。

该算法的时间复杂度为 O(n^2\log V)。一次 check 是 O(n^2) 的，证明大概是对于一对 (i,j)，只会在 \operatorname{LCA}(i,j) 时会产生 1 的代价，然后一共 n^2 个点。或者说，对于 siz\le m 的子树，每个点的贡献不超过 m。而对于 siz >m 的子树，每个点的贡献不超过 \frac{n}{m}。那么复杂度为 O(\frac{n}{m}\times m^2)，所以是 O(n^2) 的。

P2260

康复题，强转式子就行了。

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(n\bmod i)\times (m\bmod j)[i \ne j]\\= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(n\bmod i)\times (m\bmod j)-\sum\limits_{i=1}^{\min(n,m)}(n\bmod i)\times (m\bmod i)\\ =\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(n-i\times \lfloor \frac{n}{i}\rfloor)\times (m-j\times \lfloor \frac{m}{j}\rfloor)-\sum\limits_{i=1}^{\min(n,m)}(n\bmod i)\times (m\bmod i)\\ =\sum\limits_{i=1}^{n}(n-i\times \lfloor \frac{n}{i}\rfloor)\times \sum\limits_{i=1}^{m}(m-j\times \lfloor \frac{m}{j}\rfloor)-\sum\limits_{i=1}^{\min(n,m)}(n-i\times \lfloor \frac{n}{i}\rfloor)\times (m-i\times \lfloor \frac{m}{i}\rfloor)\\ =(n^2-\sum\limits_{i=1}^{n}i\times \lfloor\frac{n}{i}\rfloor)\times(m^2-\sum\limits_{i=1}^{m}i\times \lfloor\frac{m}{i}\rfloor)-nm\min(n,m)+n\sum\limits_{i=1}^{\min(n,m)}i\times \lfloor \frac{m}{i}\rfloor+m\sum\limits_{i=1}^{\min(n,m)}i\times \lfloor \frac{n}{i}\rfloor-\sum\limits_{i=1}^{\min(n,m)}i^2\times \lfloor\frac{n}{i}\rfloor\times \lfloor\frac{m}{i}\rfloor

令 f(n,m)=\sum\limits_{i=1}^{n}i\times \lfloor\frac{m}{i}\rfloor,g(n,m,k)=\sum\limits_{i=1}^{n}i^2\times \lfloor \frac{m}{i}\rfloor\times \lfloor \frac{k}{i}\rfloor，那么式子可以写成：(n^2-f(n,n))\times (m^2-f(m,m))-nm\min(n,m)+nf(\min(n,m),m)+mf(\min(n,m),n)-g(\min(n,m),nm)。

现在只需要求出 f(n,m),g(n,m,k) 是多少就行了。不难发现，这玩意是个整除分块。那么该算法的时间复杂度就是 O(\sqrt{V}) 的了。

P9619

考虑枚举边。我们枚举生成树上有一条 u\to v 的边，那么这两个点与其它 n-2 个点形成的生成树的数量根据 Prüfer 序列为：n^{n-2+1-2}\times 2 \times \prod\limits_{i=1}^{n-2} 1。那么这条边的贡献就是 (a_u ⊕a_v)\times 2\times n^{n-3}。发现后面是定值，那么有总价值为：2\times n^{n-3}\times \sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}a_i ⊕ a_j。拆位算贡献就行了。时间复杂度 O(n)。

P9681

不难发现，一个区间 [l,r] 合法当且仅当：a_r>0\land \forall i(l\le i <r),a_i \le 0\land \sum\limits_{i=l}^{r} a_i >0。我们记 pre_i 表示当 r=i 时，l 的最小值。那么对于区间询问，有答案为：\sum\limits_{i=l}^{r} i-\max(l,pre_i)。

注意到，pre_i 具有单调性，那么我们只需要二分然后前缀和就行了。时间复杂度 O(n\log n)。

P7335

考虑暴力 DP。是 O(n^3) 的。然后枚举长度的时候取长度不超过 100 就能过了。证明的话，因为数据随机。所以长度不太大。

做完了，明天就 CSP2024 了。