2019 Multi-University,Nowcoder Day 9

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)$，对每一段取全局最大值就是最大保留长度。