联合省选 2022 解题报告

本文主要是介绍联合省选 2022 解题报告，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

D1T1 preprocessor

直接模拟。

D1T2 tree

极差不超过 \(K\)，考虑计算树上路径选值中最小值为 \(v\) 的方案：

将所有 \([l_i,r_i]\) 对 \([v,v+k]\) 取交后的答案减去 对 \([v+1,v+k]\) 取交的答案即可。

容易编一个树形 dp 做到 \(O(nr)\)，拿到 40pts。

考虑值域很大的情况进行离散化

求得所有 \([v,v+k]\) 的答案可以考虑离散化端点：\(r_i,l_i-1,r_i+k,l_i+k\)

对于相邻的端点内满足 \([l_i,r_i]\) 对其取交的结果的长度关于 \(v\) 的取值呈一次函数

容易分析出 \([v,v+k]\) 的答案在区间内为关于 \(v\) 的一个 \(n\) 或者 \(n+1\) 次函数

拉插即可，时间复杂度 \(O(n^3)\)

D1T3 community

D2T1 card

首先将所有卡牌丢进 \([1,2000]\) 的桶里。

由于一个不超过 2000 的数 \(v\) 小于 \(\sqrt v\) 的质数很少，我们考虑将一个数按其所含的大质数分类。

定义“大质数”为数 \(v\) 中所含的唯一一个不小于 43 的质数（43 也算是因为 \(43\times 47>2000\)），

特别的，不存在则定义为 1。

分类后在一类中我们仅考虑 41 即以内的共 13 个小质数，考虑状压，dp 出一类中得到 \(2^{13}\) 种质因子集合的方案数，复杂度 \(O(\pi(s)2^{13})\)。

对于一次询问，我们将所有出现的大质数拿出来，在这些类中我们都至少选一个，其他类随便选。

我们考虑这实际上是所有类做或卷积，出现的大质数的集合幂级数需要稍加改动，容易发现有逆。

时间复杂度 \(O(\sum c\times2^{13})\)。

D2T2 bracket

先建出括号树，考虑操作在树上的表现：

1. 将树上相邻的兄弟 \(a,b\) 进行修改，将 \(b\) 的所有儿子挂到 \(a\) 上，再将 \(b\) 也挂到 \(a\) 上，代价为 \(xv_a+yv_b\)。
2. 任意交换两个相邻的子树，代价为 \(0\)。

我们希望求得将树变成一条链的最小代价。

我们考虑从浅到深的将节点往下移动，显然答案不劣。

那么问题变为我们将前若干层操作为链后，当前层形如一个菊花，我们需要决策留下一个节点，并将当前层其他节点下放至所留节点下。

记当前层的权值总和为 \(S\)，极值分别为 \(mn,mx\)，个数为 \(k\)

分 \(x,y\) 的取值讨论：

1. \(x=0,y=0\)，答案为 \(0\)。

2. \(x=0,y=1\)，一次移动需要将往下层走的节点记一次贡献，那么每层留下权值最大的点即可

   容易用 multiset 维护。

3. \(x=1,y=1\)，一次移动还将对其选择的父亲记一次贡献，我们希望贪心的利用当前层的最小值作为父亲。

   考虑当我们选择留下的点不是最小值时，我们现将其他所有点移到最小值下，再将最小值移到所选点下即可。

   当我们选择的点就为最小值时不需要最后的一步移动，但容易算出贡献均为 \(S+(k-2)mn\)。

   我们直接贪心的留下最大值即可，既使下一层的 \(S\) 最小，又尽可能的保证 \(mn\) 不增大。

   仍然直接使用 multiset 维护即可。

4. \(x=1,y=0\)，一次移动仅记父亲一次贡献，我们还是利用当前层的最小值作为父亲。

   移动的构造与 Case 3 相同，若留下的节点权值为 \(w\)，贡献改成 \(w+(k-2)mn\)。

   仍然贪心，考虑仅有链的第 \(n\) 个点不需要因 \(w\) 贡献权值，我们希望这个位置为全局最大值；

   而由于 \(k_i\) 是固定的，我们希望每层的 \(mn\) 都尽量小。

   那么我们尽量让每层的 \(mx,mn\) 都传下去——这在 \(k_i>2\) 的层容易实现。

   我们考虑 \(n\) 层每一层决策时的个数 \(k_i\)，

   其应当呈现一段 1，一段 2，一段 >2，直到原树中该层不存在节点，剩一段每次下降 1 的序列。

   对于第一段 1，我们不需要处理，它们没有贡献。

   第一段 2 实际上的贡献为其间所有权值和去掉一个往下传的节点，记其为 \(x\)。

   我们容易计算后面的 \(mx\) 的贡献，考虑计算 \((k-2)mn\) 的贡献。

   由于有一个 \(x\) 往下传，其可能对应一个层数区间其为最小值，带来一定的贡献，而其不为最小值的后缀区间我们容易预处理。

   那么我们从小到大枚举可能的 \(x\)，进行双指针即可，时间复杂度为排序的 \(O(n\log n)\)

总复杂度 \(O(n\log n)\)

D2T3

这篇关于联合省选 2022 解题报告的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！