写在前面

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

T1 袜子分配

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

暴力可以获得至少分。

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

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

故时间复杂度为，可以得到分。

开始时，有种不同的取法，只有种拿法可以获得快乐值。

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

对于，答案为。

T2 艰难睡眠

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

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

暴力获取大概可以获得分或更多。

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

时间复杂度。这样显然只能获得大概分，因为这个有那么夸张。

用单调队列或是其他的做法来解决问题可以获得分。

T3 路径难题

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

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

每个公交车建条边的话，大概可以得到分？

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

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

T4 牛半仙的妹子序列

作者：hahahahahahahahah

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

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

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

考虑从前往后 DP。

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

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

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