M_sea

Codeforces Global Round 2 题解
orz GM Itst比赛地址Ilya and a Colorful Walk显然最优解要么是从 $1$ 走到某个...
扫描右侧二维码阅读全文
01
2019/06

Codeforces Global Round 2 题解

orz GM Itst

比赛地址

Ilya and a Colorful Walk

显然最优解要么是从 $1$ 走到某个地方,要么是从 $n$ 走到某个地方。

直接 $O(n)$ 扫一遍即可。

代码

Alyona and a Narrow Fridge

枚举答案 $x$ ,然后判断。

判断的话,把前 $x$ 个瓶子按高度从大到小排序,然后每两个分成一组,再判断是否超出限制即可。

代码

Ramesses and Corner Inversion

挖掘这个操作的性质。可以发现操作前后,每行、每列的异或和是不变的。

那么直接两个矩阵的行列异或和是否全部相等即可。

代码

Frets On Fire

为了方便,设 $len=r-l+1$ 。

首先可以发现,询问 $[l,r]$ 和询问 $[1,len]$ 是等价的。

可以发现要求的东西其实是 $[s_i+1,s_i+len]$ 的并的大小。

把 $s$ 排序、去重,那么问题就变成了求 $\displaystyle\sum_{i=1}^{n-1}\min\left\{s_{i+1}-s_i,len\right\}$ 。

那么差分后排序,每次二分出最大的 $<len$ 的数即可得出答案。

代码

Pavel and Triangles

把 $2$ 的幂填入三角形不等式中只会有一种形式:$2^i+2^j<2^j$ 。也就是说每个三角形需要两根相同的木棍。

设 $cnt$ 表示可以凑出多少对长度相同的木棍。

从大到小考虑所有木棍,每次把 $cnt$ 加上 $\left\lfloor\frac{a_i}{2}\right\rfloor$ ,然后如果还有剩余的木棍就找一对来和它组成一个三角形。

最后 $cnt$ 可能还有值,把这 $cnt$ 对换算成 $\left\lfloor\frac{2cnt}{3}\right\rfloor$ 个三角形,再加上之前组的三角形即可。

代码

Niyaz and Small Degrees

E 和 F 的难度差了 $1000$ 海星...

为了方便,设 $deg[i]$ 表示 $i$ 的度数,现在的度数限制是 $d$ 。

先考虑一个暴力做法。设 $f[i][0/1]$ 表示以 $i$ 为根的子树全部满足条件,$i$ 到父亲的边不断/断的答案。

考虑怎么转移。如果不考虑度数限制的话显然有 $\displaystyle f[u][0]=f[u][1]=\sum\min\left\{f[v][1]+w,f[v][0]\right\}$ 。

考虑加上度数限制。先考虑 $f[u][0]$ 的转移。

显然至少要断掉 $\max\{deg[u]-d,0\}$ 条边,也就是至少要从 $\max\{deg[u]-d,0\}$ 个 $f[v][1]+w$ 转移。

假设已经有 $cnt$ 个儿子满足 $f[v][1]+w\leq f[v][0]$ ,那么我们要强制 $\max\{deg[u]-d-cnt,0\}$ 个选 $f[v][0]$ 的儿子选 $f[v][1]+w$ 。

那么我们把所有的满足 $f[v][0]<f[v][1]+w$ 的儿子的 $f[v][1]+w-f[v][0]$ 值丢到一个堆里,把前 $\max\{deg[u]-d-cnt,0\}$ 大的值的和加上 $\displaystyle \sum\min\left\{f[v][1]+w,f[v][0]\right\}$ 转移给 $f[u][0]$ 即可。

可能写的比较意会,不懂的可以在评论区问我

$f[u][1]$ 的转移类似,因为多断了一条到父亲的边,所以只要取前 $\max\{deg[u]-d-cnt-1,0\}$ 大即可。

这样子似乎是 $O(n^2\log n)$ 的,考虑怎么优化。

首先可以发现,对于一个点 $u$ ,如果有 $deg[u]\leq d$ ,那么就不需要考虑这个点了。

那么每次度数 $\leq d$ 的点删去,度数 $>d$ 的点跑一遍 $\mathrm{dp}$ 。

但是这样子每次还是要遍历儿子,复杂度不对。解决方法是删掉点 $u$ 时遍历所有出边 $(u,v,w)$ ,把 $w$ 加到 $v$ 的堆里去。

另外还有一些细节,详见代码

Get Ready for the Battle

神仙构造题...

首先答案有一个显然的下界 $\displaystyle\left\lfloor\frac{\sum_{i=1}^mhp_i}{n}\right\rfloor$ 。考虑怎么达到这个下界。

可以发现,如果要打出这个下界,那么每一次都必须打出恰好 $n$ 伤害(最后一次除外)。

那么考虑依次将每个敌人打成刚好 $0$ 滴血。设 $sum$ 为 $hp$ 的前缀和,那么可以发现,第 $i$ 个敌人时在若干轮后的血量为 $sum_i\mod n$ 。

也就是说,需要存在一个士兵的前缀,满足这个前缀的攻击力为 $sum_i\mod n$ 。这样子就可以用这个前缀去把敌人打成 $0$ ,然后用后面的士兵打后面的人。

那么可以这么构造:设 $a_i=sum_i\mod n$ ( $a_0=0,a_m=m$ ),然后将 $a$ 排序,则 $ans_i=a_i-a_{i-1}$ 。

输出方案就比较简单了,直接模拟即可。

代码

Triple

不会做,以后再来补(欢迎催更)

最后修改:2019 年 06 月 02 日 04 : 17 PM

发表评论