2021-06-11

SB树

这棵二叉树中包含了所有的非负有理数。

2021-04-29

CF708D2

D题

题很好，感觉思维得到了升华。把整个题考虑成一个图，对每对 $\{i, j\}$ ，只要tag[i] != tag[j]他们之间就要连边，边权为 $$|2^i-2^j|$$ 。按照题意，需要找一条边权不断上升的、 $\sum|s_i-s_j|$ 最大的路。由于边权不断上升，可以将边按边权排序（外层 $$i$$ 从小到大，内层 $$j$$ 从大到小），然后使用动态规划：dp[i][t]维护只使用前 $$t$$ 条边时，终点为 $$i$$ 的路的路径权值最大值。考虑转移，发现 $$t$$ 增加 $$1$$ 时只有至多两个dp值会发生变化，因为一步只引入了一条边，而且它只能被加在已经考虑过的路径的末尾。这样，我们可以舍弃 $$t$$ 维度，而代之以时间维度： $$dp$$ 数组只有一维，dp[i]维护当前时刻以 $$i$$ 结尾的路的路径权值最大值。每当时刻前进1，就新考虑一条边，更新一下dp[i]和dp[j]： $dp_i = \max(dp_i, dp_j + |s_i - s_j|)$ 和 $dp_j=\max(dp_j, dp_i+|s_i-s_j|)$ 。

2021-04-20

算法

区间众数

通用求众数离线做法：离散化之后，开线段树维护数出现的频率的最大值，带单点修改，然后再用莫队，移动区间时就跑一个单点修改，复杂度是 $O(n\sqrt{n}\log n)$ 。

2021-02-05

奇技淫巧

筛选法建堆

这可能是本学期学习数据结构与算法课的最大收获，就是知道了还有线性建堆的方法。线性建堆可能也是有应用场景的，比如用 $$O(n)$$ 的空间及时间复杂度，取出前 $n/\log n$ 大的所有数。（？

2020-12-28

游记

ICPC2020济南站

话说线上赛有啥游记好写的…但是作为惯例还是写一个。

2020-07-18

Algorithm

BIT在线求第k大数

在做小学期Day5C题（在线维护中位数）时，由于我没有做过，也没有想到正解（对顶堆），卡了很久，最后用一个奇怪的方法做出来了。发现这个奇怪的做法复杂度稍高，但是可以扩展。对顶堆只能维护中位数或固定k的第k大数，而奇怪做法可以（伪？）在线查找第k大数，k可变，代价是 $O(\log^2 n)$ 的， $$n$$ 为数列长度。