「CF1237X」Codeforces Global Round 5

2019年10月19日2330

A. Balanced Rating Changes

先把所有奇数除二下取整,再任选一些加一

B. Balanced Tunnel

按进入顺序排序,依次考虑,维护出站顺序的最大值

直观理解就是,比一辆车先进站的,如果在它之后出站,它肯定插队了

C2. Balanced Removals (Harder)

先考虑二维情况,按 x,y 排序,可以把所有点看成一列一列的点,先再每一列上两两配对。这样每一列最多剩下一个,再把相邻列配对即可。

三维情况先按 z 排序,每个平面按二维做法做完以后最多剩一个点,再把相邻列配对即可。

D. Balanced Playlist

先用数据结构(线段树或单调栈),处理出每一个 track_x,预处理往后小于其 1 / 2 的 track 是哪个,记为 b_x

再对于每个 track 为左端点,找一个右端点,满足这个区间的 b 的最小值在这个区间内

这两步我都是用二分线段树实现的

由于题目中是一个环,从一个曲子出发,答案最多是 2n,所以把序列复制三遍维护

avatar
  Subscribe  
提醒