NOI2022联合省选 题解

NOI2022联合省选 题解
day1的题解咕咕咕了，有空再写吧（好吧，看到这么长的题面+大模拟就没有写题解的欲望了……

注：非官方题解，不保证绝对正确，做法不一定是官方做法

注2：代码请见这篇blog

d2t1：传送门https://www.luogu.com.cn/problem/P8292
题意：给定一些数字，每次询问一些质数，要求从给定的数字中选出一个子集，使得乘积被所有询问的质数整除，求方案数。

数据范围： n ≤ 1 0 6 , m ≤ 1500 , ∑ c i ≤ 18000 n\leq 10^6, m \leq 1500, \sum c_i \leq 18000 n≤106,m≤1500,∑ci​≤18000，值域范围 2000 2000 2000 。

sol：注意到这么大的 n n n 其实没用（只要统计每种数有多少个就行了），同样 m m m 的范围其实也没什么用，决定复杂度的其实是 ∑ c i \sum c_i ∑ci​ 和值域范围。

对于这道题而言，一个数的影响显然只与它的质因子集合有关，因此你可以把所有质因子集合相同的数合并，不过这其实并不本质，因为仍然会剩下 1200 1200 1200 多个数。

2000 2000 2000 的值域范围很耐人寻味，我们可以观察得到这么一个性质：由于 43 × 47 = 2021 > 2000 43\times47=2021>2000 43×47=2021>2000 ，因此一个数最多只会包含一个 ≥ 43 \geq 43 ≥43 的质因子。

而 < 43 <43 <43 的质数一共只有 13 13 13 个。

假设我们根本不关心那些 < 43 <43 <43 的质因子（比如，如果询问里没有的话），那这题就很简单了：把所有数按照含有哪个 ≥ 43 \geq 43 ≥43 的质因子进行分类（可能包含某一个，也可能不含），设每一类有 a i a_i ai​ 个数，那么对于一类而言，如果询问集合里包含这一类的质因子的话，就代表这一类的数至少要选一个，方案数是 2 a i − 1 2^{a_i}-1 2ai​−1 ；否则就是可以任意选，方案数是 2 a i 2^{a_i} 2ai​ 。

把每类的方案数乘起来即可。

现在要把前 13 13 13 个质因子考虑进来，于是我们可以大力容斥：枚举 {前 13 13 13 个质因子} ∩ \cap ∩ 询问集合 的子集，要求所选的数里必须不包含这个子集中的质因子。

然后只需要把不符合条件的数扔掉之后重复刚才只考虑 ≥ 43 \geq43 ≥43 的质因子的情形就行了。

总复杂度 O ( 2 13 ∑ c i ) O(2^{13}\sum c_i) O(213∑ci​) ，看起来不小但实测跑得飞快。

d2t2：传送门https://www.luogu.com.cn/problem/P8293
题意：给定一个括号序列，，每个左括号有一个权值。

你有如下 *** 作：一是把 (A)(B) 变成 (A()B) ，代价为 x × ( A ) x \times (A) x×(A) 中第一个左括号的权值 $ + y \times (B)$ 中第一个左括号的权值，其中 x , y ∈ 0 , 1 x,y \in {0,1} x,y∈0,1 ；二是把 AB 变成 BA ，无代价。

问把原串变成 (((...()...))) 的最小代价。

sol：仔细观察题目中的 *** 作，发现其实答案只与每个括号在哪一“层”有关。

*** 作一的本质是花一定的代价把一对括号扔进里层，我们总是可以从外到里 *** 作，这样 *** 作到某一层时，这一层里的所有括号就可以用 *** 作二进行任意交换。

用vector记录每层的数，每次 *** 作一可以进一步抽象为“用一个数（即 (A) 中第一个左括号的价值）把另一个数（即 (A)中第一个左括号的价值）放进里层”。

下面我们称 (A) 中第一个左括号的价值为“辅助”。

