Codeforces – Manthan, Codefest 18 (Div.1 + Div.2) 解题报告

链接:Manthan, Codefest 18 (rated, Div. 1 + Div. 2)

继续上分!

A – Packets

取或不取自然联想到二进制表示。求一下二进制位数即可。

B – Reach Median

贪心思想,如果当前中位数比目标数小,则向后把每个比中位数小的数字加到中位数。反之,把前面每个比中位数大的数前去中位数。

C – Equalize

贪心思想,考虑swap和flip在什么情况下更优。

对于一个swap操作,需要的代价为$j – i$,假设$j > i$,如果通过flip来实现的话需要的代价为2,那么只有$j – i < 2$的时候才会做swap,也就是$j = i + 1$的时候。考虑两个相同肯定是不用换的,没有意义,当且仅当$i$和$j$所处的位的元素不同,并且交换之后a和b的对应位置相同的时候才需要交换。

D – Valid BFS?

验证BFS序列。

BFS序应该是BFS的出队顺序,给出的a数组就是一个队列。所以我们只需要取一个头元素,看看这些头元素能拓展到的元素有几个,就把队列尾部向后移动几位,然后看一下队列中的这几位是否就是能拓展出的数(用set存邻接表)。

E,F,G,H

待填坑

说点什么

avatar
50
  Subscribe  
提醒