~ Esoteria Algorithm in Reverse Observatory

POJ3070 | Fibonacci

Portal

矩阵加速递推,重点在于设计转移矩阵。画图分析:

LGOJ P1175 | 表达式的转换

Portal

很水的模拟题。先 stack 转后缀,不过似乎没有人用 list 去维护。本来可以跑得很快,但是一不小心优化过头是我的坏毛病,所以勉强忍住了。写法比较像 C++,是这次唯一的特点(笑)。用了几个很小的数代表运算符,很容易被 hack 吧。(满口 ZUN 语

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 性能表象不佳。维护当前最短路距离需要不断取出最小值,可以通过线段树查询最小值再修改为无穷大来模拟。