被 Qingyu 安利了这场。
B
简要题意.
给定 \(n,m\) 和 \(n\) 个区间 \([l_i, r_i] \subseteq [1, m]\)，每个区间有权值 \(c_i\)。
你需要选择一个区间的子序列使得可以从每个区间中选出一个正整数，按顺序排列之后得到一个不降序列。
最大化权值，并求出权值最大时的方案数。\(n,m \le 2\times 10^5\)，\(1 \le c_i \le 10^9\)。
直接 DP，注意到每次只需要用前缀最大值更新 \(l\) 处的 DP 值（因为只需要本质不同），线段树优化即可。
C
简要题意.
给定 \(n,w\) 和 \(n\) 个文件，将要通过一个总吞吐量为 \(w\) 的网络。
对于每个文件，其会在时刻 \(t_i\) 开始传输，大小为 \(s_i\)，优先级为 \(p_i\)。
对于一个大小为 \(s\) 的文件，若当前只有其在传输，则需要 \(s/w\) 秒。
若多个文件同时传输，则吞吐量会正比于其优先级分配。
请求出每个文件传输完毕的时刻。\(n \le 2\times 10^5\)，\(w \le 10^7\)，\(p_i \le 100\)。
自然直接按时间顺序处理所有传输，也就是按时间扫描线。
不妨维护当前正在进行传输的文件目前的结束时刻（即假设吞吐量不变的情况下，其结束时刻），设为 \(f_i\)。
设下一个文件为 \((t_0, s_0, p_0)\)，记当前优先级之和为 \(P\)。
则第 \(i\) 个文件还剩下 \((f_i-t_0) \cdot \frac{p_i}P w\) 的大小没有传输，而吞吐量变为 \(\frac{p_i}{P+p_0} w\)，因此 \[
f_i \gets t_0 + \frac{(f_i-t_0) \cdot \frac{p_i}P w}{\frac{p_i}{P+p_0} w} = \frac{P+p_0}P f_i - \frac{p_0}P t_0
\]
也就是说我们需要一个数据结构以支持以下操作：
- 将所有元素左复合一个一次函数 \(k_0x+b_0\)。
- 查询最小值。
- 删除最小值。
- 插入。
注意到这里复合的一次函数并不改变大小关系，所以我们只需要一个带有整体标记的堆即可。
I
简要题意.
给定二维平面上 \(n\) 个点 \((x_i, y_i)\)，你需要将它们连成一个凸多边形外挂一些点的形状，且多边形内部没有点。
若多边形的面积为 \(S\)，连接的线段总长为 \(P\)，则得分为 \(\frac SP\)。
求最大得分。\(n \le 300\)，\(|x_i|,|y_i| \le 10^6\)。