ACM巨全模板 .pdf

所需积分/C币:44 2019-10-07 11:51:34 8.42MB PDF
125
收藏 收藏
举报

看大小就知道很全啦 查看地址 https://blog.csdn.net/qq_43333395/article/details/98508424 目录: 数据结构: 1.RMQ (区间最值,区间出现最大次数,求区间gcd) 2.二维RMQ求区间最大值 (二维区间极值) 3.线段树模板(模板为区间加法) (线段树染色) (区间最小值) 4.线性基 (求异或第k大) 5.主席树(静态求区间第k小) (区间中小于k的数量和小于k的总和) (区间中第一个大于或等于k的值) 6.权值线段树 (求逆序对) 7.动态主席树 (主席树+树状数组) (区间第k大带修改) 8.树上启发式合并 (查询子树的优化) 9,树状数组模板 (求区间异或和,求逆序对) 扩展 10.区间不重复数字的和 (树状数组) 11.求k维空间中离所给点最近的m个点,并按顺序输出(KD树) 12.LCA (两个节点的公共父节点) 动态规划: 1.LIS (最长上升子序列) 2.有依赖的背包 (附属关系) 3.最长公共子序列(LCS) 4.树形DP 5.状压DP-斯坦纳树 6.背包 7.dp[i]=min(dp[i+1]…dp[i+k]),multset 博弈: 1.NIM博弈 (n堆每次最少取一个) 2.威佐夫博弈(两堆每次取至少一个或一起取一样的) 3.约瑟夫环 4.斐波那契博弈 (取的数依赖于对手刚才取的数) 5.sg函数 数论: 1.数论 素数检验:普通素数判别 线性筛 二次筛法求素数 米勒拉宾素数检验 2.拉格朗日乘子法(求有等式约束条件的极值) 3.裂项(多项式分子分母拆分) 4.扩展欧几里得 (ax+by=c) 5.勾股数 (直角三角形三边长) 6.斯特林公式 (n越大越准确,求n!) 7.牛顿迭代法 (求一元多次方程一个解) 8.同余定理 (a≡b(mod m)) 9.线性求所有逆元的方法求 (1~p modp的逆元) 10.中国剩余定理(n个同余方程x≡a1(modp1)) 11.二次剩余((ax+k)2≡n(modp)(ax+k)^2≡n(mod p)(ax+k) 2 ≡n(modp)) 12.十进制矩阵快速幂(n很大很大的时候) 13.欧拉函数 14.费马小定理 15.二阶常系数递推关系求解方法 (a_n=p*a_{n-1}+q*a_{n-2}) 16.高斯消元 17.矩阵快速幂 18.分解质因数 19.线性递推式BM(杜教) 20.线性一次方程组解的情况 21.求解行列式的逆矩阵,伴随矩阵,矩阵不全随机数不全 组合数学: 1.循环排列 (与环有关的排列组合) 计算几何: 1.三角形 (求面积)) 2.多边形 3.三点求圆心和半径 4.扫描线 (矩形覆盖求面积) (矩形覆盖求周长) 5.凸包 (平面上最远点对) 6.求凸多边形的直径 7.求凸多边形的宽度 8.求凸多边形的最小面积外接矩形 9.半平面交 图论: 基础:前向星 1.最短路(优先队列dijkstra) 2.判断环(tarjan算法) 3.最小生成树(Kruskal 模板) 4.最小生成树(Prim) 5.Dicnic最大流(最小割) 6.无向图最小环(floyd) 7.floyd算法的动态规划(通过部分指定边的最短路) 8.图中找出两点间的最长距离 9.最短路 (spfa) 10.第k短路 (spfa+A*) 11.回文树模板 12.拓扑排序 (模板) 13.次小生成树 14.最小树形图(有向最小生成树) 15.并查集 (普通并查集,带权并查集,) 16.求两个节点的最近公共祖先 (LCA) 17.限制顶点度数的MST(k度限制生成树) 18.多源最短路(spfa,floyd) 19.最短路 (输出字典序最小) 20.最长路 图论题目简述 字符串: 1.字典树(多个字符串的前缀) 2.KMP(关键字搜索) 3.EXKMP(找到S中所有P的匹配) 4.马拉车(最长回文串) 5.寻找两个字符串的最长前后缀(KMP) 6.hash(进制hash,无错hash,多重hash,双hash) 7.后缀数组 (按字典序排字符串后缀) 8.前缀循环节(KMP的fail函数) 9.AC自动机 (n个kmp) 10.后缀自动机 小技巧: 1.关于int,double强转为string 2.输入输出挂 3.低精度加减乘除 4.一些组合数学公式 5.二维坐标的离散化 6.消除向下取整的方法 7.一些常用的数据结构 (STL) 8.Devc++的使用技巧 9.封装好的一维离散化 10.Ubuntu对拍程序 11.常数 12.Codeblocks使用技巧 13.java大数 叮嘱 共173页
计算几何: 1三角形(求面积) 2多边形 3三点求圆心和半径 4扫描线(矩形覆盖求面积)(矩形覆盖求周长) 5凸包(平面上最远点对) 6求凸多边形的直径 7求凸多边形的宽度 8求凸多边形的最小面积外接矩形 9半平面交 图论: 基础:前向星 1最短路(优先队列 dijkstra) 2判断环 tarjan算法) 3最小生成树( Kruskal模板) 4最小生成树(Prim) 5 Picnic最大流(最小割) 6无向图最小环(foyd) 7foyd算法的动态规划(通过部分指定边的最短路) 8图中找出两点间的最长距离 9最短路(spfa) 10.第k短路(spfa+A*) 1.回文树模板 12.拓扑排序(模板) 13次小生成树 14最小树形图(有向最小生成树 15并查集(普通并查集带权并查集) 16求两个节点的最近公共祖先(LCA) 17限制顶点度数的MST(k度限制生成树) 18.多源最短路spfa, floyd) 19最短路(输出字典序最小) 20最长路 图论题目简述 字符串 1字典树(多个字符串的前缀) 2KMP(关键字搜索) 3 EXKMP找到S中所有P的匹配) 4马拉车(最长回文串) 5寻找两个字符串的最长前后缀(KMP) 6hash(进制hash,无错hash,多重hash,双hash) 7后缀数组(按字典序排字符串后缀) 8前缀循环节(KMP的fi函数) 9AC自动机(n个kmp) 10.后缀自动机 小技巧 1关于 int double强转为 string 2输入输出挂 3低精度加减乘除 4一些组合数学公式 5二维坐标的离散化 6消除向下取整的方法 7.一些常用的数据结构(STL) 8Dev++的使用技巧 9封装好的一维离散化 10. Ubuntu对拍程序 11.常数 12 Codeblocks使用技巧 13ava大数 数据结构 1RMQ区间最值) RMQ算法,是一个快速求区间最值的离线算法,预处理时间复杂度O(nog(m),查询O(1),所以是 一个很快速的算法,当然这个问题用线段树同样能够解决。 求区间的最大值和最小值! #include <bits/stdc++.h> using namespace std; const int maxn=100117 int n, query; int num[ maxn]; int F Min[ maxn][20],F Max[ maxn][20]; void initof for(int i=l;i<=n; i++)t F Min[i][0]=F Max[i][0]=num[i]; for(inti=1;(1<i)<=n;i+-){//按区间长度递增顺序递推 for(intj=1;j+(1<i)-1<=n;j+-){//区间起点 F Maxj[i]=max(F_ Max[j1-1,F Max[j+(1<<(1-1))l-1]) FMin[j[i]=min(FMin[j][-1],FMin[j+(1<<(1-1)][1-1]) int Query max(int l,int r)f int k=(int)(log2( double(r-1+1))): return max (FMax[1][k],FMax[r-(1<k)+1][k]); int Query min (int l,int r)f int k=(int)(log2( double (r-1+1))); return min(F Min[,f Min[r-(1<<k)+lkl; int main(i int a, b scanf(" %d %d",&n, &query for (int i=l; i=n; i++) ("%d",&num[i]) init(; le(query--)t scanf("‰d%",&a,&b); printf("区问‰到%d的最大值为:‰dn",ab, Query_max(a,b)); printf("区间‰到%的最小值为:‰Ⅶn",a,b, Query min(a,b)); printf("区间‰到%d的最大值和最小值只差为:‰dn",a,b, Query_max(a,b)- ρ uery min(a,b)) return a 2、求区间内出现次数最多的数字出现的次数! 对上升序列如:1122233455.统计区间出现次数最多数个数 我们可以构造一个b数组 if (ai==ali-ln bi=bi-1+1 else b[]=1; 这样对上述例子,b数组有1212312112 那么对询问区间[,如果在数与数交界处,那么直接查询l,r区间最大值。 否则要知道与a]相同延伸到end,那么这个区间大小end4+1,与mq(end+l,r)取最大值就是答案。 #include <bits/stdc++.h> using namespace std; const int maxn=100017 int num[ maxn],f[maxn], MAX[ maxn][20]; int n int max(int a, int b)f return a>ba: b: int rmq_ max (int l, int r)f if(l>r return 0; int k=log2((double)(r-1+1)); return max(MAX[l][kl, MAXIr-(1<<k+1]lkl; void initof for (int i=;i<=n; i++)f MAX[i][]=千[i]; int k=log2((double)(n+1)) for(int i=1; i(=k; i++)f for (int j=1;j+(1<<1)-1<=n: j++)0 MAX[][i]=max(MAX[j][i-1],MAX[j+(1<(i-1))][i-1]); } int mainO[ int a, b, q thile( scanf( %d",&n)&&n f scanf("%d",&q) for (int i=l; i<=n; i++t scanf (" %d",&num[i1); sort(num+1, num+n+1) for (int i=1; i<=n; i++t if(i==1){ continue; if(num[i==num[i-1]t f[i]=f[i-1]+1 false f[i]= it( for (int i=l; i<=g: i++)i scanf( %d%d",a, &b); int t=a: While(t<=b&&num[t]==num[t-1])t int cnt=rmq max(t, b); int ans=max(t-a, cnt) printf( %d\n",ans); return 0; RMQ求区间gcd r[1,r} ged (sa I,a{1+1},…ar$),问r[1,r的值和有多少对(L,R使得L,R]=r[1,r]l #include<bits/stdc++h> using namespace std; #define ll long long int dp[101][32] inta[1010] int n, m, g,Jj int gcd(int a, int b)[ return b?gcd (b, a%b): a; void rmq _ initot for(int j= 1;j<=n;j++)dp[jlo]-aljlj for(inti=1:(1<<i)<=n;i++){ for(intj=1;j+(1<i)-1<=n;j+){ dp[j][i]=gcd(dp[j][i-1],dp[j+(1<<(i-1)][i-1]); int rmq_qui(int1,intr)[//查询的即是区间gcd int k=(int)log2(double(r-1+1)); return gcd(dpll][k], dp[r-(1<<k)+1][k]) map<int, longlong>mp; void setTable(t mp. clear( for(int i=l; i<=n; i++)t g=dp[i][0],j=i; While(j<=n)f int l=j,r=n; While(l<r)i int mid=(l+r+1)>>1 if(rmg qui(i, mid)==g)l=mid else r=mid-1 mp[g]+=1-j+1;//相当于二分枚举相加 g= rmq qui(主,j); int main(i int tl,r int cas=1: scan("Ⅺd",&t); thile(t--) printf("Case #%d: \n",cas++); scanf( %d",&n); for (int i-1; i<=n; i++) scanf("%",&a[i]); rma_inito) scanf( %d",&m); for(int i=0; i<m; i++)i scanf("%d %d",&l,&r); int g=rmq qui(l,r) printf( %d %lld\n",g, mplgl; 2二维RMQ求区间最大值) 建表复杂度 O(nmlog(n)og(m),查询复杂1) 还有种做法是把每行当作维区问求最大建表m*og(m),查询O(n) #include<bits/stdc++ h> using namespace std; intn,m,a[490][489] int dp[469][48][28][28] int r1, cl, r2, c2, k1, k2,ans int main(f scan+("‰d%d",&n,&m);//二维区间的范围 for(int i=l; i<=n; i++0 for (int j=1: j<=m;3++)0 scanf("%d",&a[i][j]) dp[i]j[0][0]=a[i][j;//初始化 int ul=0,u2=0 hile((1<<(u1+1))<=n)u1+ while((1<<(u2+1))<=m)u2++ for (int i=l; i<=n; i++)i for(int k=1; k<=u2; k++) for(intj=1;j+(1<<(k-1)<=m;j++){//列建立RNQ dp[i][j][e][k]=max(dp[i][j[e][k-1],dp[i][j+(1<<(k-1))][e][k-1]); for (int i=l; 1<=m; i++ for (int k=l; k<=ul; k++)t for(intj=1;j+(1<(k-1))<=n;j++){//行建立RMQ dp[j][i][k][]=max(dp[j[主][k-1][8],dp[j+(1<<(k-1))][i][k-1][e]); for (int i=1; i<=u1; i++)0 for (int j=l; j<=u2: j++) for(intk=1;k+(1<<(1-1))<=n;k++){ for(intp=1;p+(1<(j-1))<=m;p++){//行列合并 dp[k][pJ[i][j]=max(dp[k][p][i][j],dp[k][p][i-1][j-1]) dp[k][p][i[j]=max(dp[k][p][i][j],dp[k+(1<<(i-1)][p][i-1][j-1]) dp[k][p]J[i][j=max(dp[k][p][i][j,dp[k][p+(1<<(-1)][i-1][-1]) dp[k][pJ[i][j]=max(dp[k][p][i][j],dp[k+(1<<(i-1))][p+(1<(-1))] [i-1][j-1]); scanf("%d",&p); while(p--)t scanf("%%d%d%d",&r1,&c1,&r2,&c2);//矩形的两个对角线顶点 k1=k2=8 while((1<<(k1+1))<=(r2-r1+1)k1++;//等于int(log2(r2-1+1) while((1<<(k2+1))<=(c2-c1+1)k2+;/等于int(10g2(c2-c1+1)) ans=0 //下面相当于分成四块矩形 ans=max(ans,dp[r1][c1][k1][k2])://从(r1,c1)开始长度为2~k1和2^k2 ans=max(ans,dp[r2-(1<k1)+1][c2-(1<<k2)+1]k1][k2]);//从(r2-2^k1,c2-2~k2)开始长 度为2k1和2~k2 ans=max(ans,dp[2-(1<k1)+1][c1[k1][k2]);//从(r2-2^k1,c1)开始长度为2^k1和2~k2 anS=max(ans,dp[r1][c2-(1<k2)+1][k1][k2]);/从(r1,c2-2~k2)开始长度为2~k1和2~k2 printf (" %d\",ans); return 0; 线段树 a)模板为区间加法 include <bits/stdc++h> using namespace std typedef long long ll; const int maxn =1000005 struct tree f int treelmaxn*4];//线段树 [maxn*4];//延退标记 void init(){//初始化 memset(tree, 0, sizeof (tree)) memset(lz,0, sizeof(lz)) //创建线段树 void build(int root, int l, int r)i if(1==r){ scanf("%d",&tree [root]) return int mid =(1 +r)>> 1 build(root < 1, 1, mid); build(root < 1 1, mid + 1, r); tree[root]=tree[root<<1]+tree[root<<1|1];//可取模 return; //单点更新,n为更新值, index为更新点,1r为更新范围 void update(int root, int n, int index, int l, int r)t if (1 ) tree[root]=n;//更新方式,可以自由改动 int mid =(l+r)>>1 //push_down(rot,mid-1+1,r-mid);若既有点更新又有区间更新,需要这句话 if (index <= mid) date(root < 1, n, index, l, mid); else update(root < 1 1,n, index, mid +1, r) tree[root]=tree[root<<1]+ tree[root<11];//可取模 oid push_ down (int root, int l intr){//懒标记下传,若需取模,懒标记均可取模 if (lz[root])i d=(1+r) lz[root < 1] += lz[root] 1: tree [root < 1+=1LL *(mid lz[root]j tree[root < 11]+= 1LL *(r-mid rooti t]=8 /区间更新,1r为更新范围,LR为线段树范围,add为更新值 void update range(int root, int l, int r, int L, int R, int add)i push_ down(root,L,R);//应敚在最开始,否则会出借 if(1<=L&&r>=R){ lz[root]+= ILL* add tree[root]+=1Ll*(R-L+1)*ad;//更新方式 return int mid =(L +r)>>1 if (mid >=1)update range (root < 1, l,r, L, mid, add); if (mid r) update range(root < 1 1, 1,r, mid +1,R, add); tree[root]=tree[root<1]+tre[root<<11];/河可取模 /区间查找 1l query range(int root, int L, int R, int l, int r)t push down(root,L,R);/应放在最开始,否则会出错 if (l<=l&&r >=r ret int mid =(L +R)>>1 11 su if (mid >=1) sum + qu nge( root<1,L,mid,1,r);//可取模 if (mid r) sum+= query range(root<1|1,mid+1,R,1,r);/可取模 return sum TREE nt mai int n: N // build(int root, int l, int r) /建树,数组在树中输入,root=1,1r为线段树范围 trees, build(1, 1, N) / update range(int root, int l,int r,int L, int R,int add) //区间更新root为1,1r为更新范围,LR为线段树范围,add为更新值 int x,y, k trees. update range(l, x, y, 1, N,k); // update(int n,int index, int l, int r, int root) /单点更新,n为更新值, index为更新点,1r为线段树范围 int i, k trees. update(l,k, i, 1, N); / query range(int root, int L, int R,int l, int r) //区间查找root为1,1为更新范围,LR为线段树范围 int x, y trees. query range(1, 1,N, x, y) return e b)线段树染色 在一条线上画一些彩色的部分,一些先前画的部分可能会被后面的部分覆盖。 下面代码可以直接生成涂色后的颜色分布状况。(可以将每个点的颜色输出出来) #include <cstdio> include <cstring> #include <algorithm> typedef long long ll const int maxn=1e5+10: using namespace std int tree[maxn<2];/对节点染色 void pushDown( int root){//下传,线段树维护颜色 if(tree[root]!=-1)[ tree[root]=-1 // update(1,1,8098,a+1,b,k); void update(int root, int L,int R, int l, int r, int k)i if(1<=L&&r>=R){ [root =k turn Pushdot int mid=(L+R)>>1 if(l<=mid) update(root<<1, L, mid, l,r, k) if(r>mid) date(root<<1 1, mid1, R,I,r, k); int red[maxn];//存储i节点的颜色 int top=0 void query (int root, int l,int r)i if(1==r){ rec[tap++]=tree[root];/记录节点的颜色

...展开详情
试读 127P ACM巨全模板 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • GitHub

  • 分享学徒

关注 私信
上传资源赚钱or赚积分
最新推荐
ACM巨全模板 .pdf 44积分/C币 立即下载
1/127
ACM巨全模板 .pdf第1页
ACM巨全模板 .pdf第2页
ACM巨全模板 .pdf第3页
ACM巨全模板 .pdf第4页
ACM巨全模板 .pdf第5页
ACM巨全模板 .pdf第6页
ACM巨全模板 .pdf第7页
ACM巨全模板 .pdf第8页
ACM巨全模板 .pdf第9页
ACM巨全模板 .pdf第10页
ACM巨全模板 .pdf第11页
ACM巨全模板 .pdf第12页
ACM巨全模板 .pdf第13页
ACM巨全模板 .pdf第14页
ACM巨全模板 .pdf第15页
ACM巨全模板 .pdf第16页
ACM巨全模板 .pdf第17页
ACM巨全模板 .pdf第18页
ACM巨全模板 .pdf第19页
ACM巨全模板 .pdf第20页

试读结束, 可继续阅读

44积分/C币 立即下载 >