1619069063414549

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

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

优美深深震撼到的代码

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

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

猜你喜欢

百度竞价搜索推广怎么找到ip和屏蔽

百度竞价搜索推广怎么找到ip和屏蔽

在正常推广的时候,经常会早到恶意点击,虽然百度有机制不算到计费系统内,但还是会给客服接待人员造成大量困扰,为减少推广的成本,可以屏蔽一些恶意的点击IP,是最理智的选择,不过在国

2020-07-01

View UI(iView) Upload 自定义多图上传列表提交

View UI(iView) Upload 自定义多图上传列表提交

iViewUpload自定义多图上传列表提交可以自由控制上传列表,完成各种业务逻辑,示例是一个照片墙,可以查看大图和删除。设置属性 show-upload-list&

2020-06-29

iViewUpload上传

页面顶部空白行,源码显示&amp;amp;#65279解决方法

页面顶部空白行,源码显示&amp;amp;#65279解决方法

最近在做一个项目的时候,好几个页面都出现顶部莫名多出一定高度的空白,查看自己写的样式又没有添加这样的样式。查看源码后模板文件生成html文件之后会在body开头处加入一个可见的

2020-06-08

PHP反爬虫攻略禁止垃圾蜘蛛爬虫UserAgent频繁访问网站

PHP反爬虫攻略禁止垃圾蜘蛛爬虫UserAgent频繁访问网站

我们都知道网络上的爬虫非常多,有对网站收录有益的,比如百度蜘蛛(Baiduspider),也有不但不遵守robots规则对服务器造成压力,还不能为网站带来流量的无用爬虫,比如宜

2020-06-05

userAgent垃圾蜘蛛PHP反爬虫

各大中文网站蜘蛛userAgent及IP段

各大中文网站蜘蛛userAgent及IP段

UserAgent中文名为用户代理,简称UA,它是一个特殊字符串头,使得服务器能够识别客户使用的操作系统及版本、CPU类型、浏览器及版本、浏览器渲染引擎、浏览器语言、浏览器插件

2020-05-28

蜘蛛爬虫userAgent百度蜘蛛360蜘蛛google蜘蛛蜘蛛IP