2020-10-29 22:17 浙江大学 C++

关注

【题解】2020牛客NOIP赛前集训营-提高组（第六场）

写在前面

T2的语言组织非常欠妥，十分抱歉。

T1 袜子分配

注意题目要求误差需要小于 $10^{-8}$ ，如果直接输出保留的位数不够多会扣很多分。

暴力可以获得至少 $30$ 分。

定义d[i][j]表示现在有 $i$ 个单只袜子，有 $j$ 对双只袜子到取完的数学期望。

每次取时可以枚举拿第一只和拿第二只的情况，可以在O(1)的时间复杂度下转移。

故时间复杂度为 $O(n^2)$ ，可以得到 $80$ 分。

开始时，有 $2n(2n-1)$ 种不同的取法，只有 $n$ 种拿法可以获得快乐值。

可以通过数学推导或者观察得出结论：

对于 $n$ ，答案为 $\frac{n}{2n-1}$ 。

T2 艰难睡眠

本意是处理一个环上的问题。但是题目描述好像给大家造成一定困扰，再次抱歉。

考虑枚举牛牛睡觉的时间，相当于需要对每个人取睡觉不干扰牛牛部分的最小值。

暴力获取大概可以获得 $40-50$ 分或更多。

可以用multiset预处理区间最小值，或者用某些数据结构在线维护。

时间复杂度 $O(nm \log m)$ 。这样显然只能获得大概 $80$ 分，因为这个 $nm$ 有 $10^7$ 那么夸张。

用单调队列或是其他 $O(nm)$ 的做法来解决问题可以获得 $100$ 分。

T3 路径难题

考察最短路和构图技巧。如果是独立思考的结果的话，证明你已经有点懂最短路了。

如果无视公交车的话，可以得到 $20$ 分。

每个公交车建 $t_i^2$ 条边的话，大概可以得到 $60$ 分？

构图上考虑将每路公交车构造一个点：让该路公交车对应的所有站台都有向边连接到它；它通过有向边连接到该路公交车对应的所有站台。然后跑dijkstra即可。因为单次打车和多次打车有舍入上的出入，所以需要维护一个下一次收费的距离，如果坐公交车就清空该距离。

这样的话时间复杂度是O(m\log m)级别的。

T4 牛半仙的妹子序列

作者：hahahahahahahahah

把题目转化为对一个极长上升子序列计数。

一个子序列 $A$ 是极长上升子序列，当且仅当不存在一个不同于 $A$ 的上升子序列 $B$ ，且 $B$ 包含 $A$ 中所有的元素。

设 $f_i$ 表示以第 $i$ 个位置结尾的子序列的极长上升子序列个数。

考虑从前往后 DP。

考虑怎样的j能够转移到 $f_i$ ，在位置 $(j,i)$ 之间不存在比 $v_j$ 大且比 $v_i$ 小的数，如果只考虑“比 $v_i$ 小”这个限制，可以建一个权值线段树，含两个标记，一个为是否能产生贡献，一个为贡献的大小，每次更新对应权值，查询只需查询目前加入的小于当前数的权值，单次复杂度 $O(\log n)$ 。

考虑加上“比 $v_j$ 大”这个限制，当出现一个权值被夹在中间的数之后， $j$ 就不能贡献了，于是我们考虑一个线段树区间取 $\min$ 的操作：将能否产生贡献的标记改成一个权值 $mn$ ,在扫完原数列的一个数 $j$ 后，将 $mn_j$ 赋为 $inf$ ，在查询第 $i$ 位的答案时，先将线段树 $[1,vi]$ 的所有点的 $mn$ 对 $v_i$ 取 $\min$ ，线段树 $[1,vi]$ 中的 $mn$ 等于 $v_i$ 的数的贡献和即是答案。

考虑如何维护线段树取 $\min$ ，记录一个 $mx$ 表示区间最大， $se$ 表示区间严格次大。若区间取 $\min$ 的值大于等于 $mx$ ，return；若 $se$ ,修改 $mx$ 和对应贡献，打个 $tag$ ;否则就暴力递归处理，一次暴力递归复杂度是 $O(\log n)$ 的，一次递归 $mn_j$ 的种数会至少减 $1$ ，而种数是 $O(n)$ 的，所以总时间复杂度 $O(n\log n)$