山东的大学ACM模板.docx

山东的大学ACM模板.docx字符串处理 31、 KMP算法 32、 扩展KMP 63、 Manacher最长回文子串 74、 AC自动机 85、 后纟矽组 106、 后缀自动机 137、 字符串HASH 14数学 161、 素数 162、 素数筛选和合数分解 183、 扩展欧几里得算法(求ax+by=gcd的解以及逆元素) 194、 求逆元 195、 模线性方程组 206、 随机素数测溺口大数分解(POJ1811) 207、 欧拉函数 238、 高斯消元(浮点数) 249、 FFT 2510、 高斯消元法求方程组的解 28llx整数拆分 3212、 求AAB的约数之和对MOD取模 3313、 莫比乌斯反演 3414、 Baby-StepGiant-Step 3615、 自适应simpson积分 37相关公式 37数据结构 391、 划分树 392、 RMQ 403、 树链剖分 424、 伸展树(splaytree) 475、 动态树 516、 主席树 557、 Treap 64图论 691、 圜豆路 692、 最小对 723、 次小对 744、 有向图的强连通分量 755、 图的割点、桥和双连通分支的基本概念 776、 割点与桥 787、 边双连通分支 818、 点双连通分支 839、 最小树形图 8510、 二分图匹配 8711、 生成树计数 9111、 二分图多重匹配 9412、 KM算法(二分图最大权匹配) 9413、 最大流 9614、 最小费用最大流 10015、 2-SAT 10216、 曼哈顿最小生成树 10517、 一般图匹配带花树 10718、 LCA 11019、 欧扌靖 115计算几何 1211、 基本函数 1212、 凸包 1263、 平面最近点对(HDU1007) 1274、 旋转卡壳 1285、 半平面交 1336、 三点求圆心坐标(三角形外心) 1367、 求两圆相交的面积 1368、 Pick公式 137动态规划 1371、最长上序歹I」O(nlogn) 137搜索 138ls DancingLinks 138其他 1421、 高精度 1422、 完全高精度 1443、 strtok和sscanf结合输入 1494、 解决爆栈,手动加栈 1495、 STL 1496、 输入输出夕卜挂 1517、 莫队算法 1518、 VIM配置 156字符串处理1、KMP算法/*next[]的含义:x[i-next[i]・・・i-1]=x[0・・・next[i]・1]next[i]为满足x[i-z...i-l]=x[O...z-l]的最大z值(就是x的自身匹配)*/voidkmp_pre(charx[],intm,intnext[]){inti,j;j=next[0]=-l;i=0;while(i<m){while(-1!=j&&x[i]!=x[j])j=next[j];next[++i]=++j;}}/*kmpNext[]的意思:next1[i]=next[next[・・・[next[i]]]](肓至[Inext1[i]<0或者x[next*[i]]!=x[i])*这样的预处理可以快_些*/voidpreKMP(charx[],intintkmpNext[]);j=kmpNext[0]=-l;i=0;while(i<m)while(-1!=j&&x[i]1=x[j])j=kmpNext[j];if(x[++i]==x[++j])kmpNext[i]=kmpNext[j];kmpNext[i]=j;}}/**返回X在y中出现的次数,可以重叠*/intnext[10010];intKMP_Count(charx[],intmzchary[],intn){//x是模式串,y是主串inti#j;intans=0;//preKMP(x,mznext);kmp_pre(xzmznext);i=j=0;while(i<n){while(-1!=j&&y[i]!=x[j])j=next[j];i++;j++;if(j>=m){ans++; j=next[j];}}returnans;}经典题目:POJ3167/**POJ3167CowPatterns*模式串可以浮动的模式匹配问题*给出模式串的相对大小,需要找出模式串匹配次数和位置*比如说模式串:1,4,4,2,3,1而主串:5,6,2,10,*那么2,10,10,7,3,2就是匹配的★*统计比当前数小,和于当前数相等的,然后进行彌*/#include<iostream>#include<stdio・h>#include<string・h>#include<algorithm>#include<vector>usingnamespacestd;constintMAXN=100010;cons