~ Esoteria Algorithm in Reverse Observatory

FHQ Treap | 非旋式树堆

Prologue

前置技能

一些定义

  • 树中任意节点的权值都大于或等于其父节点的权值,则称该二叉树满足 “小根堆性质”
  • 二元搜寻树(Binary Search Tree, BST)是一棵空树或具有下列性质的二叉树

左偏树

Prologue

左偏树是一种合并复杂度很优秀的堆。下图就是一棵典型的左偏树,蓝色的数字为该节点的路径长。

Cover Image

NOIP2018 骗分指南

Prologue

据悉,CCF 本人予以承认。它的泄题行为在选手中造成一定的恐慌和混乱,干扰了正常的竞赛秩序,有损竞赛的声誉,也给组织方带来不必要的负担和干扰。

LGOJ P3393 | 逃离僵尸岛

Portal

​题目只有两个步骤:处理每个点的点权;跑一遍点权最短路。

​对于 KK 个城市,可以考虑把点权赋为 \infty 。对于 KK 个点周围的点,可以 bfs 进行预处理。但当 KK 较大时,复杂度为 O(kN)O(kN), 与队列优化的 Bellman ford 相同。

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

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

线段树优化 Dijkstra

过早的优化是万恶之源。
Go beyond speed.

一般的 Dijkstra 使用 priority_queue 维护当前最短路的距离,但不吸氧气的 STL 性能表象不佳。维护当前最短路距离需要不断取出最小值,可以通过线段树查询最小值再修改为无穷大来模拟。

负环与单源最短路计数

Prologue

  • 若图上存在一个环,环上各边的权值之和是负数,则称这个环是负环。

负环判定

​设 cnt[v] 表示从 11vv 的最短路径包含的边数,cnt[1]=0。当执行更新 d[v]=d[u]+w 时,同样更新 cnt[v]=cnt[u]+1。此时若发现 cnt[v]>=n,则图中有负环。若算法正常结束,则图中没有负环。