~ Esoteria Algorithm in Reverse Observatory

NOI2015D1T1 | 程式自动分析

Portal

OI 中离散化方法很多,常见的有 std::sort std::unique,然后 std::find 查找键值对,也可以用 std::map<key,val> 直接进行 insert()find() 。不过 map 不吸氧气几乎要 T 掉,sort unique 也不算快。观察数据范围发现最多只有 100,000 对关系,不同的数最多只有 200,000 种,可以考虑进行简单取膜 hash,取一个稍大于 200,000 的素数作为膜数,取膜后扔进并查集。

CF939D | Love Rescue

Portal

比较好玩的一个并查集水题。只要看懂题面,看出是并查集就可以直接切掉,所以无可奉告。