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

From EOJ Wiki
Jump to navigation Jump to search
 
(7 intermediate revisions by 3 users not shown)
Line 2: Line 2:
  
 
Upsolved by Kilo_5723. (-1)
 
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 ==
 
== Problem B ==
Line 24: Line 34:
  
 
Solved by Weaver_zhu. 00:57:31 (+1)
 
Solved by Weaver_zhu. 00:57:31 (+1)
 +
 +
增量法 CRT 模板题,需要高精度。
  
 
== Problem E ==
 
== Problem E ==
  
 
Solved by Kilo_5723. 00:25:09 (+1)
 
Solved by Kilo_5723. 00:25:09 (+1)
 +
 +
题意:给定 $2^n \cdot 2^n$ 的方阵中 $m$ 个点,按 hilbert 曲线经过它们的顺序排列。
 +
 +
题解:分治。
 +
 +
对将每一个方阵分成四块,将点按块的编号先排序,对每一块内部的点进行一次坐标转换继续排序。
  
 
== Problem F ==
 
== Problem F ==
  
 
Solved by Kilo_5723. 01:21:05 (+)
 
Solved by Kilo_5723. 01:21:05 (+)
 +
 +
题意:给出平面上 $n$ 个气球,给定一个值 $r$,你可以选择 $p,q$,扎破直线 $x=p-r,p,p+r$ 和 $y=q-r,q,q+r$ 上的所有气球,求最多能扎破气球的数量。
 +
 +
题解:虽然是三行三列,但本质上情况和一行一列是相同的。在一行一列的问题中,令 $sumx(p)$ 代表 $x=p$ 上的气球数量,$sumy(q)$ 代表 $y=q$ 上的气球数量,$cnt(p,q)$ 代表 $(p,q)$ 上的气球数量,我们要找的是 $sumx(p)+sumy(q)-cnt(p,q)$ 的最大值,则对每一个 $p$,维护 $sumy(q)-cnt(p,q)$ 的值,再从中取出最大值。
 +
 +
将情况推广到三列,我们发现求得答案的方式没有变化,只是 $sumx(p)$ 代表 $x=p-r,p,p+r$ 三条直线上的气球数量,$sumy(q)$ 代表 $y=q-r,q,q+r$ 三条直线上的气球数量,而 $cnt(p,q)$ 代表 $(p-r,q-r),(p-r,q),(p-r,q+r),(p,q-r),(p,q),(p,q+r),(p+r,q-r),(p+r,q),(p+r,q+r)$ 九个点上的气球数量。
  
 
== Problem G ==
 
== Problem G ==
Line 40: Line 64:
  
 
Solved by Xiejiadong. 00:52:41 (+1)
 
Solved by Xiejiadong. 00:52:41 (+1)
 +
 +
题意:判断六元烷烃属于哪一种。
 +
 +
题解:大部分的直接通过度数判断即可,就是 $2$ 型和 $3$ 型的度数是完全同构的,拿度数 $3$ 的那个点,再做一次判断即可。
  
 
== Problem I ==
 
== Problem I ==

Latest revision as of 08:24, 9 September 2019

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$ 的方阵中 $m$ 个点,按 hilbert 曲线经过它们的顺序排列。

题解:分治。

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

Problem F

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

题意:给出平面上 $n$ 个气球,给定一个值 $r$,你可以选择 $p,q$,扎破直线 $x=p-r,p,p+r$ 和 $y=q-r,q,q+r$ 上的所有气球,求最多能扎破气球的数量。

题解:虽然是三行三列,但本质上情况和一行一列是相同的。在一行一列的问题中,令 $sumx(p)$ 代表 $x=p$ 上的气球数量,$sumy(q)$ 代表 $y=q$ 上的气球数量,$cnt(p,q)$ 代表 $(p,q)$ 上的气球数量,我们要找的是 $sumx(p)+sumy(q)-cnt(p,q)$ 的最大值,则对每一个 $p$,维护 $sumy(q)-cnt(p,q)$ 的值,再从中取出最大值。

将情况推广到三列,我们发现求得答案的方式没有变化,只是 $sumx(p)$ 代表 $x=p-r,p,p+r$ 三条直线上的气球数量,$sumy(q)$ 代表 $y=q-r,q,q+r$ 三条直线上的气球数量,而 $cnt(p,q)$ 代表 $(p-r,q-r),(p-r,q),(p-r,q+r),(p,q-r),(p,q),(p,q+r),(p+r,q-r),(p+r,q),(p+r,q+r)$ 九个点上的气球数量。

Problem G

Unsolved.

Problem H

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

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

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

Problem I

Unsolved.

Problem J

Unsolved. (-11)