算法模板【最后更新2014-05】.doc

《算法模板【最后更新2014-05】.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法模板网络122王硕目录1.数学1.1矩阵………………………21.2一次方程组的解……………31.3矩阵的逆…………………41.4最大公约数…………………61.5欧几里得扩展……………61.6素数表………………………71.7判断素数…………………81.8分解质因数…………………91.9欧拉函数…………………101.10欧拉函数表…………………111.11mobius函数…………………121.12数值积分…………………121.13数值积分（精确）………131.14快速幂求余…………………141.15进制转换…

2、………………151.16格雷码………………………161.17高精度类…………………161.18Fibonacci数列……………221.19FFT………………………232.图论2.1拓扑排序…………………242.2dijkstra…………………252.3floyd-warshall……………262.4kruskal…………………263.序列3.1快速排序…………………283.2逆序对………………………283.3最长不降子序列长度………303.4最长公共子序列长度………313.5最长公共上升子序列长度…313.6

3、最长公共上升子序列………324.字符串4.1Sunday………………………344.2子串清除…………………344.3KMP………………………375.数据结构5.1并查集………………………385.2树状数组…………………395.3左偏树………………………405.4哈希………………………415.5RMQ线段树…………………416.其他6.1多边形面积…………………436.2幻方构造…………………436.3奇数阶次幻方……………451.1矩阵#include#includeus

4、ingnamespacestd;constintMAXN=100;constintMAXM=100;structMatrix{intn,m;inta[MAXN][MAXM];voidclear(){m=n=0;memset(a,0,sizeof(a));}Matrixoperator+(constMatrix&b)const{Matrixtmp;tmp.n=n;tmp.m=m;for(inti=0;i

5、;returntmp;}Matrixoperator*(constMatrix&b)const{Matrixtmp;tmp.clear();tmp.n=n;tmp.m=m;for(inti=0;i#include#include#include

6、#defineMAX10#defineEPS1e-8usingnamespacestd;doublea[MAX][MAX+1];booll[MAX];doubleans[MAX];voidswap(double&x,double&y){doublet;t=x;x=y;y=t;}inlineintsolve(doublea[MAX][MAX+1],booll[],doubleans[],constint&n){intres=0,r=0;inti,j,k;memset(ans,0,sizeo

7、f(a));memset(l,false,n);for(i=0;iEPS){for(k=i;k<=n;k++)swap(a[j][k],a[r][k]);break;}if(fabs(a[r][i])EPS){doubletmp=a[j][i]/a[r][i];for(k=i;k<=n;k++)a[j][k]

8、-=tmp*a[r][k];}l[i]=true;r++;}for(i=0;iEPS)ans[i]=a[j][n]/a[j][i];for(i=0;i>