根据 x , y x,y x,y 的不同可能的取值分类讨论：
如果 x = 1 , y = 1 x=1,y=1 x=1,y=1 ：假设当前层有 m m m 个数，最大值是 m x mx mx ，最小值是 m n mn mn ，总和是 s u m sum sum ，那么无论是最终被放进去的还是留在外面的至少都要有一次的代价，同时总的代价次数一定是 2 ( m − 1 ) 2(m-1) 2(m−1) ，那么显然可以贪心地用最小的数当辅助，把多出来的 m − 2 m-2 m−2 次代价全都算在 m n mn mn 头上。

同时放尽可能小的数进去使得下一层尽可能小，只需最后用最大的数把最小的数放进去。

代价为 ( m − 2 ) × m n + s u m (m-2)\times mn+sum (m−2)×mn+sum 。

如果 x = 0 , y = 1 x=0,y=1 x=0,y=1 ：这种情况也很简单，因为代价只与被放进去的数有关，那么就每次贪心地把尽可能小的数往里扔就行了。

每一层把最大的数留在外面，这一层的代价为 s u m − m x sum-mx sum−mx 。

最复杂的情况是 x = 1 , y = 0 x=1,y=0 x=1,y=0 ，即代价算在辅助头上的情况：对于每一层，首先要决策把哪个数留下来，然后用最小的数把其余的数放进去，最后再用留下来的数把最小的数放进去。

问题是如何决策呢？
计算所有层的总代价，我们发现除了最里层的数以外，每个数都会在某一层被留下来并计算一次贡献。

既然这样，如果我们确定了最里层的数是多少，每一层就可以贪心地留下当前层的（除了要被放进最里层的数以外的）最大数，因为这样可以让尽可能小的数往里走，以减小里层辅助的代价。

很自然的想法是最里层放全局最大数，这样的决策如下：
当还没有遇到全局最大数时，留下本层最大，代价为 m n × ( m − 2 ) + m x mn\times (m-2)+mx mn×(m−2)+mx ；遇到了全局最大数时，留下本层次大，代价为 m n × ( m − 2 ) + c d mn\times (m-2)+cd mn×(m−2)+cd （ c d cd cd 为本层次大值）。

这就完了吗？我们发现存在反例：

1 10
9 9

如果第一层把全局最大值 10 10 10 放进去，总代价为 1 + 9 + 9 + 9 = 28 1+9+9+9=28 1+9+9+9=28 ；但如果把 1 1 1 放进去，代价为 10 + 1 + 9 + 1 = 21 10+1+9+1=21 10+1+9+1=21 。

问题出在哪里？
在于“遇到全局最大数后把当前层的次大值留下”这一步。

如果这一层恰好只有 2 2 2 个数，而被留下的恰好是一个很小的数，就失去了把它放进里层用来当辅助的机会。

不过仔细分析，发现这种情况只可能出现在一开始，即第一层只有两个数的情况（如果第一层只有一个数，显然可以直接忽略这一层，从下一层开始做）。

这是因为每层都只会留下一个数，而题目性质保证了每层至少也会多出来一个数，因此如果进入某一层时已经有超过 2 2 2 个数，一直到最后一步之前都一定是超过 2 2 2 个数。

于是我们可以在一开始遇到这种情况时特判把较小的数放进去，但是紧接着又会有问题：如果下一层只有 1 1 1 个数，可能又会面临刚才的尴尬情况。

进一步，如果我们面临如下情况：前 k k k 层分别有 2 , 1 , 1 , . . . 2,1,1,... 2,1,1,... 个数， 我们显然不能在每一层都枚举。

进一步，我们把这前 k k k 层一起处理，发现无非只有两种可能：要么把这 k k k 层的最大值扔进里面，用于扔进最里层；要么把这 k k k 层的最小值扔进里面，用于当里层的辅助。

无论哪种情况这 k k k 层的代价均为所有数的和减去被放进去的数。

因此只要讨论这两种情况，后面按照原策略贪心即可。

总复杂度 O ( n log ⁡ n ) O(n \log n) O(nlogn)，瓶颈主要在于排序和/或用set维护当前层的最值。

d2t3：传送门https://www.luogu.com.cn/problem/P8294
题意：给定树，点有点权。

