《代码仓库培训资料》由会员分享，可在线阅读，更多相关《代码仓库培训资料（33页珍藏版）》请在金锄头文库上搜索。
1、33代码仓库代码仓库目录：01.【数学方法】矩阵快速幂02.【数学方法】高斯消元（nave版）03.【数学方法】高斯消元（mid版）04.【字符串啊】Manacher算法（回文串）05.【字符串啊】KMP（字符串匹配）06.【数据结构】线段树（ZKW单点修改）07.【数据结构】线段树（RMQ）08.【数据结构】线段树（区间加+赋值）09.【数据结构】Splay树（未完全测试）/！10.【数据结构】AVL树（平衡树）11.【图论图论】最小生成树（prim）12.【图论图论】次小生成树13.【图论图论】最大流（Dinic）14.【图论图论】LCA+最大生成树（truck）15.【动态规划】背包01
2、，多重，完全矩阵模板#include #include#includeusing namespace std;typedef long long ll;const int P = 9973;const int N=13;ll n,m;struct matrix ll aNN; int row,col; matrix():row(N),col(N)memset(a,0,sizeof(a);/？ matrix(int x,int y):row(x),col(y)memset(a,0,sizeof(a); ll* operator (int x)return ax; matrix operator
3、* (matrix x) matrix tmp ; for (int i=0;i=n+1;i+) for (int j=0;j=n+1;j+) tmpij=0; for (int k=0;k=n+1;k+) tmpij=(tmpij+aik*xkj)%P; return tmp; void operator *= (matrix x)*this = *this * x; matrix operator (ll x) matrix ret; for (int i=0;i=1,tmp*=tmp)if(x&1)ret *=tmp; return ret; void print() for (int
4、i=0;i=n+1;i+) for (int j=0;j=n+1;j+) printf(%d ,aij); puts(); ;高斯消元，判断有无解的#include#include#include#include#includeusing namespace std;typedef long long LL;const double EPS=1e-6;const int N=55;struct matrix int aNN; int row,col; matrix():row(N),col(N)memset(a,0,sizeof(a); matrix(int x,int y):row(x),c
5、ol(y) memset(a,0,sizeof(a); int* operator (int x)return ax; void print() for (int i=0;irow;i+) for (int j=0;jcol;j+) printf(%d ,aij); puts(); puts(); ;int Gauss(matrix a,int m,int n) int x_cnt = 0; int col, k; /col为列号,k为行号 for (k=0,col=0;km&coln; +k, +col) int r = k; /r为第col列的一个1 for (int i=k;im;+i)
6、 if (aicol)r=i; if (!arcol) k-; continue; if (r!=k)for (int i=col;i=n;+i) swap( ari, aki); for (int i=k+1;im; +i)if (aicol)/消元 for (int j=col;j=n;+j)aij=akj; for (int i=k;im;+i) if (ain)return -1; if (k=n)return n-k; /返回自由元个数高斯消元，求出一组解的#include #include #include #include #include using namespace std
7、;const int N = 1010;const double EPS=1e-7;int m,n;double aNN,xN;int Gauss(int m,int n) int col=0, k=0;/col为列号,k为行号 for (;km&coln;+k,+col) int r = k; for (int i=k+1;ifabs(arcol)r=i; if (fabs(arcol)EPS)k-;continue;/列全为0 if (r!=k)for(int i=col;i=n;+i) swap(aki,ari); for (int i=k+1;iEPS) double t = aico
8、l/akcol; for (int j=col;j=n;j+)aij-=akj*t; aicol = 0; for(int i=k ;iEPS) return -1; if (k =0; i-)/回带求解 double temp = ain; for (int j=i+1; jn; +j) temp -= xj * aij; xi = (temp / aii); return 0;Manacher算法#include#include#include#include#includeusing namespace std;const int N=;/20W/在o(n)时间内算出以每个点为中心的最大
9、回文串长度int Manacher(string st) int len=st.size(); int *p=new intlen+1; memset(p,0,sizeof(p); int mx=0,id=0; for (int i=1;ii)pi=min(p2*id-i,mx-i); else pi=1; while (sti+pi=sti-pi)pi+; if (i+pimx)mx=i+pi;id=i; int ma=0; for(int i=1;ilen;i+)ma=max(ma,pi); delete(p); return ma-1;int main() /freopen(fuck.i
10、n,r,stdin); char stN; while (scanf(%s,st) string st0=$#; for (int i=0;sti!=0;i+) st0+=sti; st0+=#; printf(%dn,Manacher(st0); return 0;KMP 字符串匹配#include#includeusing namespace std;typedef long long ll;const int N=;const int P=;char aN,bN;bool matN;int nextN;ll fN;void getNext(int m) int i=0,j=-1; next0=-1; while (im) if (j=-1|bi=bj) if (b+i!=b+j
