Difference between revisions of "2018 CCPC Jilin Onsite Contest"

From EOJ Wiki
Jump to navigation Jump to search
 
(11 intermediate revisions by 2 users not shown)
Line 20: Line 20:
  
 
Solved by Kilo_5723. 00:28:20 (+)
 
Solved by Kilo_5723. 00:28:20 (+)
 +
 +
题意:不停玩一个游戏,胜率为 $p\%$,可以抽奖,一开始抽中的概率是 $2%$,如果上一局游戏胜利可以抽一次奖,如果没有抽中获奖概率上升 $2%$,如果游戏失败则获奖概率上升 $1.5%$。求期望玩多少局游戏能抽中。
 +
 +
题解:概率 $dp$,以 $0.5%$ 为单位构造 $200$ 个当前抽奖概率对应的状态,求出每个状态的期望抽奖次数。
  
 
== Problem E ==
 
== Problem E ==
  
Upsolved by Kilo_5723. 02:13:13 (+)
+
Solved by Kilo_5723. 02:13:13 (+)
 +
 
 +
题意:给定平面一个圆锥体,给定一个匀速运动的点,求撞击时间。
 +
 
 +
题解:设 $f(t)$ 代表点运动 $t$ 时间后点的高度与圆锥体在点的 $xOy$ 坐标处高度之差。
 +
 
 +
有两种可能,如果 $f(+\infty)>0$,那么三分出 $f(x)$ 的最低点,再在 $0$ 和该点之间二分。
 +
 
 +
否则,直接在 $0$ 到 $+\infty$ 之间二分。
  
 
== Problem F ==
 
== Problem F ==
Line 32: Line 44:
  
 
Solved Kilo_5723. 04:50:07 (+1)
 
Solved Kilo_5723. 04:50:07 (+1)
 +
 +
题意:用 $10^4$ 个 $1 \;\Omega$ 的电阻通过串并联构造 $r \;\Omega$ 的电阻 $(0.1 \le r \le 0.9)$,要求误差在 $10^{-7}$ 以内。
 +
 +
题解:考虑将电阻分组,各组大小分别是 $2,4,8,16,\dots,1024,2048,4096$。每组之内并联,各组之间串联。这样,通过删除前六组中的一些组,我们可以获得一个由并联电阻串联得到 $r$ 的方案,误差在 $10^2$ 以内。
 +
 +
然后,我们考虑如何进行微调。对于剩下的所有组中,假设相邻两组的电阻数量分别是 $a,b$ $(2 \cdot a \approx b)$,如果将前一组的一个电阻分给后一组,总电阻会上升,反之则会降低,而变化的数值的数量级接近于 $a^{-2}$。从前往后这样调整,最终可以把精度误差调整到 $10^{-7}$ 以内。
  
 
== Problem H ==
 
== Problem H ==
Line 48: Line 66:
  
 
$xs_lx+xs_{l+1}x+\cdots xs_rx\\
 
$xs_lx+xs_{l+1}x+\cdots xs_rx\\
=$
+
=x(r-l+1)+10\cdot \sum_{i=l}^rs_i+x(\sum_{i=l}^r 10^{len_i+1})$
 +
 
 +
显然 $\sum_{i=l}^rs_i$ 和 $\sum_{i=l}^r 10^{len_i+1}$ 是可以通过线段树维护的。
  
 
用线段树维护这些操作,为了快速的 Pushdown ,需要下列信息:
 
用线段树维护这些操作,为了快速的 Pushdown ,需要下列信息:
  
* tagl 当前区间左边需要一起加上的数
+
* tagl 当前区间左边需要一起加上的数;
* tagr 当前区间右边需要一起加上的数
+
* tagr 当前区间右边需要一起加上的数;
* taglen 当前区间左/右边需要加上的数的长度
+
* taglen 当前区间左/右边需要加上的数的长度;
* sum 当前区间的和
+
* sum 当前区间的和;
* sumlen
+
* sumlen 表示区间的 $\sum_{i=l}^r 10^{len_i+1}$。
 +
 
 +
于是考虑 Pushdown 的时候,标记下传的具体计算即可。
 +
 
 +
写起来有一些些繁琐。
  
 
== Problem I ==
 
== Problem I ==
Line 68: Line 92:
 
