算法模板最后更新05课件.docx

1、算法模板最后更新05课件算法模板网络122王硕目录1.数学 1.1 矩阵 21.2 一次方程组的解 31.3 矩阵的逆 41.4 最大公约数 61.5 欧几里得扩展 61.6 素数表 71.7 判断素数 81.8 分解质因数 91.9 欧拉函数 101.10 欧拉函数表 111.11 mobius函数 121.12 数值积分 121.13 数值积分（精确） 131.14 快速幂求余 141.15 进制转换 151.16 格雷码 161.17 高精度类 161.18 Fibonacci数列 221.19 FFT 232.图论 2.1 拓扑排序 242.2 dijkstra 252.3 floyd

2、-warshall 262.4 kruskal 263.序列 3.1 快速排序 283.2 逆序对 283.3 最长不降子序列长度 303.4 最长公共子序列长度 313.5 最长公共上升子序列长度 313.6 最长公共上升子序列 324.字符串 4.1 Sunday 344.2 子串清除 344.3 KMP 375.数据结构 5.1 并查集 385.2 树状数组 395.3 左偏树 405.4 哈希 415.5 RMQ线段树 416.其他6.1 多边形面积 436.2 幻方构造 436.3 奇数阶次幻方 451.1矩阵#include #include using namespace std

