当我们提到 “Treap” 的时候,我们实际上说的是 “Tree” + “Heap”。朴素的 Treap 在插入的时候给每个点一个随机的 Key,通过旋转来满足堆的性质。对于 FHQTreap,我们不再使用旋转维护,转而使用拆分和合并。
Category: Notes
【学习笔记】快速傅里叶变换
Posted on快速傅里叶变换(Fast Fourier Transform,FFT)是一种可在 $\Theta(n \log n)$ 时间内完成的离散傅里叶变换(Discrete Fourier transform,DFT)算法。
这篇文章将简单地讲解它的工作原理,以及使用 C++ 的代码实现。
【笔记】映射方法在几何计数中的应用
Posted on作者:余不悔,高二,2018 年 CMO 铜牌获得者。 对于两个有限集合 $A$ 和 $B$,如果存在一个一一映射:$f:A \rightarrow B $,那么就有 $|A|=|B|$。 在某些情况下,如果 $A$ 的元素个数不好求,那么我们可以寻找一个集合 $B$,并建立起 $A$ 到 $B$ 的一个一一映射,然后去计算集合 $B$ 的元素个数,从而将问题解决。在这个过程中,寻找到容易计算元素个数的集合 $B$ 是至关重要的一步。 譬如下面这个大家都很熟悉的例子: 在 $6 \times 6$ 的方格表中,从左下角的 $A$ 点到右上角的 $B$ 点沿方格表的最短路径有多少条? 容易发现,从 $A$ 点到 $B$ 点的最短路径中,全部由 “向上” 和 “向右” 的线段组成,且各有六条。因此,我们建立起集合 $B$,定义它包含 “在 12 条线段中,选择 6 条作为向上线段的方法”。这样,对每一个确定的 $B$ 的元素,都可以唯一对应一种 $A$ 的方法,而对于 $A$ 的每一种方法都可以唯一的生成一个 […]
【笔记】动态 DP
Posted on这个算法的名字好毒瘤的样子。。。Dynamically Dynamical Programming,动态 – 动态规划,简称 DDP。 我们先考虑简单的动态规划。有一个经典问题叫做树上最大权独立集。比如 没有上司的舞会。 那么我们可以设 $f_{u,1}$ 为 $u$ 在独立集内的最大收益,$f_{u,0}$ 为 $u$ 不在独立集内的最大收益。转移方程如下: $$f_{u,1}=\sum_{v\in son}f_{v,0}$$ $$f_{u,1}=\sum_{v\in son}\max (f_{v,0},f_{v,1})$$ 现在我们要支持的操作是动态修改某个点的权值,比如 洛谷模板。 为了快速维护,我们先对整棵树做一个树剖,然后对每一条重链分别进行 dp。 对于重链上的每个点,先根据轻儿子的 $f$ 维护 $g_{u,1/0}$: $$g_{u,0}=\sum_{v\in lightson}\max(f_{v,0},f_{v,1})$$ $$g_{u,1}=\sum_{v\in lightson} f_{v,0}$$ 对于重链上的点,则有: $$f_{u,0}=g_{u,0}+\max(f_{heavyson,0},f_{heavyson,1})$$ $$f_{u,1}=g_{u,1}+f_{heavyson,0}$$ 这样,树上的问题就转化成了序列上的问题。我们可以对于每条重链维护一颗线段树。修改一个点的值就在这个点所在重链的线段树上修改,最后改变了重链顶端的点的 $f$ 值,进而影响了其父亲的 $g$ 值,反复向上修改,时间复杂度就是 $\Theta(log^2n)$ 的。 问题来了,如何用线段树维护 $f$ 呢。我们重新定义矩阵乘法。对于 $C=A\times B$,有 $$C_{i,j}=\max\limits_{k=1}^{n}(A_{i,k}+B_{k,j})$$ 于是,重链上的转移可以写成这样的矩乘 $${\left[ \begin{array}{cc}g_{i,0} &g_{i,0}\\ g_{i,1} […]
【杂谈】对崔永元纪录片的不严谨分析与解读
Posted on2014年3月1号,崔永元先生公布了自费 100 万元拍摄的赴美考察转基因纪录片,时隔四年多,这部纪录片里提出的观点还有多少可挖掘的价值?我将从头开始分析一下视频的主要内容,希望给读者带来更多的思考。
【NOIp 2018】Day 1 & 2 / 考后总结
Posted onNOIP 2018 游记。
【笔记】关于 KMP
Posted on考前记忆模板。 我们回忆一下 $next$ 数组的含义: $next[i]$ 表示在 $[1,i-1]$ 内,前缀与后缀相同的部分最长是多长。可以理解为,若第 $i$ 位失配了,至少要往前跳多少步,才可能重新匹配得上。 于是对于匹配串,预处理出它的 $next$ 数组,然后对文本串逐位匹配即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <bits/stdc++.h> #define maxn 1000001 char p[maxn],t[maxn]; int next[maxn],n,m; int main(){ scanf("%s%s",p+1,t+1); n=strlen(p+1),m=strlen(t+1); for (register int i=2,j=0;i<=m;++i){ while(j&&t[j+1]!=t[i]) j=next[j];//失配则回到上个匹配的位置; if (t[j+1]==t[i]) j++;//匹配就继续向后 next[i]=j; } for (register int i=1,j=0;i<=n;++i){ while(j&&p[i]!=t[j+1]) j=next[j];//失配则回到上个匹配的位置; if (t[j+1]==p[i]) j++;//匹配就继续向后 if (j==m) printf("%d\n",i-m+1),j=next[j];//完整匹配则输出 } for (register int i=1;i<=m;++i) printf("%d ",next[i]); return 0; } |
后记 不知道为什么我内心一直觉得 NOIp 会考这个算法。。。说不定被我奶中了呢。。。
【Tips】NOIp 防翻车指北
Posted on写代码时请注意: 是否要开 long long?数组边界处理好了么? 实数精度有没有处理? 特殊情况处理好了么? 数组是否足够或者过大? 做一些总比不做好。 当你把你的暴力程序改成正解时,记得扩大数组。 思考提醒: 最大值和最小值问题可不可以用二分答案? 有没有贪心策略?否则能不能 dp? 考场调整: 写下代码前,必须保证有充足的思考时间,有成熟的想法后再动手; 写代码前,尽量用多而强的数据去测试想到的算法,毕竟代码写完后再测试就浪费很多时间了; 不能想一点写一点,就算是输入部分也要在整体思路理清后再写; 永远别去写从未接触过的算法/数据结构; 有多余时间可以尝试进行对拍,即 3 个程序:生成数据、朴素算法(暴力算法)、准备交的算法; 如果你发现你旁边的人写得很快,请你放心,他的算法十有八九是错的,神仙没有你想象中那么多; 交之前 5 分钟千万不要再改动代码,主要留意代码中是否还有测试程序时留下的痕迹; 走出考场后,除非已经是 Day 2,永远别对答案。 其他注意事项 作者:lornd
【杂谈】尝试签约视觉中国
Posted on(10/12)UPDATE 意料之中… 这是我的 500px 主页 众所周知,我是一个能力低下设备糟糕的摄影爱好者,擅长拍废片和烂片。 我花了一年多的时间凑齐了二十张稍微能看的照片,在 2018年10月7日提交了审核,结果会在 3~4个工作日里出来。现在先把这些照片放出来污染一下读者的眼睛。 (懒得再传一遍了你们直接去 500px 看吧顺便点个赞什么的) 这里只放我个人最喜欢的几张: 摄于 Nikon D7100 摄于 SONY Xperia X 摄于 Nokia 7
【大坑】网络流 24 题集合
Posted on在看题之前。。。 感谢前辈写出的优秀论文。 部分资源分享(持续更新中) 序号 标题 备注 题解 1 飞行员配对方案问题 最大匹配 裸题 2 太空飞行计划问题 最大权闭合子图 / (最小割) 建模SSL_XXY_BlackCloud 3 最小路径覆盖问题 最小路径覆盖(废话) 参考部落战争 4 魔术球问题 (贪心可做) 代码 5 圆桌问题 多重匹配(奇水无比) 代码 6 最长递增子序列问题 分层图 / 最大流 7 试题库问题 二分图匹配 8 机器人路径规划问题 听说最优解不是网络流 9 方格取数问题 最大点权独立集 10 餐巾计划问题 最小费用最大流 11 航空路线问题 最大费用最大流 12 软件补丁问题 最小转移代价 13 星际转移问题 分层图最大流 […]