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

From EOJ Wiki
Jump to navigation Jump to search
Line 44: Line 44:
  
 
Upsolved by Xiejiadong. (-11)
 
Upsolved by Xiejiadong. (-11)
 +
 +
题意:每次询问一个区间,要求每次在某一个高度砍平,使得砍掉的总长度一样,求 $x$ 刀砍在哪里。
 +
 +
题解:用主席树维护每一个高度的有多少,并且每次维护后缀高度的总长度。
 +
 +
考虑二分答案的话,如果当前砍的高度为 $mid$ ,那么一定是高度大于 $mid$ 的全部砍到 $mid$ ,用总和减一下就能判断了。
 +
 +
似乎这样就能过了。
 +
 +
但其实可以在主席树上二分,去掉一个 log 。
  
 
== Problem I ==
 
== Problem I ==

Revision as of 13:28, 15 August 2019

Problem A

Solved by Weaver_zhu. 04:10:16 (+)

Problem B

Solved by Xiejiadong. 00:47:16 (+)

题意:给出 $a+b\;mod\; p$ 和 $ab\;mod\; p$ 的结果,求 $a$ 和 $b$ 。

题解:可以从 $(a-b)^2=(a+b)^2-4ab$ 得到 $(a-b)^2$ ,利用二次剩余求得 $a-b$ ,再和差得到 $a$ 、 $b$ 。

F0RE1GNERS 的二次剩余板子需要特判 $b=0$ 的情况,会死循环。

Problem C

Solved by Kilo_5723. 04:46:30 (+1)

Problem D

Solved by Kilo_5723. 00:52:54 (+)

Problem E

Solved by Xiejiadong. 01:49:18 (+)

题意:每次添加一堆新的关系,求能选出多少四元组,使得两两都没有关系。

题解:每次合并的时候,考虑减少的四元组。

每次合并两个组,减少的关系一定包含了这两个组,于是就是在剩余的组中再选两个人。

于是我们维护四元组和二元组的数量,用并查集维护块大小就好了。

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Upsolved by Xiejiadong. (-11)

题意:每次询问一个区间,要求每次在某一个高度砍平,使得砍掉的总长度一样,求 $x$ 刀砍在哪里。

题解:用主席树维护每一个高度的有多少,并且每次维护后缀高度的总长度。

考虑二分答案的话,如果当前砍的高度为 $mid$ ,那么一定是高度大于 $mid$ 的全部砍到 $mid$ ,用总和减一下就能判断了。

似乎这样就能过了。

但其实可以在主席树上二分,去掉一个 log 。

Problem I

Unsolved.

Problem J

Solved by Kilo_5723. 01:24:15 (+3)