2019 Multi-University,Nowcoder Day 9

From EOJ Wiki
Jump to: navigation, search

Problem A

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

斐波那契数列的周期大概是 $O(MOD)$ 的,然后把模数拆开来 CRT 就好了

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)

题意:给出一个序列 $\{a_i\}$ 和 $b$,求 $\sum_{\{r_i\}\;{\rm is \; a \; permutation \; of}\;\{a_i\}}b^{t(\{r_i\})}\;{\rm mod}\;10^9+7$,其中 $t(\{r_i\})$ 代表 $r_i$ 中的逆序对。

题解:猜。

令 $f(n)=\sum_{i=0}^{n-1} b^i$,则答案为 $\frac{f(n)}{\prod_{x\;{\rm exists \; in}\;\{a_i\}}\;f(cnt(x))}$,其中 $cnt(x)$ 代表 $x$ 在 $a$ 中出现的次数。

Problem D

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

题意:给出 $\{a_i\}$,求出 $\{a_i\}$ 的一个子集,其元素之和为 $s$。

题解:折半查找。

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

Upsolved by Weaver_zhu.

题意:求 $\sum\limits_{k=1}^{n}(km)\&m$

题解:按位做,得 $ans=\sum\limits_{i=1}^{64}\sum\limits_{k=1}^{n} \frac{km}{2^i} 2^i - \frac{km}{2^{i+1}} 2^{i+1}$

Problem J

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

题意:在 $x=i$ 的位置有一条 $l_i \le y \le r_i$ 的线段,现在要找一条水平的对称轴,擦去一些长度的线段使得每一条线段都对这条对称轴对称,求擦去线段长度的最小值。

题解:令 $f(k)$ 代表取对称轴为 $y=k$ 时擦去线段长度的最小值。我们发现,对第 $i$ 条线段,其对 $f(k)$ 的贡献是一个连续的分段函数,且每一段都是一次函数。对函数的分段点的斜率变化值求和再求前缀和就能得到 $f(x)$,对每一段取全局最大值就是最大保留长度。