ThinkofBlank

论文

未归档(4) 题单(1) 题解(90)

/ 注册

全部文章 / 论文（共10篇）

基于字典树实现的O(n)排序来自专栏

我们用字典树，从高位到低位进行排序，使用中有类似于基排的思路。残留问题在于，空间方面，需要我们使用vector或类似的动态扩充的来做。不过，不想去想了，先给个代码： #include<bits/stdc++.h> using namespace std; const int N=1e5...

研究

2020-05-20

1 535

关于无向图缩点

把之前的补过来/xk 最近,做了好多图论,其中大部分都跟tarjan有关,而又有好多无向图。。。orz 我们都知道,tarjan会把能互达的若干点合并为一个点,然而,在无向图中,所有点都可互达(图联通),故,整个图就会缩成一个点...然鹅,我们把图画出来,又是另外的样子...明明就只有一个环,却把所...

理解图论研究

2020-05-19

0 1229

玄学最短路算法——Ex Floyd 来自专栏

Floyd再思考 ——by ThinkofBlank 一.序言 Floyd,是一个十分常用的图论算法，其作用是在O(n^3)的时间内计算出全源最短路。其实现原理是利用的dp,然而，刚开始接触Floyd的时候，并没有去尝试理解，思路此算法，仅仅记了下打法就跑了，最近无聊时思考了下，得...

研究优化理解图论

2019-02-24

0 614

实现非递归树链剖分来自专栏

树链剖分，是个很神奇蛇皮的算法，他巧妙的运用了与分块类似的思想，来加速整块代码。不过，对于某些毒瘤题来说，树链剖分很可能会爆栈，如：一本通:染色。不过洛谷还好，不会爆栈。。。那么这个时候，我们就需要手动模拟来实现非递归版本的树链剖分了。注意到，整块树链剖分的代码中使用了递归的地方:...

研究优化图论

2019-01-21

1 479

快速计算高精乘低精---低精优化高精来自专栏

这是一个普通人都想得出来的超简单但很有用的优化。 -----序言给一个题: 计算n!的阶乘,n<=10000，时限500ms。一.各种算法要是你打普通高精乘低精,辣么恭喜您GG，要是您不爽时限，给他加大成1000ms，恭喜您,还是GG。于是，您就可以光荣的放弃打...

研究优化

2019-01-12

0 519

高精板子合集(string版本)

#include<bits/stdc++.h> using namespace std; const int N=100001; int a[N],b[N],c[N]; inline string zhuan(int x){//int转化string string ant="...

研究高精

2018-12-21

0 519

二分链表插入排序来自专栏

这玩意儿,效率一般... 本来估摸复杂度为O(nlogn),但似乎用stl后更高? 代码: //#pragma GCC optimize()//手动Ox优化 #include<bits/stdc++.h> using namespace std; const int...

研究排序

2018-12-19

0 543

素剩倍筛来自专栏

#include<bits/stdc++.h> using namespace std; const int N=1e8+1; int las[N],nex[N],sta[N],top; bool f[N]; inline void fsbz(int maxe){ &...

研究筛法

2018-12-19

1 524

关于扩展欧几里得中求最小非负x的方法的推导

推导假设,我们已经求出有一对x,y满足ax+by=gcd(a,b)。我们想要求最小非负整的x,那么必须要减去一个能减的最大值,我们设减去一个D,则方程变为: a(x-D)+by+aD=gcd(a,b) 整合一下： a(x-D)+b(y-aD/b)=gcd(a,b) 我们...

数论理解

2018-12-19

0 466

快速模拟暴力组合数来自专栏

本题解讲的是快速暴力组合数的方法，需要知道以下知识(能做此题的大佬应该都知道吧。。。)：欧拉筛，组合数公式,卡速米(这个应该没人会吧？) 否则将引起不适设π(x->y)为从x连乘到y(数学公式编译器崩了。。。) 组合数，大家都知道，公式为C(n,m)=!n/(!m*!(n...

数论研究

2018-12-19

0 492