竞赛讨论区 > 【题解】牛客小白月赛29
头像
scimoon
编辑于 2020-11-15 18:04
+ 关注

【题解】牛客小白月赛29

A.进攻

对战机和基地分别按破坏力和防御值从小到大排序,维护一个前缀最大值即可,复杂度O(n)

B.二进制

我们考虑对于二进制下每一位分开处理,记录该位若是 1 会变成几,若是 0 会变成几,以此为标准分配三种运算即可,3 次操作之内即可满足条件,复杂度O(nloga)

C.积木

首先可以发现当 n 为奇数时必然无解
对于 n 是偶数,我们给出两种构造方案
1:从外向内一圈一圈黑白染色,上下两层颜色相反即可

2:以一个 的方块为基本单位,黑白相间摆满整个立方体即可

D.种树

二分答案,考虑如何 check 答案 mid 是否合法
我们将 val > mid 的权值定义成 0 ,将 的权值定义为 1
用 f[i][0/1] 表示该节点获得 0/1 最多能用几次 min ,显然 min 操作用 max 替换不会变的更劣,故当 时,答案即合法

在比赛中,发现最多只能获得深度小于等于操作次数的点的子树min传到根,这个做法也是对哒

E.考试

贪心,把一样的尽量当他是对的,不一样的尽量当他是错的即可

F.项链

用双向链表模拟即可

G.涂色

输出 n+1 即可,模数是来吓人的

H.圆

分类讨论一下即可,这里出题人可能没说清楚,有交的是指有交点,故相切也算

I.修改

在链最后创建一个虚点,对于第 i 个操作,给 l_i 两个点连上一条边权为 w_i 的边,对这个图求一棵最小生成树即为答案
为什么?可以这样考虑:由于所有点的值为 0,所以其差分数组也都为 0
把操作视为在差分数组的 l_i 加上数 x,在 减去数 x,由于之前的差分数组肯定存在不为 0 的构造方式,所以我们必须把所有的差分值都转移到**虚点的位置**
而上面的边的含义是差分值的转移,所以充要条件是:每个点都可以通过选择的有向边到达虚点
由于边都是从前往后连的,所以有向边可以视为无向边,最后必然形成了一棵以虚点为根的树,最小代价为最小生成树大小

J.克隆

我们发现这个 很有趣,显然所有的 k 个人能走的点数总和 >=2n
很自然的想到一个叫欧拉序的东西,这个序列的长度是 n+m=2n-1 的
那么把欧拉序拉下来,让分身在欧拉序上走即可



全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