Difference between revisions of "2018 CCPC Jilin Onsite Contest"
Line 28: | Line 28: | ||
Solved by Kilo_5723. 02:13:13 (+) | Solved by Kilo_5723. 02:13:13 (+) | ||
+ | |||
+ | 题意:给定平面一个圆锥体,给定一个匀速运动的点,求撞击时间。 | ||
+ | |||
+ | 题解:设 $f(t)$ 代表点运动 $t$ 时间后点的高度与圆锥体在点的 $xOy$ 坐标处高度之差。 | ||
+ | |||
+ | 有两种可能,如果 $f(+\inf)>0$,那么三分出 $f(x)$ 的最低点,再在 $0$ 和该点之间二分。 | ||
+ | |||
+ | 否则,直接在 $0$ 到 $+\inf$ 之间二分。 | ||
== Problem F == | == Problem F == |
Revision as of 06:54, 5 October 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(+\inf)>0$,那么三分出 $f(x)$ 的最低点,再在 $0$ 和该点之间二分。
否则,直接在 $0$ 到 $+\inf$ 之间二分。
Problem F
Solved by Weaver_zhu. 01:04:38 (+)
Problem G
Solved Kilo_5723. 04:50:07 (+1)
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.