CF-Codefest18 Solution

A. Packets

题意

问你$1\sim n$最多可以通过几个数的和全部表示出来.

题解

类似二进制,算一下就行.(WA $\times$ 1, 6minA掉)

B. Reach Median

题意

给出$n$个数,问你把$n$个数的中位数变成$k$的最小代价,代价指的是把$a$变$b$,花费$|a-b|$

题解

sort一下(6min1A)

C. Equalize

题意

把$0$变$1$花费是$1$,把$a_i$和$a_j$交换花费是$|i-j|$,问把串$a$变串$b$的最小花费

题解

考虑如果距离大于1交换就没有意义了,直接for一遍,判断相邻的交换是否更优.

最后再扫一遍就好,(6min1A)

D. Valid BFS?

题意

给出一棵树和从1开始的BFS序,判断是否合法

题解

写这题的时候写了很久,可能是神智不清了.

一直决定直接判断深度没有毛病.然后就WA了好多次.

比赛还剩一个小时的时候才发现跟顺序有关

然后就只能删了重打.

具体做法是把BFS序列按照深度分层.然后对于每一层维护一个指针.

DFS实现,对于一个点DFS时,它的下一层所有点应该是连续的.而且应该是当前最靠前的.

那么每一层维护一个指针.顺着扫.

最后判断一下是否每个指针都在层的最后一个元素的位置.

代码+调试打了15分钟左右.换了做法就A了.

但是之前还是WA $\times$ 3,最后得分只有800多.比第三题还低.说明我很有问题,题目都读不清楚,真是太菜了.

E. Trips

题意

有$n$个点,每天会多一条边.问最大的集合使得集合中的每一个点连接的被选的点个数不小于给出的$k$.对于每一天输出一个答案.

题解

比赛的时候留给这个题的时间不超过50分种.看到A掉的人不多就没怎么认真想.

一直觉得可以带权并查集搞一下.但是我没有方法统计加入一个边的贡献.

想起来猴子那个题.觉得是不是可以倒着做.结果发现我最终情况怎么算答案都不会,思维迟钝.一直在想怎么搞联通块的一个子集,没啥收获,就弃疗了.

其实我的方向的是对的.但是思路不止仅限于联通块.

只需要把deg小于k的点放入队列BFS,然后每次加入点的时候倒着做BFS.给删掉的点打标记就好.

总结

这次CF的状态比上次打的时候要好很多了,切题速度有明显提升,(可能是因为这次的题意比较好看懂,看了样例就知道提议了),但是这样子还远远不够.切掉ABC三题的时候只过了17分钟.大概是400+左右的样子.后来D题因为WA了太多次.耗时巨大,罚分爆炸,直接GG.从400直接变为1000+.看来还是要多想想题目描述和细节,在设计算法之前想一下极端数据.不然交上去没有底气.挂掉或者FST都是不好的.其实慢一点无伤大雅,但是罚分一高就差距很大了.

写出E题的只有300+,那么如果少WA几次.我可以到rank700左右,如果不是D题浪费太多时间.或者说直接去写E,可能可以进前300.

所以,打CF还是要冷静,头脑更加清醒,才能打好.

9.3 02:05: D题没FST,早上7点还要上学,写完了blog,但是分还没算,E题还没交,睡觉了.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*