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

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

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$的数量级。

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

猜你喜欢

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

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

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

2020-01-13

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

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

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

2020-01-07

什么样的网站才叫大气?如何设计出大气的网站?

什么样的网站才叫大气?如何设计出大气的网站?

做过网站建设的工作的人都有体会,当问及许多客户对网站的需要的时候,他们大多数都说不上来,但是通常他们都会说网站设计的要“大气”。做为一个网页设计人员遇到这样的词是有些头疼的。因

2019-12-12

[源码分享]一个扁平化风格响应式布局的后台管理模版

[源码分享]一个扁平化风格响应式布局的后台管理模版

一个很赞的,扁平化风格的,响应式布局的后台管理模版,旨为后端程序员减压!PC端效果预览手机移动端效果预览项目地址:https://gitee.com/bobi1234/ok-a

2019-12-09

[源码分享]开源的自定义表单设计器源码

[源码分享]开源的自定义表单设计器源码

自定义表单设计器,这是一个现代化应用中一个加分的模块,目前很多大型的系统都会存在很多表单,针对不同的客户,可能表单都会不一样,而且不够灵活,可能针对不同的场景都得去定制化的开发

2019-12-03