2019 Multi-University,HDU Day 10

From EOJ Wiki
Revision as of 00:43, 12 September 2019 by Kilo (talk | contribs) (→‎Problem C)
Jump to navigation Jump to search

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.