2019-2020 ICPC, NERC, Northern Eurasia Finals

2022-11-12,,,,

A. Apprentice Learning Trajectory

rdc乱编的做法

考虑贪心,每次会选择结束时间最早的。
设当前时间为 \(x\),那么可以区间有两类 a) \(l_i \leq x \leq r_i-t_i\),b) \(x \leq l_i\),用两个堆维护选择区间的结束时间。
堆被改变的次数与最优解变化次数都是 \(O(n)\) 级别的。


B. Balls of Buma


C. Cactus Revenge


D. DevOps Best Practices


E. Elections


F. Foolpr¨uf Security


G. Game Relics


H. Help BerLine


I. Intriguing Selection

265min, solved by rdc

做法

先比较出长度为 \(x,y\) 的两条链,满足 \(x+y = n+1\),那么两条链中最卜的元素不可能同时出现在前 \(n\) 大中。
每次淘汰掉较弱的那个,再插入一个新元素,让两条链的长度保持 \(x, y\)。


J. Just Arrange the Icons


K. Key Storage

139min, solved by rdc

做法

数字可以得到一个唯一的序列,序列可以得到一个唯一的数字。
序列合法等价于,序列的第 \(i\) 位(1-index) 小于等于 \(i\),且,序列最高位不为 0.
枚举最高位填啥,逐个考虑每位方案数,乘法原理。


L. Lexicography

2019-2020 ICPC, NERC, Northern Eurasia Finals的相关教程结束。

《2019-2020 ICPC, NERC, Northern Eurasia Finals.doc》

下载本文的Word格式文档,以方便收藏与打印。