3、;const int MAXN=100;const int MAXM=100;struct Matrix int n,m; int aMAXNMAXM; void clear() m=n=0; memset(a,0,sizeof(a); Matrix operator +(const Matrix &b) const Matrix tmp; tmp.n=n; tmp.m=m; for(int i=0;in;i+) for(int j=0;jm;j+) tmp.aij=aij+b.aij; return tmp; Matrix operator *(const Matrix &b) const

4、Matrix tmp; tmp.clear(); tmp.n=n; tmp.m=m; for(int i=0;in;i+) for(int j=0;jb.m;j+) for(int k=0;km;k+) tmp.aij+=aik*b.akj; return tmp; ;1.2一次方程组的解#include #include #include #include #define MAX 10#define EPS 1e-8using namespace std;double aMAXMAX+1;bool lMAX;double ansMAX;void swap(double &x,double &

5、y) double t; t=x; x=y; y=t;inline int solve(double aMAXMAX+1,bool l,double ans,const int &n) int res=0,r=0; int i,j,k; memset(ans,0,sizeof(a); memset(l,false,n); for(i=0;in;i+) for(j=r;jEPS) for(k=i;k=n;k+) swap(ajk,ark); break; if(fabs(ari)EPS) res+; continue; for(j=0;jEPS) double tmp=aji/ari; for(

6、k=i;k=n;k+) ajk-=tmp*ark; li=true; r+; for(i=0;in;i+) if(li) for(j=0;jEPS) ansi=ajn/aji; for(i=0;in;i+) if(fabs(ansi)n; for(i=0;in;i+) for(j=0;jaij; res=solve(a,l,ans,n); for(i=0;in;i+) coutansi ; return 0;1.3矩阵的逆#include #include #include #include #define MAX 10using namespace std;vector aMAX;vecto

7、r cMAX;inline vector operator *(vector a,double b) int i; int n=a.size(); vector res(n,0); for(i=0;in;i+) resi=ai*b; return res;inline vector operator -(vector a,vector b) int i; int n=a.size(); vector res(n,0); for(i=0;in;i+) resi=ai-bi; return res;inline void inverse(vector a,vector c,int n) int i

8、,j; for(i=0;in;i+) ci=vector (n,0); for(i=0;in;i+) cii=1; for(i=0;in;i+) for(j=i;j0) swap(ai,aj); swap(ci,cj); break; ci=ci*(1/aii); ai=ai*(1/aii); for(j=0;j0) cj=cj-ci*aji; aj=aj-ai*aji; int main() int n,i,j; double x; cinn; for(i=0;in;i+) for(j=0;jx; ai.push_back(x); inverse(a,c,n); for(i=0;in;i+)

9、 for(j=0;jn;j+) coutcij ; coutendl; return 0;1.4最大公约数#include int gcd(int a,int b) return b=0?a:gcd(b,a%b);int lcm(int a,int b) return a*b/gcd(a,b);1.5欧几里得扩展#include using namespace std;int gcd(int a,int b,int &x,int &y) if(b=0) x=1; y=0; return a; else int r=gcd(b,a%b,y,x); y-=x*(a/b); return r; in

10、t main() int a,b,x,y; scanf(%d%d,&a,&b); printf(%d ,gcd(a,b,x,y); printf(%d %d,x,y); return 0;/* 求AB的最大公约数，且求出X,Y使得AX+BY=gcd(A,B); 15 20 5 -1 1*/1.6素数表#include #include #include #define MAX 350000000using namespace std;bool validMAX;int primeMAX;void getprime(int n,int &tot,int ans) int i,j; memset(

11、valid,true,sizeof(valid); for(i=2;i=n;i+) if(validi) tot+; anstot=i; for(j=1;(j=tot)&(i*ansjn; getprime(n,sum,prime); for(i=1;i=sum;i+) coutprimei ; j+; if(j%10=0) coutendl; return 0;1.7判断素数#include #include using namespace std;long long int rsa(long long int a,long long int k,long long int m) if(k=

12、0) return 1%m; long long int tmp=rsa(a,k1,m); tmp=tmp*tmp%m; if(k&1) tmp=tmp*a%m; return tmp;bool test(int n,int a,int d) if(n=2) return true; if(n=a) return true; if(n&1)=0) return false; while(!(d&1) d=d1; long long int t=rsa(a,d,n); while(d!=n-1)&(t!=1)&(t!=n-1) t=t*t%n; d=d1; return (t=n-1)|(d&1

13、)=1);bool isprime(int n) if(n2) return false; int a=2,3,61,4567,23456789,i; for(i=0;in; for(i=2;i=n;i+) if(isprime(i) couti ; sum+; if(sum%10=0) coutendl; return 0;1.8分解质因数#include #include #define MAX 10000long long int aMAX,bMAX,tot;using namespace std;void factor(long long int n,long long int a,l

14、ong long int b,long long int &tot) long long int temp=sqrt(n)+1,now=n; int i; tot=0; for(i=2;in; /fenjie(n,2); factor(n,a,b,tot); for(i=1;i=tot;i+) coutai ; coutendl; for(i=1;i=tot;i+) coutbi ; return 0;/*7212345678900630630*/1.9欧拉函数#include long long int eular(long long int n) long long int ret=1,i

15、; for(i=2;i*i1) ret*=n-1; return ret;int main() long long int n; scanf(%lld,&n); printf(%lld,eular(n); return 0;/小于或等于n的数中与n互质的数的个数。1.10欧拉函数表#include #include #define MAX 100using namespace std;int mindivMAX,phiMAX;void genphi(int n) int i,j; for(i=1;in;i+) mindivi=i; for(i=2;i*in;i+) if(mindivi=i)

16、for(j=i*i;jn;j+=i) mindivj=i; phi1=1; for(i=2;in;i+) phii=phii/mindivi; if(i/mindivi)%mindivi=0) phii*=mindivi; else phii*=mindivi-1; int main() int n,i; genphi(MAX); for(i=1;iMAX;i+) coutphii ; return 0;/1 1 2 2 4 2 6 4 6 4/10 4 12 6 8 8 16 6 18 8/12 10 22 8 10 12 18 12 28 81.11mobius函数#include #in

17、clude #define MAX 120using namespace std;int muMAX;void genmu(int n) int i,j; for(i=1;i=n;i+) int target=(i=1); int delta=target-mui; mui=delta; for(j=i+1;jn; genmu(n); for(i=1;in;i+) coutmui ; return 0;/1 -1 0 -1 1 -2 2 -3 4 -5/4 -5 8 -9 7 -9 13 -14 12 -13/18 -21 17 -18 29 -31 23 -28 36 -371.12数值积分

18、#include #include #define MAXN 300000using namespace std;double f(double x) return sin(x)/(sin(x)+cos(x);double simpson(double a,double b,int n) const double h=(b-a)/n; double ans=f(a)+f(b); for(int i=1;in;i+=2) ans+=4*f(a+i*h); for(int i=0;iab; coutsimpson(a,b,MAXN)endl; return 0;/* 求f(x)在 a,b上的积分*

19、/1.13数值积分(精确)#include #include using namespace std;double f(double x) return sqrt(1-sin(2*x);double Romberg(double a,double b,double eps=1e-8) double t64; double h=b-a; int n=1,i; t0=h*(f(a)/4.0+f(b)/4.0+f(a+h/2.0)/2.0); t1=h*(f(a)/6.0+f(b)/6.0+f(a+h/2.0)/1.5); for(i=2;fabs(ti-2-ti-1)eps;i+) int j;

20、h/=2.0; n=1; double base=t0/h; double x=a+h/2.0; for(j=0;jn;j+) base+=f(x); x+=h; base=base*h/2.0; double k1=4.0/3.0,k2=1.0/3.0; for(j=0;jab; coutRomberg(a,b,1e-8)endl; return 0;1.14快速幂求余#include long long int rsa(long long int a,long long int k,long long int m) long long int b=1; while(k=1) if(k%2=

21、1) b=a*b%m; a=a*a%m; k=k/2; return b;1.15进制转换#include #include using namespace std;string transform(int x,int y,string s) int i,l; string res=; int sum=0; l=s.length(); for(i=0;i=0&si=9) sum=sum*x+si-0; else sum=sum*x+si-A+10; while(sum) char tmp=sum%y; sum/=y; if(tmp=9) tmp+=0; else tmp=tmp+A-10; res=tmp+res; if(res.length()=0) res=0; if(s0=-) res=