Hdu暑期多校训练10

来自PC Wiki
跳到导航 跳到搜索

Records

[Contest]

Solutions

A

B

C

D

E

按$$x$$排序,考虑枚举A集合中最大的$$x$$,那么$$x$$比他大的必须扔进B集合

$$x$$比当前小的里面找$$y$$和它最接近的,set维护

F

G

H

排序,a>=b时关键字就是各自的实际价值,a<b时关键字是两者平均值(a+b)/2

然后贪心的取,当取值落在a<b的中间时,两种决策:

①不选这个a,选择后面最大的可取的硬币

②选这对a,b,扔掉前面(已选)最小的可扔的硬币

I

每次暴力dfs

J

K

考虑分治求这个东西

每次找出当前区间最大点,将当前区间分成两半

考虑较小的那一半的每个点作为端点,然后另一个端点在较大的那一半里

满足条件的端点一定是个连续区间,预处理可行范围计数即可

复杂度$$O(n \log n)$$