邝斌ACM模板2015最新版下载.pdf

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

440a3544-f45b-4197-b878-dd123295f6d6.pdf-第1页.png

第1页 / 共173页

440a3544-f45b-4197-b878-dd123295f6d6.pdf-第2页.png

第2页 / 共173页

440a3544-f45b-4197-b878-dd123295f6d6.pdf-第3页.png

第3页 / 共173页

440a3544-f45b-4197-b878-dd123295f6d6.pdf-第4页.png

第4页 / 共173页

440a3544-f45b-4197-b878-dd123295f6d6.pdf-第5页.png

第5页 / 共173页

440a3544-f45b-4197-b878-dd123295f6d6.pdf-第6页.png

第6页 / 共173页

440a3544-f45b-4197-b878-dd123295f6d6.pdf-第7页.png

第7页 / 共173页

440a3544-f45b-4197-b878-dd123295f6d6.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 算法 /* * next[]的含义：x[i-next[i]...i-1]=x[0...next[i]-1] * next[i]为满足x[i-z...i-1]=x[0...z-1]的最大z值（就是x的自身匹配） */ void kmp_pre(char x[],int m,int next[]) { } int i,j; j=next[0]=-1; i=0; while(i

上海大学 ACM 模板 by kuangbin while(-1!=j && x[i]!=x[j])j=kmpNext[j]; if(x[++i]==x[++j])kmpNext[i]=kmpNext[j]; else kmpNext[i]=j; } } /* * 返回x在y中出现的次数，可以重叠 */ int next[10010]; int KMP_Count(char x[],int m,char y[],int n) {//x是模式串，y是主串 int i,j; int ans=0; //preKMP(x,m,next); kmp_pre(x,m,next); i=j=0; while(i=m) { } ans++; j=next[j]; return ans; } 经典题目：POJ 3167 /* * POJ 3167 Cow Patterns * 模式串可以浮动的模式匹配问题 * 给出模式串的相对大小，需要找出模式串匹配次数和位置 * 比如说模式串：1，4，4，2，3，1 而主串：5,6,2,10,10,7,3,2,9 * 那么2,10,10,7,3,2就是匹配的 * * 统计比当前数小，和于当前数相等的，然后进行kmp */ #include #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 if(i==0) { } for(int j=1;j<=25;j++)as[i][j]=0; else { } for(int j=1;j<=25;j++)as[i][j]=as[i-1][j]; as[i][a[i]]++; } for(int i=0;i0)t11+=bs[i][k]-bs[i-j-1][k]; else t11+=bs[i][k]; if(i-j>0)t12=bs[i][b[i]]-bs[i-j-1][b[i]]; else t12=bs[i][b[i]]; for(int k=1;kans; void kmp() ans.clear(); int i,j; kmp_pre(); { 4 / 173 ACM 模板 kuangbin

上海大学 ACM 模板 by kuangbin i=j=0; while(i0)t11+=as[i][k]-as[i-j-1][k]; else t11+=as[i][k]; if(i-j>0)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]; else j=next[j]; } } int main() { while(scanf("%d%d%d",&n,&m,&s)==3) { for(int i=0;i

上海大学 ACM 模板 by kuangbin //extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀 void pre_EKMP(char x[],int m,int next[]) { } next[0]=m; int j=0; while(j+1

上海大学 ACM 模板 by kuangbin Ma[l++]='#'; for(int i=0;ii?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; } /* * abaaba * i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 * Ma[i]: $ # a # b # a # a $ b # a # * Mp[i]: 1 1 2 1 4 1 2 7 2 1 4 1 2 1 */ char s[MAXN]; int main() { } while(scanf("%s",s)==1) { } int len=strlen(s); Manacher(s,len); int ans=0; for(int i=0;i<2*len+2;i++) ans=max(ans,Mp[i]-1); printf("%d\n",ans); return 0; 4、AC 自动机 //====================== // HDU 2222 // 求目标串中出现了几个模式串 //==================== #include #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 root,L; int newnode() { } for(int i = 0;i < 26;i++) next[L][i] = -1; end[L++] = 0; return L-1; void init() { } L = 0; root = newnode(); void insert(char buf[]) { } int len = strlen(buf); int now = root; for(int i = 0;i < len;i++) { } if(next[now][buf[i]-'a'] == -1) next[now][buf[i]-'a'] = newnode(); now = next[now][buf[i]-'a']; end[now]++; void build() { queueQ; fail[root] = root; for(int i = 0;i < 26;i++) if(next[root][i] == -1) next[root][i] = root; else { } fail[next[root][i]] = root; Q.push(next[root][i]); while( !Q.empty() ) { } int now = Q.front(); Q.pop(); for(int i = 0;i < 26;i++) if(next[now][i] == -1) next[now][i] = next[fail[now]][i]; else { } fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } int query(char buf[]) { int len = strlen(buf); int now = root; int res = 0; for(int i = 0;i < len;i++) { 8 / 173 ACM 模板 kuangbin

分享到：

赞收藏

资料库

邝斌ACM模板2015最新版下载.pdf

相关推荐

后端

热门标签

最新资料