2019 Multi-University,HDU Day 6

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Solved by Kilo_5723. 03:09:30 (+)

题意：有 $n$ 个工作，第 $i$ 个给甲做会花 $a_i$ 的时间，给乙做会花 $b_i$ 的时间。但是甲乙可以各做一部分工作，花费的时间为 $x\cdot a_i+y \cdot b_i(x+y=1)$。对每个 $i(1 \le i \le n)$，求出前 $i$ 个工作，两个人做完，花费时间最多的人需要花费至少多少时间。

题解：我们考虑 $n$ 个工作的情况：

如果工作全部分给甲，那么此时甲要花 $A=\sum_{i=1}^n a_i$ 的时间，乙要花费 $0$ 的时间，记为 $(A,0)$。

而接下来甲要把工作分给乙，那么甲肯定会分 $\frac{a_i}{b_i}$ 最大的工作，设这个工作为 $p$。如果这个工作全部分给乙，此时的情况是 $(A-a_p,b_p)$。而这之间的所有情况，都分布在 $(A,0)$ 和 $(A-a_p,b_p)$ 的连线上。

再接下来，甲肯定会分 $\frac{a_i}{b_i}$ 第二大的工作，然后是第三大，直到最后情况会变成 $(0,B)$。

自此，我们得到了一系列点，我们要求的就是这些点形成折线段和直线 $x=y$ 的交点，我们只要二分找到直线 $x=y$ 上下的两个点求交点就可以了。

现在考虑怎么维护的问题。我们发现，去掉一个工作 $a_i,b_i$ 之后，其对应的线段右方的点会全部平移 $(-a_i,0)$，而上方的点会全部平移 $(0,-b_i)$。我们要求解，仍是二分找到直线 $x=y$ 上下的两个点，再求交点。

因此，我们需要先对工作按斜率排序，并记录每个工作排序后的位置，用线段树来维护 $n+1$ 个点。其中线段树需要支持的操作有区间加一个向量，以及线段树上二分查找直线 $x=y$ 上下的两个点。

Problem E

Solved by Xiejiadong. 04:42:02 (+2)

题意：在二维平面内框一个矩阵，使得框内权值和最大。

题解：离散以后，枚举行的上下边界，然后把列的元素都压在一起，问题就变成了求连续子序列的最大和。

考虑用线段树维护前缀和，每次都是在某个位置加入一个点和他的权值，相当于后缀区间的修改，维护区间最大最小值。

每次 Pushup 的时候，顺便维护连续子序列的最大和，如果两个端点分属于两个子树，用右子树的最大值减最小值更新答案，如果属于同一个子树，直接通过孩子节点的连续子序列最大和更新即可。

Problem F

Solved by Weaver_zhu. 04:01:16 (+2)

Problem G

Unsolved.

Problem H

Solved by Weaver_zhu. 00:28:26 (+)

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Unsolved. (-3)

Problem L

Solved by Xiejiadong && Kilo_5723. 00:14:59 (+)

题意：两个人轮流取小根堆的叶子，两个人都希望自己获得的价值最大，求两个人获得的价值。

题解：显然两个人的策略就是取当前剩下的里面叶子中最大的。

又显然，当前堆中的最大元素一定是叶子，所以排序以后，两个人依次从大到小取就好了。