分享几个第一次看到就被它的优美深深震撼到的代码

  • 时间:
  • 浏览:92
  • 来源:无双科技

优美深深震撼到的代码

1、线性求逆元:

for (int i = 2; i < MAXN; i++)
inv[i] = mul(inv[mod%i], mod - mod / i, mod);

仅仅两行代码,就实现了在$O(n)$的时间内求出1到n对模m的逆元有木有!?

2、求最大公因数:

int gcd(int x, int y){return y ? gcd(y, x%y) : x;}

第一次接触到这样的代码时,我的内心是这样的:

wtf???黑人问号.jpg

3、树状数组

对于单点修改区间求和,树状数组可谓达到了时空复杂度的极限,甚至不多用额外一字节存储空间。来看看它的实现:

修改:

void add(int i, int x){
for (;i <= n; i += i & -i)tree[i] += x;
}

查询:

int sum(int i){
int ret = 0;
for(; i; i -= i & -i)ret +=tree[i];
return ret;
}

表示记性不好的我看完一遍也记住了呢。

4、zkw线段树

对于单点修改区间查询的线段树,zkw大神实力教你如何1分钟内码出代码:

修改:

void set(int x, int value){
val[x += treeLen] = value;
while (x >>= 1)pushUp(x);
}

查询:

int query(int l,int r){
int ret = 0;
for (l += treeLen - 1, r += treeLen +1; l ^ r ^ 1; l >>= 1, r >>= 1){
if (~l & 1)ret = min(ret, val[l^1]);
if (r & 1)ret = min(ret, val[r ^ 1]);
}
return ret;
}

以上都是一些十分基础但真的让你赞不绝口的算法和数据结构。还有一些稍微复杂一些的栗子,由于手机码代码太不方便了,就以后再更吧。(如果有笔误打错的地方欢迎指正哈)

5、后缀数组的DC3算法,反正学完它的一瞬间我是明白了,天才和普通人的智商差距简直比人和狗还大啊。。。

6、快速傅里叶变换的数论版本(即NTT):学完后有种想去数学系的冲动(还好后来冷静下来了)。费马素数群的性质居然和复数完美吻合,不得不说是一种奇迹啊。

7、主席树:这是fotile巨佬考场上发明这种数据结构,用于在$O(log n)$的时间复杂度内解决序列区间第k大问题,以及区间内元素的排名。个人感觉他比划分树的设计巧妙多了,有一种自然的美感。

8、Pollard因数分解算法:如果你真的把关于时间复杂度的证明一步步看完后,相信你会有一种豁然开朗的感觉。这个算法真正高的地方在于把生日悖论和递推式循环节巧妙的结合在一起,最后运用递推方程主定理的理论,使得时间复杂度达到了看似不可能的期望$n^0.25$的数量级。

其实现在感觉一切和数据结构或数学有关的算法都是非常优美的,前者在于设计的精巧性,后者在于证明的环环相扣,达到引人入胜的效果。

猜你喜欢

谷歌SEO实战经验:我是怎样1周内将新网站DA和PA提升到10的?

谷歌SEO实战经验:我是怎样1周内将新网站DA和PA提升到10的?

最近做了一个B2B网站,之前一直在做网站的基本建设。从2月1号开始做网站的SEO,差不多一周时间网站的DA和PA增加到10(MOZ:DA11,PA10)。下面外链收录情况和近7

2020-02-19

H5网页布局+css代码美化,零基础参考

H5网页布局+css代码美化,零基础参考

HTML5的结构化标签,对搜索引擎更友好li标签对不利于搜索引擎的收录,尽量少用banner图片一般拥有版权,不需要搜索引擎收录,因此可以使用ul+li<samp>

2020-02-14

SEO快排的常见公式

SEO快排的常见公式

流量公式SEO流量=整体收录量×整体排名×整体点击率整体收录率与网站构架和内容有关,一般企业网站、个人博客等不存在这个问题,只有上规模的大中型网站有收录的问题,而且是普遍存在收

2020-02-14

SEO快排百度优化推广网站优化排名

企业信息系统建设的5个阶段

企业信息系统建设的5个阶段

信息系统基本涵盖了公司的所有方面,从员工到业务,算一个较重的工具。很少有公司在成功之初就上大型的信息系统,基本是企业人数、业务,发展到一定规模才会上专业的管理软件。毕竟不可能公

2020-01-13

5行代码,实现一个js的打字效果

5行代码,实现一个js的打字效果

有次看电影,看到屏幕上一个个的文字蹦出来,感觉像是有人在打字一样,觉得挺有意思,于是这里也用js实现了一个。效果预览最简单的打字效果只要五行代码,这里直接贴出来:constdo

2020-01-07