2018 CCPC Jilin Onsite Contest

From EOJ Wiki
Revision as of 06:51, 5 October 2019 by Kilo (talk | contribs) (→‎Problem D)
Jump to navigation Jump to search
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 (+)

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.