代码仓库

1

代码仓库

代码仓库 目录：

01.【数学方法】矩阵快速幂

02.【数学方法】高斯消元（na?ve版） 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 #include usingnamespace std; typedeflonglong ll; constint P =9973; constint N=13; ll n,m;

struct matrix{ ll a[N][N]; 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 a[x];} matrix operator*(matrix x){ matrix tmp ; for(int i=0;i<=n+1;i++) for(int j=0;j<=n+1;j++){ tmp[i][j]=0; for(int k=0;k<=n+1;k++)

tmp[i][j]=(tmp[i][j]+a[i][k]*x[k][j])%P; }

return tmp; }

voidoperator*=(matrix x){*this=*this* x;} matrix operator^(ll x){ matrix ret;

for(int i=0;i<=n+1;i++)ret[i][i]=1; matrix tmp =*this;

for(;x;x>>=1,tmp*=tmp){if(x&1)ret *=tmp;} return ret; }

void print(){

for(int i=0;i<=n+1;i++){ for(int j=0;j<=n+1;j++)

printf(\,a[i][j]); puts(\); }

3

代码仓库

} }; 高斯消元，判断有无解的 #include #include #include #include #include usingnamespace std; typedeflonglong LL; constdouble EPS=1e-6; constint N=55;

struct matrix{ int a[N][N]; 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)); }

int*operator[](int x){return a[x];} void print(){

for(int i=0;i

printf(\,a[i][j]); puts(\); }

puts(\); } };

int Gauss(matrix a,int m,int n){ int x_cnt =0;

int col, k;//col为列号,k为行号

for(k=0,col=0;k

for(int i=k;i

4

代码仓库

for(int i=k+1;i

高斯消元，求出一组解的

#include #include #include #include #include usingnamespace std; constint N =1010; constdouble EPS=1e-7; int m,n;

double a[N][N],x[N];

int Gauss(int m,int n){

int col=0, k=0;//col为列号,k为行号 for(;k

for(int i=k+1;i

if(fabs(a[i][col])>fabs(a[r][col]))r=i;

if(fabs(a[r][col])EPS){

double t = a[i][col]/a[k][col];

for(int j=col;j<=n;j++)a[i][j]-=a[k][j]*t; a[i][col]=0; } }

for(int i=k ;iEPS)return-1; if(k < n)return n - k;//自由元个数 for(int i =n-1; i>=0; i--){//回带求解

5

代码仓库

double temp = a[i][n]; for(int j=i+1; j

Manacher算法

#include #include #include #include #include usingnamespace std; constint N=233333;//20W

//在o(n)时间内算出以每个点为中心的最大回文串长度 int Manacher(string st){ int len=st.size(); int*p=newint[len+1]; memset(p,0,sizeof(p)); int mx=0,id=0;

for(int i=1;i<=len;i++){

if(mx>i)p[i]=min(p[2*id-i],mx-i); else p[i]=1;

while(st[i+p[i]]==st[i-p[i]])p[i]++; if(i+p[i]>mx){mx=i+p[i];id=i;} }

int ma=0;

for(int i=1;i

int main(){

//freopen(\