== Problem K ==
 
== Problem K ==
  
Unsolved.
+
Upsolved by Weaver_zhu.
  
 
== Problem L ==
 
== Problem L ==
  
 
Unsolved.
 
Unsolved.

Latest revision as of 12:14, 6 November 2019

Problem A

Solved by Weaver_zhu. 00:07:11 (+)

Problem B

Solved by Xiejiadong. 00:45:37 (+2)

题意:要求在四个城市之间完成时区转换计算。

题解:注意 `12:00 AM` 表示的是凌晨一点就能做了。

if 有一个地方没写 else 于是 zbl 好久。

Problem C

Solved by Weaver_zhu. 00:43:55 (+)

Problem D

Solved by Kilo_5723. 00:28:20 (+)

题意:不停玩一个游戏,胜率为 $p\%$,可以抽奖,一开始抽中的概率是 $2%$,如果上一局游戏胜利可以抽一次奖,如果没有抽中获奖概率上升 $2%$,如果游戏失败则获奖概率上升 $1.5%$。求期望玩多少局游戏能抽中。

题解:概率 $dp$,以 $0.5%$ 为单位构造 $200$ 个当前抽奖概率对应的状态,求出每个状态的期望抽奖次数。

Problem E

Solved by Kilo_5723. 02:13:13 (+)

题意:给定平面一个圆锥体,给定一个匀速运动的点,求撞击时间。

题解:设 $f(t)$ 代表点运动 $t$ 时间后点的高度与圆锥体在点的 $xOy$ 坐标处高度之差。

有两种可能,如果 $f(+\infty)>0$,那么三分出 $f(x)$ 的最低点,再在 $0$ 和该点之间二分。

否则,直接在 $0$ 到 $+\infty$ 之间二分。

Problem F

Solved by Weaver_zhu. 01:04:38 (+)

Problem G

Solved Kilo_5723. 04:50:07 (+1)

题意:用 $10^4$ 个 $1 \;\Omega$ 的电阻通过串并联构造 $r \;\Omega$ 的电阻 $(0.1 \le r \le 0.9)$,要求误差在 $10^{-7}$ 以内。

题解:考虑将电阻分组,各组大小分别是 $2,4,8,16,\dots,1024,2048,4096$。每组之内并联,各组之间串联。这样,通过删除前六组中的一些组,我们可以获得一个由并联电阻串联得到 $r$ 的方案,误差在 $10^2$ 以内。

然后,我们考虑如何进行微调。对于剩下的所有组中,假设相邻两组的电阻数量分别是 $a,b$ $(2 \cdot a \approx b)$,如果将前一组的一个电阻分给后一组,总电阻会上升,反之则会降低,而变化的数值的数量级接近于 $a^{-2}$。从前往后这样调整,最终可以把精度误差调整到 $10^{-7}$ 以内。

Problem H

Upsolved by Xiejiadong. (-3)

题意:要求支持两个操作:

  • 对于区间 $[l,r]$ 所有的数 $s_i$ 变成 $xs_ix$ ;
  • 询问一个区间的和。

题解:

如果当前区间的答案是 $sum$ ,现在对区间整体进行操作 $1$ ,此时代价变成

$xs_lx+xs_{l+1}x+\cdots xs_rx\\ =x(r-l+1)+10\cdot \sum_{i=l}^rs_i+x(\sum_{i=l}^r 10^{len_i+1})$ 。

显然 $\sum_{i=l}^rs_i$ 和 $\sum_{i=l}^r 10^{len_i+1}$ 是可以通过线段树维护的。

用线段树维护这些操作,为了快速的 Pushdown ,需要下列信息:

  • tagl 当前区间左边需要一起加上的数;
  • tagr 当前区间右边需要一起加上的数;
  • taglen 当前区间左/右边需要加上的数的长度;
  • sum 当前区间的和;
  • sumlen 表示区间的 $\sum_{i=l}^r 10^{len_i+1}$。

于是考虑 Pushdown 的时候,标记下传的具体计算即可。

写起来有一些些繁琐。

Problem I

Solved by Weaver_zhu. 01:52:36 (+)

Problem J

Unsolved.

Problem K

Upsolved by Weaver_zhu.

Problem L

Unsolved.