每次切断一条边，交换这条边两个端点的点权，代价为这两个点权之和。

求把所有边都切断的最小代价。

sol：第一种dp方案：设 f [ x ] [ y ] [ z ] f[x][y][z] f[x][y][z] 表示点 x x x 的子树，把子树内的点 y y y 换出去， 外面的 z z z 换进来的答案。

转移：考虑与 x x x 相邻的 3 3 3 条边的 *** 作顺序：
1、如果先 *** 作 x x x 与父亲的边，则被换出去的是 x x x ，枚举换进来的点 z z z 。

假设剩余两条边先 *** 作左子树，那么在左子树里枚举换出去的点 w w w ，把它换到 x x x 的位置之后换进右子树，枚举换出去的点 p p p ，则有： f [ x ] [ x ] [ z ] = m i n ( f [ x ] [ x ] [ z ] , f [ l c ] [ w ] [ z ] + f [ r c ] [ p ] [ w ] + c [ x ] + c [ z ] ) f[x][x][z]=min(f[x][x][z], f[lc][w][z] + f[rc][p][w] + c[x] + c[z]) f[x][x][z]=min(f[x][x][z],f[lc][w][z]+f[rc][p][w]+c[x]+c[z]) 。

剩余两条边先 *** 作右子树同理。

2、如果先 *** 作 x x x 与左儿子的边，则左子树换进来 x x x ，枚举换出去的点 w w w ；假设再 *** 作 x x x 与父亲的边，那么换出去 w w w ，枚举换进来的 z z z ；最后把 z z z 换进右子树，枚举换出去的点 p p p ，则有： f [ x ] [ w ] [ z ] = m i n ( f [ x ] [ w ] [ z ] , f [ l c ] [ w ] [ x ] + f [ r c ] [ p ] [ z ] + c [ z ] + c [ w ] ) f[x][w][z]=min(f[x][w][z],f[lc][w][x] + f[rc][p][z] + c[z] + c[w]) f[x][w][z]=min(f[x][w][z],f[lc][w][x]+f[rc][p][z]+c[z]+c[w])。

3、如果先 *** 作 x x x 与左儿子的边再 *** 作 x x x 与右儿子的边，那么要把 w w w 换进右子树，枚举换出去的点 p p p ；最后把 p p p 换出去，枚举换进来的点 z z z ，则有： f [ x ] [ p ] [ z ] = m i n ( f [ x ] [ p ] [ z ] , f [ l c ] [ w ] [ x ] + f [ r c ] [ p ] [ w ] + c [ z ] + c [ p ] ) f[x][p][z]=min(f[x][p][z],f[lc][w][x] + f[rc][p][w] + c[z] + c[p]) f[x][p][z]=min(f[x][p][z],f[lc][w][x]+f[rc][p][w]+c[z]+c[p])。

4，5：如果先 *** 作 x x x 与右儿子的边，与2，3同理。

虽然看起来枚举很多，但是复杂度是 O ( n 3 ) O(n^3) O(n3) 的，这是因为所有的 *** 作可以归结为：枚举点 x x x ，并从左子树、右子树、子树外各枚举一点。

众所周知枚举左右子树的点是 O ( n 2 ) O(n^2) O(n2) 的（类似于树形背包，只在lca处算贡献），再加一个子树外就是 O ( n 3 ) O(n^3) O(n3) 的。

但是这一算法也没法进一步优化了，因为状态本身已经 O ( n 3 ) O(n^3) O(n3) 了。

我们需要换一种状态！现在设 f [ x ] [ v ] [ d ] f[x][v][d] f[x][v][d] 表示点 x x x 的子树内， v v v 被换出去，被换进来的点最终停在距离 x x x 为 d d d 的位置上的答案。

并且不计入换进来的点产生的贡献。

我们先看状态数：注意到 v v v 和 d d d 一定不会来自同一侧，因此套用树形背包可知状态数已经是 O ( n 2 ) O(n^2) O(n2) 的了 。

