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

From EOJ Wiki
Jump to navigation Jump to search
Line 44: Line 44:
  
 
Solved by Xiejiadong && Kilo_5723. 01:09:19 (+1)
 
Solved by Xiejiadong && Kilo_5723. 01:09:19 (+1)
 +
 +
题意:每次询问一个区间能组成的周长最长的三角形周长。
 +
 +
题解:如果我们确定了一个区间里的某一条边为最长边,那么显然组成的三角形的另两条边一定是长度比它小但是最接近的两条边。
 +
 +
也就是说,组成三角形的三条边一定是区间里长度排序以后连续的三条边。
 +
 +
考虑无法组成三角形的情况,一定存在 $a>b+c$ ,也就是说,如果不成立的话,长度可以至少减少一半,于是就可以直接暴力了。
 +
 +
不断的询问最大的长度,次大的长度,直到询问到三角形或者无解。
 +
 +
区间 $k$ 大值,用主席树维护就好了。
  
 
== Problem L ==
 
== Problem L ==
  
 
Solved by Kilo_5723 && Xiejiadong. 03:06:54 (+)
 
Solved by Kilo_5723 && Xiejiadong. 03:06:54 (+)

Revision as of 13:39, 24 July 2019

Problem A

Unsolved.

Problem B

Upsolved by Kilo_5723 && Weaver_zhu. (-1)

没写完。赛后 2min 补题。

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Solved by Weaver_zhu && Kilo_5723. 01:40:33 (+)

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Solved by Xiejiadong. 03:50:48 (+1)

Problem J

Solved by Kilo_5723. 00:22:49 (+1)

Problem K

Solved by Xiejiadong && Kilo_5723. 01:09:19 (+1)

题意:每次询问一个区间能组成的周长最长的三角形周长。

题解:如果我们确定了一个区间里的某一条边为最长边,那么显然组成的三角形的另两条边一定是长度比它小但是最接近的两条边。

也就是说,组成三角形的三条边一定是区间里长度排序以后连续的三条边。

考虑无法组成三角形的情况,一定存在 $a>b+c$ ,也就是说,如果不成立的话,长度可以至少减少一半,于是就可以直接暴力了。

不断的询问最大的长度,次大的长度,直到询问到三角形或者无解。

区间 $k$ 大值,用主席树维护就好了。

Problem L

Solved by Kilo_5723 && Xiejiadong. 03:06:54 (+)