Difference between revisions of "2019 Multi-University,HDU Day 6"

From EOJ Wiki
Jump to navigation Jump to search
Line 59: Line 59:
 
题解:显然两个人的策略就是取当前剩下的里面叶子中最大的。
 
题解:显然两个人的策略就是取当前剩下的里面叶子中最大的。
  
又显然,当前堆中的最大元素一定是叶子,所以排序以后,两个人一次从大到小取就好了。
+
又显然,当前堆中的最大元素一定是叶子,所以排序以后,两个人依次从大到小取就好了。

Revision as of 13:37, 7 August 2019

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

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

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 (+)

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

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

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