2019 Multi-University,Nowcoder Day 10

Problem A

Upsolved by Kilo_5723. (-1)

赛后五分钟补题。

题意：给定 $n$ 张卡牌，每张卡片上的分值是 $x_i>0$，顺序随机，你要按顺序抽卡，使得你的卡片上的分值总和 $\in [b,a)$，求能成功的概率。

题解：令 $dp_{i,j}$ 代表取 $i$ 张卡牌分值和为 $j$ 的方案数。将所有卡片加进状态中时，我们考虑枚举每一张卡片作为最后一张卡片被抽取的情况。

对于 $dp_{i,j}$，显然将卡片加入状态的顺序对最终结果没有关系，也就是说，倒数第二个结果有 $n$ 种可能性，分别对应 $n$ 张卡牌作为最后一张卡牌被抽取的情况。我们发现，这种状态是可以从 $dp_{i,j}$ 倒推的，也就是说，令不取第 $k$ 张卡牌时，取 $i$ 张卡牌分值和为 $j$ 的方案书为 $cnt_{i,j}$，我们可以从 $dp_{i,j}$ 推出 $cnt_{i,j}$。

在确定抽取的最后一张卡片之后，答案就很好求了。我们要找的就是每一个 $j<b$ 且 $j+x_i<a$ 的状态，对每一个状态求出其发生的概率，最后全局求和就是答案。

Problem B

Solved by Xiejiadong. 00:22:29 (+1)

题意：给出一个斐波那契字符串，求某一位开始的十个字符分别是什么。

题解：只需要输出十个字符串，直接暴力。

考虑从最后往前做，需要判断来自前半段还是后半段，递归下去。

可以发现当 $n=60$ 的时候，长度就远大于题面了，所以超过 $60$ 的，一定属于前半段。

这样一直递归到初始条件输出即可。

Problem C

Unsolved.

Problem D

Solved by Weaver_zhu. 00:57:31 (+1)

增量法 CRT 模板题，需要高精度。

Problem E

Solved by Kilo_5723. 00:25:09 (+1)

题意：给定 $2^n \cdot 2^n$ 的方阵中 $n$ 个点，按 hilbert 曲线经过它们的顺序排列。

题解：分治。

对将每一个方阵分成四块，将点按块的编号先排序，对每一块内部的点进行一次坐标转换继续排序。

Problem F

Solved by Kilo_5723. 01:21:05 (+)

Problem G

Unsolved.

Problem H

Solved by Xiejiadong. 00:52:41 (+1)

题意：判断六元烷烃属于哪一种。

题解：大部分的直接通过度数判断即可，就是 $2$ 型和 $3$ 型的度数是完全同构的，拿度数 $3$ 的那个点，再做一次判断即可。

Problem I

Unsolved.

Problem J

Unsolved. (-11)