（kuangbin）邝斌的ACM模板.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：1.35M 资料格式：pdf 举报版权申诉

第1页 / 共173页

qq_42809849-10876049-（kuangbin）邝斌的ACM模板.pdf-第2页.png

第2页 / 共173页

qq_42809849-10876049-（kuangbin）邝斌的ACM模板.pdf-第3页.png

第3页 / 共173页

qq_42809849-10876049-（kuangbin）邝斌的ACM模板.pdf-第4页.png

第4页 / 共173页

qq_42809849-10876049-（kuangbin）邝斌的ACM模板.pdf-第5页.png

第5页 / 共173页

qq_42809849-10876049-（kuangbin）邝斌的ACM模板.pdf-第6页.png

第6页 / 共173页

qq_42809849-10876049-（kuangbin）邝斌的ACM模板.pdf-第7页.png

第7页 / 共173页

qq_42809849-10876049-（kuangbin）邝斌的ACM模板.pdf-第8页.png

第8页 / 共173页

文本预览

上海大学 ACM 模板 by kuangbin 字符串处理 ............................................................................................................................... 2 1、KMP 算法 .................................................................................................................... 2 2、扩展 KMP .................................................................................................................... 5 3、Manacher 最长回文子串 ........................................................................................... 6 4、AC 自动机 ................................................................................................................... 7 5、后缀数组 ..................................................................................................................... 9 6、后缀自动机 ............................................................................................................... 13 7、字符串 HASH............................................................................................................. 15 数学......................................................................................................................................... 17 1、素数 ........................................................................................................................... 17 2、素数筛选和合数分解 ............................................................................................... 19 3、扩展欧几里得算法（求 ax+by=gcd 的解以及逆元素） ........................................ 20 4、求逆元 ....................................................................................................................... 20 5、模线性方程组 ........................................................................................................... 20 6、随机素数测试和大数分解(POJ 1811) ..................................................................... 21 7、欧拉函数 ................................................................................................................... 24 8、高斯消元（浮点数） ............................................................................................... 25 9、FFT ............................................................................................................................. 26 10、高斯消元法求方程组的解 ..................................................................................... 29 11、整数拆分 ............................................................................................................... 34 12、求 A^B 的约数之和对 MOD 取模 .......................................................................... 36 13、莫比乌斯反演 ......................................................................................................... 37 14、Baby-Step Giant-Step .............................................................................................. 39 15、自适应 simpson 积分 ............................................................................................. 40 相关公式 ......................................................................................................................... 40 数据结构 ................................................................................................................................. 42 1、划分树 ....................................................................................................................... 42 2、RMQ .......................................................................................................................... 43 3、树链剖分 ................................................................................................................... 45 4、伸展树（splay tree） ............................................................................................... 50 5、动态树 ....................................................................................................................... 55 6、主席树 ....................................................................................................................... 60 7、Treap.......................................................................................................................... 70 图论......................................................................................................................................... 75 1、最短路 ....................................................................................................................... 75 2、最小生成树 ............................................................................................................... 79 3、次小生成树 ............................................................................................................... 80 4、有向图的强连通分量 ............................................................................................... 81 5、图的割点、桥和双连通分支的基本概念 ............................................................... 84 6、割点与桥 ................................................................................................................... 85 7、边双连通分支 ........................................................................................................... 88 8、点双连通分支 ........................................................................................................... 90 9、最小树形图 ............................................................................................................... 93 10、二分图匹配 ............................................................................................................. 95 11、生成树计数 ............................................................................................................. 98 11、二分图多重匹配 ................................................................................................... 101 12、KM 算法（二分图最大权匹配） ........................................................................ 102 13、最大流 ................................................................................................................... 103 14、最小费用最大流 ................................................................................................... 109 15、2-SAT ...................................................................................................................... 110 16、曼哈顿最小生成树 ............................................................................................... 114 17、一般图匹配带花树 ............................................................................................... 117 18、LCA ........................................................................................................................ 120 19、欧拉路 ................................................................................................................... 126 计算几何 ............................................................................................................................... 133 1、基本函数 ................................................................................................................. 133 1 / 173 ACM 模板 kuangbin

