2019 Multi-University,HDU Day 10

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Solved by Kilo_5723. 00:43:29 (+2)

题意：有 $n$ 个礼物，每个礼物有 $P_i$ 的概率让女友开心，要选出一些礼物，最大化让女友开心恰好一次的概率，求这个概率。

题解：大力猜结论：

对 $P_i$ 排序，从大往小取，直到取了一个礼物之后女友恰好开心一次的概率下降为止，输出上一步的答案。

Problem D

Unsolved.

Problem E

Solved by Xiejiadong. 01:34:34 (+1)

题意：每个人有两个属性 $a_i$ 和 $b_i$ ，将人分类，使得 $|max{a_i}-max{b_i}|$ 最小。

题解：对 $a_i$ 排序，枚举每一个 $a_i$ 作为 $a$ 属性上限的时候的情况，显然比当前 $a_i$ 大的一定是 $b$ ，然后可以选择在比他小的或者相等（不能是自己）中挑一个和 $a_i$ 最接近的且能称为最大值的。

直接拿 set 、 map 玩一下就好了。

lower_bound 写炸了，白给了一发。

Problem F

Unsolved.

Problem G

Unsolved. (-10)

Problem H

Solved by Xiejiadong. 03:59:44 (+4)

题意：每一组两个硬币，分别价值 $a_i$ 、 $b_i$ ，每一组有三个选择：取 $a_i$ ，取 $a_i$ 和 $b_i$ ，不取，求恰好取 $k$ 个硬币的时候的最大价值。

题解：分两类贪心：

• $a\ge b$ ，肯定先取 $a$ 再取 $b$ ，直接贪心；

• $a < b$ ，有一个显然的结论是，只有当奇数的时候才会出现一个 $a$ 的情况，其余的一定是一组一起出现。而出现一个 $a$ 的情况，一定是最大的几组和一个剩下的中的 $a$ 或者最大的几组中去掉一个最小的 $b$ ，两种情况取 max 。

这样，可以很容易的分别得到两种情况下，取任意个硬币的时候的最大价值。

考虑合并，相当于是一个 max-和 的卷积，不大能搞。

但是发现对于 $a<b$ 的情况具有决策单调性，于是就可以 $O(nlogn)$ 得解了。

Problem I

Solved by Kilo_5723. 00:26:16 (+)

Problem J

Unsolved.

Problem K

Unsolved.