Difference between revisions of "2018 Multi-University, Nowcoder Day 5"

From EOJ Wiki
Jump to navigation Jump to search
 
(3 intermediate revisions by the same user not shown)
Line 28: Line 28:
  
 
== Problem C ==
 
== Problem C ==
 +
 +
题意:给定一张 n 个点 m 条边的无向图,对于每个边集的子集 S,假设这个子集作为边的话,这张图的连通块个数为 k[S],求 $\sum_S k[S]^{k[S]-1}$。
 +
 +
题解:
 +
 +
虽然出题人的本意是要把 $x^{x-1}$ 看做 $x$ 个点的有根树个数,但是姑且不考虑这个,而是求出满足对于所以 $x$, $k(S)=x$ 的 $S$ 的个数。
 +
 +
$g(S)=2^{e(S)}$,其中 $e(S)$ 表示顶点集 $S$ 的导出子图中边的条数。
 +
 +
先求出 $f(S) = \sum_{T\subseteq S} g(S)$,用高维前缀和或者 FWT 都可以。定义乘法为子集卷积,$f^n(S)$ 的含义是 $S$ 导出子图的边集中至少有 $n$ 个联通块的方案数。
 +
 +
设 $h(n)=f^n(U)$,$h'(n)$ 为恰好 $n$ 个联通块的方案数。那么 $h'(x)=h(x)-\sum_{i>x} h'(i) S(i,x)$,其中 $S$ 是第二类斯特灵数。
 +
 +
实现过程中由于要子集卷积,所以还要按二进制中 1 的个数分离,计算 $h(n)$ 时还需要一次容斥。
 +
 +
zerol:出题人卡常卡得太狠了。(标程 3555ms,时限给 4s ????)
  
 
== Problem D ==
 
== Problem D ==

Latest revision as of 09:36, 4 September 2018

Problem A

Solved by ultmaster. 00:25 (+)

题意:要求删掉 $k$ 门课程的成绩使得加权平均分最大。

题解:二分答案,移项后判断式子是否大于 0 即可。

Problem B

Upsolved by ultmaster.

题意:$n$ 是好数,当存在 $x \in [n^2+1,n^2+2n]$ 满足 $x | n^4$。求比输入大的最小的好数。

题解:$n^4 = (n^2-x)(n^2+y)$ 展开得到 $(y-x)n^2 = xy$。由于 $y \le 2n$,$y-x$ 只能是 1 或 2 或 3。下面分别讨论。

$y-x=1$ 时,方程无解。(没有严格证明过)

$y-x=2$ 时,$2n^2 = x(x+2)$,即 $(x+1)^2-2n^2=1$。解该佩尔方程得到 $n$ 的递推式是 $a_n = 6 a_{n-1} - a_{n-2}$。

$y-x=3$ 时,$(2x+3)^2 - 12n^2 = 9$。得到 $n$ 的递推式是 $a_n = 14 a_{n-1} - a_{n-2}$。

暴力算一算就好了。

佩尔方程小课堂:佩尔方程千万不要去推(虽然推起来很有趣,但结果不一定好看,会是两个式子)。记住佩尔方程结果的形式通常是 $a_n = k a_{n-1} - a_{n-2}$($a_{n-2}$ 前的系数通常是 $-1$)。暴力 / 凑出两个基础解之后加上一个 0,容易解出 $k$ 并验证。一般的话还可以找规律得到,但本题由于是两个序列并在一起,规律并不容易发现。

特别鸣谢:本题题解和佩尔方程小课堂由 oxx 友情提供。

Problem C

题意:给定一张 n 个点 m 条边的无向图,对于每个边集的子集 S,假设这个子集作为边的话,这张图的连通块个数为 k[S],求 $\sum_S k[S]^{k[S]-1}$。

题解:

虽然出题人的本意是要把 $x^{x-1}$ 看做 $x$ 个点的有根树个数,但是姑且不考虑这个,而是求出满足对于所以 $x$, $k(S)=x$ 的 $S$ 的个数。

$g(S)=2^{e(S)}$,其中 $e(S)$ 表示顶点集 $S$ 的导出子图中边的条数。

先求出 $f(S) = \sum_{T\subseteq S} g(S)$,用高维前缀和或者 FWT 都可以。定义乘法为子集卷积,$f^n(S)$ 的含义是 $S$ 导出子图的边集中至少有 $n$ 个联通块的方案数。

设 $h(n)=f^n(U)$,$h'(n)$ 为恰好 $n$ 个联通块的方案数。那么 $h'(x)=h(x)-\sum_{i>x} h'(i) S(i,x)$,其中 $S$ 是第二类斯特灵数。

实现过程中由于要子集卷积,所以还要按二进制中 1 的个数分离,计算 $h(n)$ 时还需要一次容斥。

zerol:出题人卡常卡得太狠了。(标程 3555ms,时限给 4s ????)

Problem D

Upsolved by kblack. (-1)

题意:往一个指定偶数排列里面插入保持顺序的奇数,求产生的最少逆序对数。

题解:往哪里插入可以随便维护,题解说最优插入位置一定递增,证不来,我们就假装的确是这样吧 QAQ。

Problem E

Solved by zerol. 00:49 (+)

题意:给一些无序的无序四元组,要求变成目标,求最少的需要改变位置的元素。

题解:KM。定义两个之间的匹配值是四元组的交的个数,然后跑二分图最大匹配。

Problem F

Solved by ultmaster. 02:14 (+)

题意:每一个数 $d_i$ 有 $p_i$ 的概率出现,求贪心的上升序列的长度的期望。

题解:从 $1$ 到 $n$ 用 $p$ 和 $d$ 反复更新两个数组。$a_k$ 表示序列以 $k$ 结尾的概率;$b_k$ 表示序列以 $k$ 结尾的情形下答案的期望(不是条件期望,就是直接贡献答案的)。

FOR (j, 0, d) {
    b[d] += (b[j] + a[j]) * p;
    b[j] = b[j] * prev;
}
FOR (j, 0, d) {
    a[d] += a[j] * p;
    a[j] = a[j] * prev;
}

答案是 $b$ 数组的和。

下面优化这个过程:发现大概涉及到下面的操作:区间乘,单点加,区间查询。用线段树就可以。单点加的时候直接暴力 pushdown 下去。没有优化,卡着时限过了。

ultmaster: 绝对是做烦了,因为题解只要一个树状数组就好了。

Problem G

Solved by kblack. 00:14 (+1)

温暖的签到。

Problem H

Solved by zerol. 02:52 (+1)

题意:求一个数列的下标字典序第 k 小的上升子序列。

题解:预处理出每个下标开始的上升子序列个数,然后一位一位确定即可。

Problem I

Solved by kblack. 01:17 (+1)

题意:求一个点集有多少非空子集 $S$ 使得 $S$ 的每个子集都能被一个长条 $\{(x,y)|x \geq a, l \leq y \leq r\}$ 切出来。

题解:3 个点必须是 < 形状,所有大于 3 个点都布星。一个点直接算,其他情况枚举第二个点,搞个树状数组维护一下就好了。

Problem J

Solved by kblack. 00:08 (+)

温暖的签到。