Codeforces #565 Div.3 小结

比赛链接:Codeforces #565 Div.3

A – Divide it!

按照题意模拟。

B – Merge it!

统计模3余0,1,2的数各有几个,然后贪心凑整。

C – Lose it!

记$ t = \{ 4,8,15,16,23,42 \}  $,$O(n)$扫描整个序列,$a_i$可取当且仅当$a_i$在$t$中的前一个数的个数大于已经统计到的$a_i$的个数。

D – Recover it!

观察规则:

  • $a_i \in P$,则追加$p_{a_i}$
  • $a_i \notin P$,则追加小于$a_i$ 的最大约数 $f(a_i)$

我们可以发现$p_{a_i} > a_i$,$f(a_i) < a_i$。我们可以对$b$进行从小到大排序,用类似于邻接表的查找结构存储每个数在$b_i$中的位置,这个结构满足可以快速删除/查找的性质。我们从后往前开始匹配,将匹配到的两个数删除,同时把匹配到的$a$中的数加入答案序列。

这里用set实现了这个快速删除/查找的结构,渐进时间复杂度$O(n \log n)$。

E – Cover it!

从任意一个点开始dfs,对搜索树分层染色,偶数层染$c_1$,奇数层染$c_2$,最终$c_1$的个数和$c_2$的个数总有一个小于等于$\lfloor \frac{n}{2} \rfloor$。

F – Destroy it!

待填坑。

说点什么

avatar
50
  Subscribe  
提醒