同样分类讨论转移：
1、先 *** 作 x x x 与父亲 ：假设再 *** 作左儿子，则换进来的点最终停在左侧，那么枚举右侧深度 d ′ d' d′ ，左侧换出来的点 v v v 以及右侧换出来的点 v ′ v' v′，有： f [ x ] [ x ] [ d ] = m i n ( f [ x ] [ x ] [ d ] , f [ l c ] [ v ] [ d − 1 ] + f [ r c ] [ v ′ ] [ d ′ ] + c [ v ] × ( d ′ + 1 ) + c [ x ] ) f[x][x][d]=min(f[x][x][d],f[lc][v][d-1]+f[rc][v'][d']+c[v]×(d'+1)+c[x]) f[x][x][d]=min(f[x][x][d],f[lc][v][d−1]+f[rc][v′][d′]+c[v]×(d′+1)+c[x]) 。

再 *** 作右儿子同理。

2、先 *** 作左儿子再 *** 作父亲：则换进来的点最终停在右侧，枚举左侧深度 d ′ d' d′ ，左侧换出去的点 v v v ，右侧换出去的点 v ′ v' v′ ，有： f [ x ] [ v ] [ d ] = m i n ( f [ x ] [ v ] [ d ] , f [ l c ] [ v ] [ d ′ ] + c [ x ] × ( d ′ + 1 ) + f [ r c ] [ v ′ ] [ d − 1 ] + c [ v ] ) f[x][v][d]=min(f[x][v][d],f[lc][v][d']+c[x]×(d'+1)+f[rc][v'][d-1]+c[v]) f[x][v][d]=min(f[x][v][d],f[lc][v][d′]+c[x]×(d′+1)+f[rc][v′][d−1]+c[v]) 。

3、先 *** 作左儿子再 *** 作右儿子：则换进来的点最终停在 x x x 处。

枚举左侧深度 d ′ d' d′，左侧换出去的点 v ′ v' v′ ，右侧深度 d d d ，右侧换出去的点 v v v ，有： f [ x ] [ v ] [ 0 ] = m i n ( f [ x ] [ v ] [ 0 ] , f [ l c ] [ v ′ ] [ d ′ ] + c [ x ] × [ d ′ + 1 ] + f [ r c ] [ v ] [ d ] + c [ v ′ ] × ( d + 1 ) + c [ v ] ) f[x][v][0]=min(f[x][v][0],f[lc][v'][d']+c[x]×[d'+1]+f[rc][v][d]+c[v']×(d+1)+c[v]) f[x][v][0]=min(f[x][v][0],f[lc][v′][d′]+c[x]×[d′+1]+f[rc][v][d]+c[v′]×(d+1)+c[v]) 。

4，5：先 *** 作右儿子，与2，3同理。

乍一看枚举的复杂度直接飞起，别急，让我们冷静分析：
2、 d d d 显然不超过右子树的深度，那么只要枚举 d ′ d' d′ 不超过左子树的深度，然后不难发现 v v v 和 v ′ v' v′ 根本不用枚举，可以事先预处理出最小值（因为 v v v 的贡献只与 d d d 有关， v ′ v' v′ 的贡献只与 d ′ d' d′ 有关）。

这一步是 O ( n 2 ) O(n^2) O(n2) 的；
3、枚举左右两侧的 d d d 和 d ′ d' d′ ，同样可以预处理 v v v 和 v ′ v' v′ 的最小值而省去枚举，这一步也是 O ( n 2 ) O(n^2) O(n2) 的；
1、这是比较麻烦的一步，因为枚举 d ′ d' d′ 之后，虽然 v ′ v' v′ 的影响可以预处理最小值，但是 v v v 的贡献与 d d d 和 d ′ d' d′ 都有关，没法直接预处理最小值。

但是注意到，如果固定 d d d ，那么 v v v 的贡献随着 d ′ d' d′ 的变化就是一个一次函数。

于是只需要跑一个斜率优化，枚举 d ′ d' d′ 的同时让 v v v 在下凸壳上跑即可。

那么这一步也被优化到了 O ( n 2 ) O(n^2) O(n2) 。

最终，总的时空复杂度均为 O ( n 2 ) O(n^2) O(n2) 。