快速傅里叶变换（Fast Fourier Transform，FFT）是一种可在 $\Theta(n \log n)$ 时间内完成的离散傅里叶变换（Discrete Fourier transform，DFT）算法。
这篇文章将简单地讲解它的工作原理，以及使用 C++ 的代码实现。
Category: Notes
【笔记】映射方法在几何计数中的应用
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
【正睿 OI】国庆集训趣题分享
Posted on这几天在蔡老板的带领下学习到了很多有趣（shui）的题，挑几道印象深刻的分享一下。 自闭的游戏 题目描述 小 A 和小 B 在玩一个游戏，游戏一开始有 n 张卡牌，第 i 张卡牌上面的值为 a[i]，且有一个关键数字 M。 两个玩家轮流操作，小 A 先手。每轮每个玩家可以移除任意一张卡牌，假设卡牌上的数字为 x ，则关键数字 M 会变成 $⌊\dfrac M x⌋$ 如果某位玩家操作后，关键数字变成 0 了，那么游戏结束，最后操作的玩家输。 小 B 玩了几天后输得有点自闭，所以他想问你，对于给定的 n 张牌 a[1..n]，有多少 $x∈[L,R]$，满足关键数字为 x 时后手必胜。 保证 $∏_{i=1}^{n}a[i]>R$，这样永远都不会出现没有牌了但是游戏还未结束的情况。 数据范围 对于 100% 的数据，有 $1≤n≤10$，$1≤a[i]≤1000$，$1≤L≤R≤10^{18}$，$\prod\limits_{i=1}^{n}a[i]>R$ 思路 首先我们不要管 $L,R$ 的范围，思考一下对于一个确定的 M 如何快速求得答案。。。然后会发现无法快速求得答案。。。 这个时候观察发现 $n$ 不管什么时候都很小，考虑一下是不是可以暴搜判断胜负。 枚举两个人在某个时刻选择了哪张牌，发现最后的胜负是取决于选出来的牌的数字之积（废话）。由于 M 是被整除，所以对于一个数字之积，对应的一段连续 […]
【大坑】网络流 24 题集合
Posted on在看题之前。。。 感谢前辈写出的优秀论文。 部分资源分享（持续更新中） 序号 标题 备注 题解 1 飞行员配对方案问题 最大匹配 裸题 2 太空飞行计划问题 最大权闭合子图 / （最小割） 建模SSL_XXY_BlackCloud 3 最小路径覆盖问题 最小路径覆盖（废话） 参考部落战争 4 魔术球问题 (贪心可做) 代码 5 圆桌问题 多重匹配（奇水无比） 代码 6 最长递增子序列问题 分层图 / 最大流 7 试题库问题 二分图匹配 8 机器人路径规划问题 听说最优解不是网络流 9 方格取数问题 最大点权独立集 10 餐巾计划问题 最小费用最大流 11 航空路线问题 最大费用最大流 12 软件补丁问题 最小转移代价 13 星际转移问题 分层图最大流 […]