2018 CCPC Jilin Onsite Contest

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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