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

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

优美深深震撼到的代码

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

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

猜你喜欢

CSS:度量单位(px,em,rem,vw,%等)

CSS:度量单位(px,em,rem,vw,%等)

介绍我决定写这个博客的目的是希望探索更多有关使用CSS调整大小的方法。有这么多种可能性,很容易感到不知所措和困惑。浏览器当前支持16种度量单位:像素,英寸,皮卡,厘米,毫米,点

2020-04-07

PHP下载文章中的图片+处理文章中的字符

PHP下载文章中的图片+处理文章中的字符

//保存路径$d=date('Ym',time());$dirslsitss='/uploads/images/'.$d;if(!file_exists($dirslsitss

2020-03-27

网站利用JS自动提交至百度搜索资源平台

网站利用JS自动提交至百度搜索资源平台

什么是百度链接提交自动推送JS代码自动推送JS代码是百度站长平台最新推出的轻量级链接提交组件,站长只需将自动推送的JS代码放置在站点每一个页面源代码中,当页面被访问时,页面链接

2020-03-27

Web网站站点页面优化加载速度

Web网站站点页面优化加载速度

Web页面性能优化,解决了图片相关,问题就解决了大半。本文从Web常见的图片格式入手,引出与图片优化相关的有效方案,期望对大家能有一点帮助。先来点背景知识注:如下说明整理于网络

2020-03-27

网站加速网站压缩优化加载速度

SEO优化百万关键词批量组合生成软件

SEO优化百万关键词批量组合生成软件

很多新手在刚接触SEO的时候,往往学到一定的技术,想自己实现操作的时候,发现缺少了最重要的一点!关键词!!!没有关键词拿什么来操作seo排名呢?谈何批量上排名呢?哈哈哈,这里就

2020-03-25