上海大学 ACM 模板 by kuangbin 2、凸包 ......................................................................................................................... 138 3、平面最近点对（HDU 1007） ................................................................................ 139 4、旋转卡壳 ................................................................................................................. 140 5、半平面交 ................................................................................................................. 146 6、三点求圆心坐标（三角形外心） ......................................................................... 149 7、求两圆相交的面积 ................................................................................................. 150 8、Pick 公式 ................................................................................................................. 150 动态规划 ............................................................................................................................... 150 1、最长上升子序列 O(nlogn) ...................................................................................... 150 搜索....................................................................................................................................... 151 1、Dancing Links ........................................................................................................... 151 其他....................................................................................................................................... 156 1、高精度 ..................................................................................................................... 156 2、完全高精度 ............................................................................................................. 158 3、strtok 和 sscanf 结合输入 ...................................................................................... 163 4、解决爆栈，手动加栈 ............................................................................................. 163 5、STL ........................................................................................................................... 163 6、输入输出外挂 ......................................................................................................... 165 7、莫队算法 ................................................................................................................. 166 8、VIM 配置 ................................................................................................................. 172 字符串处理 1、KMP 算法 while(-1!=j && x[i]!=x[j])j=next[j]; next[++i]=++j; int i,j; j=next[0]=-1; i=0; while(i

上海大学 ACM 模板 by kuangbin } while(-1!=j && y[i]!=x[j])j=next[j]; i++;j++; if(j>=m) { } ans++; j=next[j]; while(-1!=j && x[i]!=x[j])j=kmpNext[j]; if(x[++i]==x[++j])kmpNext[i]=kmpNext[j]; else kmpNext[i]=j; int i,j; int ans=0; //preKMP(x,m,next); kmp_pre(x,m,next); i=j=0; while(i #include #include #include #include using namespace std; const int MAXN=100010; const int MAXM=25010; int a[MAXN]; int b[MAXN]; int n,m,s; int as[MAXN][30]; int bs[MAXM][30]; void init() { for(int i=0;i

上海大学 ACM 模板 by kuangbin for(int j=1;j<=25;j++)as[i][j]=0; for(int j=1;j<=25;j++)as[i][j]=as[i-1][j]; for(int j=1;j<=25;j++)bs[i][j]=0; for(int j=1;j<=25;j++)bs[i][j]=bs[i-1][j]; if(i==0) { } else { } as[i][a[i]]++; } for(int i=0;ians; void kmp() { int i,j; j=next[0]=-1; i=0; while(i0)t11+=bs[i][k]-bs[i-j-1][k]; else t11+=bs[i][k]; int t11=0,t12=0,t21=0,t22=0; for(int k=1;k0)t12=bs[i][b[i]]-bs[i-j-1][b[i]]; else t12=bs[i][b[i]]; for(int k=1;k

上海大学 ACM 模板 by kuangbin t21+=bs[j][k]; if(i-j>0)t11+=as[i][k]-as[i-j-1][k]; else t11+=as[i][k]; int t11=0,t12=0,t21=0,t22=0; for(int k=1;k0)t12=as[i][a[i]]-as[i-j-1][a[i]]; else t12=as[i][a[i]]; for(int k=1;k=m) { } ans.push_back(i-m+1); j=next[j]; i=j=0; while(i

上海大学 ACM 模板 by kuangbin next[0]=m; int j=0; while(j+1

上海大学 ACM 模板 by kuangbin Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1; while(Ma[i+Mp[i]]==Ma[i-Mp[i]])Mp[i]++; if(i+Mp[i]>mx) { mx=i+Mp[i]; id=i; } Ma[l++]=s[i]; Ma[l++]='#'; Ma[l++]='#'; for(int i=0;i #include #include #include #include using namespace std; struct Trie { int next[500010][26],fail[500010],end[500010]; 7 / 173 ACM 模板 kuangbin

上海大学 ACM 模板 by kuangbin int len = strlen(buf); int now = root; for(int i = 0;i < len;i++) { } end[now]++; if(next[now][buf[i]-'a'] == -1) now = next[now][buf[i]-'a']; next[now][buf[i]-'a'] = newnode(); next[L][i] = -1; for(int i = 0;i < 26;i++) end[L++] = 0; return L-1; int root,L; int newnode() { } void init() { L = 0; root = newnode(); } void insert(char buf[]) { } void build() { } int query(char buf[]) { queueQ; fail[root] = root; for(int i = 0;i < 26;i++) while( !Q.empty() ) { } int len = strlen(buf); int now = root; int res = 0; for(int i = 0;i < len;i++) { int now = Q.front(); Q.pop(); for(int i = 0;i < 26;i++) if(next[now][i] == -1) else { } next[root][i] = root; if(next[root][i] == -1) else { } fail[next[root][i]] = root; Q.push(next[root][i]); next[now][i] = next[fail[now]][i]; fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); 8 / 173 ACM 模板 kuangbin

分享到：

赞收藏

资料库

（kuangbin）邝斌的ACM模板.pdf

相关推荐

课程资源

热门标签

最新资料