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

From EOJ Wiki
Jump to navigation Jump to search
Line 24: Line 24:
  
 
Solved by Xiejiadong. 01:49:18 (+)
 
Solved by Xiejiadong. 01:49:18 (+)
 +
 +
题意:每次添加一堆新的关系,求能选出多少四元组,使得两两都没有关系。
 +
 +
题解:每次合并的时候,考虑减少的四元组。
 +
 +
每次合并两个组,减少的关系一定包含了这两个组,于是就是在剩余的组中再选两个人。
 +
 +
于是我们维护四元组和二元组的数量,用并查集维护块大小就好了。
  
 
== Problem F ==
 
== Problem F ==

Revision as of 13:25, 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)

Problem I

Unsolved.

Problem J

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