~ Esoteria Algorithm in Reverse Observatory

Cover Image

JZOJ3501 | 物语(ものがたり)

あぁ、青春の在り処も
幸福のルールも見つかってないから
泥に塗れたって
足が縺れたって
探しているんだろう
探していくんだろう

LGOJ P1254 | 扇区填数

Portal

有一个圆,当输入一个整数 n(1n8)n(1\leq n\leq 8) 后,它被分成 nn 个扇区。

所以圆中有 nn 条分割线。从圆中选取 2 条分割线,可以将圆分割为由连续扇区组成的两部分。又选择所有扇区是被允许的,所以:

i2Cn2+1=n2n+1i\leq 2\cdot C_n^2 +1=n^2-n+1

因为 n8n\leq 8 ,所以 i57i\leq 57。但通过手算,可以 大胆猜想 在本题中上式可以取等号。并且不难发现:当 n5n\leq 5 时,扇区中可以填的最大数为 ii;当 n>5n>5 时,扇区中可填最大数为 22。所以只需爆搜出每一位即可。

POJ3070 | Fibonacci

Portal

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

LGOJ P1175 | 表达式的转换

Portal

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

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

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

Cover Image

树的中心

CAUTION
本文含有大段写得很丑的 Golang,可能会引起不适(

题目描述
蓮子和梅莉玩游戏。梅莉掏出一棵无根树,要蓮子在规定时间内确定一个点,使得这个点到其他点的最长路径最小,蓮子是一个只会 AK IPhO 的巨佬,所以她请教你帮她,事成之后就和梅莉结婚。