Difference between revisions of "2019 Multi-University,Nowcoder Day 7"

From EOJ Wiki
Jump to navigation Jump to search
Line 39: Line 39:
 
题意:每次将 $[l_i,r_i]$ 里的 $r_i-l_i+1$ 个数加入数列,求数列的中位数。
 
题意:每次将 $[l_i,r_i]$ 里的 $r_i-l_i+1$ 个数加入数列,求数列的中位数。
  
题解:离散化线段树,区间加,求第 $k$ 大的值。
+
题解:离散化线段树,需要支持区间加,求第 $k$ 大的值。
  
 
== Problem F ==
 
== Problem F ==

Revision as of 12:19, 8 August 2019

Problem A

Solved by Xiejiadong. 00:32:38 (+)

题意:将字符串尽可能少的断开,使得断开的每部分都是其循环串种字典序最小的。

题解:考虑最多的断开情况,一定是 $1111\; 0111\; 0011\; 0001\; 0000$ 如此的。

也就是断开的一定是 $\sqrt{n}$ 级别的。

于是考虑贪心的做,从后往前枚举断点,用最小表示法判断合法性即可。

Problem B

Solved by 柴俊,丁大公,陈咸平等. 01:09:39 (+)

《高等数学(上册)》 P149 5.4.6 有理函数的积分:

……,由代数学可知,$Q(x)$ 在实数范围内总可以分解为一些因式(一次二项式或有虚根的二次三项式)的乘积,……

Problem C

Solved by Xiejiadong. 03:49:18 (+5)

题意:有 $n$ 种树,每种树砍掉一棵都需要 $p_i$ ,每种树有 $c_i$ 棵,现在要求高度最高的树数量超过一半,求最小的看法代价。

题解:把高度相同的树都放在一起。枚举当前最高的树是高度是多少,高度比当前高的肯定全部砍掉。高度比当前低的选择中选择代价最小的来砍掉就好了。

题目中 $c_i$ 和 $p_i$ 看反了,还过样例了。自闭了两个小时。

Problem D

Solved by Weaver_zhu. 00:03:13 (+)

Problem E

Solved by Kilo_5723. 04:48:49 (+)

题意:每次将 $[l_i,r_i]$ 里的 $r_i-l_i+1$ 个数加入数列,求数列的中位数。

题解:离散化线段树,需要支持区间加,求第 $k$ 大的值。

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Unsolved. (-4)

Problem I

Solved by Kilo_5723. 03:13:21 (+)

Problem J

Solved by Xiejiadong. 00:06:51 (+)

温暖的签到。

Problem K

Unsolved.