[Blog] [Docs] [Code] [Slides] [About]

Kick Start 2020 Round D

2020-07-15 20:12 CST

2020-07-15 20:32 CST

久违的KickStart总结,这次想到了最后一题怎么做,拿到了42nd(开心)。

然而周日的比赛周三才写wrap up的懒肥宅是屑。

前情回顾:

A - Record Breaker

超级水题。开个变量存前面元素的最大值即可,丢人的WA了一发。

代码:/code/ks2020d-a/

B - Alien Piano

动态规划,用$dp[pos][cur]$表示当前位置选择$cur$时最少违反了规则多少次。

$$dp[pos][cur] = \min\left(dp[pos - 1][lst] + break(cur, lst)? \right)$$

代码:/code/ks2020d-b/

C - Beauty of Tree

树上的概率论求期望。求出每个点被A选中的概率和被B选中的概率,则这个点的期望值是$p_A + p_B - p_A p_B$,所有点的期望求和即为答案。

看树的规模很大所以用了倍增来加速找父节点,但是听说只要普通的DFS就可以了。

代码:/code/ks2020d-c/

D - Locked Doors

比较复杂的题目。一个展览馆有$n$间展厅,两两之间有一个上了锁的门,开门的难度各不相同。一个人参观展览馆一定会挑两边难度更低的门先开,要求在线查询从$S$开始参观的第$K$个展厅的编号。

我的做法是从位置$S$开始开门,那么开了$K$扇门之后左边开了多少门肯定是可以计算的。如果左边多开了一扇门,那么这扇门的难度肯定比右边没开的那扇大,所以开了多少扇门是可以二分求得得。

  • 二分查找开了$K-2$扇门时左手边开了多少扇,然后左右两边的下一扇门取难度更小的那个即为答案;
  • 展览馆两端的门的难度,即$d[0]$和$d[n]$都是正无穷,处理起来代码简单;
  • 每次二分查找时,需要找左边$m$扇门的最大难度,转化为常见的RMQ问题用线段树解决。

一开始做的时候查了$K-1$扇门,把自己搞晕了WA了两发。

代码:/code/ks2020d-d/

<EOF>

Loading Comments By Disqus