OI

昨天考试完成T4时，明明想出了正解，但又以为二叉堆时间复杂度过高不敢实现……白白浪费了几十分钟时间。事后实现，发现完全没有技术上的问题。

具体来讲，通过同时保存指向每个元素在堆中当前位置的指针，可以$\mathrm{O}(\log n)$地修改和删除特定节点，以及常规的$\mathrm{O}(\log n)$的弹出栈顶、插入等操作，$\mathrm{O}(1)$地查询堆顶元素。

下面就以动态修改无向图中每个点的度并查询最小度的点为例实现一个这样的二叉堆。

（更多…）

基数排序是一种非比较的排序算法。它基于对每个子关键字在值域上的计数实现整体的排序。对于整数，可以在$\mathrm{O}(kn + \sum\limits_{i=1}^{k}w_i)$的线性时间内完成排序，其中$w_i$为每个关键字的值域大小。

以下代码将对int范围内的整数，以前$16$位和后$16$位为关键字进行排序。可以发现，在数据个数$n \leq 7\times 10^4$，其表现不如基于比较的快速排序算法。因此，在值域很大而数据较少时，应合理调整策略。

（更多…）

说来惭愧。从国庆到现在，至少有3个人试图把我讲懂期望，但我还是只明白最基本的定义，根本不会做题。

今天发现一篇入门级别的数学期望讲解，在此转载。

Educational Codeforces Round 115

A – Computer Game

由题意可知这是一个八连通的$2 \times n$网格。故我们扫描一遍，发现某列的两个格子均无法通过则失败。复杂度$\mathrm{O}(n)$。

（更多…）

或许是人品不错，最近两天接连刷到三道排列组合相关的题。在此作简单整理。

AtCoder ABC226 F – Score of Permutations

题意参见原题面。

很自然地想到，对于一个排列$P = (p_1, p_2, \dots, p_n)$，有$n$条$i \rightarrow p_i$的连边。因为排列中正整数$1, 2, \dots, n$恰好出现仅有一次，所以等价于每个点有且仅有一条出边、一条入边的图。容易发现这个图由若干个有向环构成（包括自环——即$p_i = i$的情况）。例如排列$P = (1, 3, 4, 2)$代表由$1 \rightarrow 1$和$2 \rightarrow 3 \rightarrow 4 \rightarrow 2$两个环组成的图。

（更多…）

（更多…）