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

资源描述

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

《算法模板最后更新05课件.docx》由会员分享，可在线阅读，更多相关《算法模板最后更新05课件.docx（73页珍藏版）》请在冰点文库上搜索。

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

算法模板最后更新05课件

算法模板

网络122

王硕

1.数学

1.1矩阵………………………2

1.2一次方程组的解……………3

1.3矩阵的逆…………………4

1.4最大公约数…………………6

1.5欧几里得扩展……………6

1.6素数表………………………7

1.7判断素数…………………8

1.8分解质因数…………………9

1.9欧拉函数…………………10

1.10欧拉函数表…………………11

1.11mobius函数…………………12

1.12数值积分…………………12

1.13数值积分（精确）………13

1.14快速幂求余…………………14

1.15进制转换…………………15

1.16格雷码………………………16

1.17高精度类…………………16

1.18Fibonacci数列……………22

1.19FFT………………………23

2.图论

2.1拓扑排序…………………24

2.2dijkstra…………………25

2.3floyd-warshall……………26

2.4kruskal…………………26

3.序列

3.1快速排序…………………28

3.2逆序对………………………28

3.3最长不降子序列长度………30

3.4最长公共子序列长度………31

3.5最长公共上升子序列长度…31

3.6最长公共上升子序列………32

4.字符串

4.1Sunday………………………34

4.2子串清除…………………34

4.3KMP………………………37

5.数据结构

5.1并查集………………………38

5.2树状数组…………………39

5.3左偏树………………………40

5.4哈希………………………41

5.5RMQ线段树…………………41

6.其他

6.1多边形面积…………………43

6.2幻方构造…………………43

6.3奇数阶次幻方……………45

1.1矩阵

#include

usingnamespacestd;

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

for（intj=0;j

tmp.a[i][j]=a[i][j]+b.a[i][j];

returntmp;

}

Matrixoperator*（constMatrix&b）const

{

Matrixtmp;

tmp.clear（）;

tmp.n=n;tmp.m=m;

for（inti=0;i

for（intj=0;j

for（intk=0;k

tmp.a[i][j]+=a[i][k]*b.a[k][j];

returntmp;

}

};

1.2一次方程组的解

#include

#defineMAX10

#defineEPS1e-8

usingnamespacestd;

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,sizeof（a））;

memset（l,false,n）;

for（i=0;i

{

for（j=r;j

if（fabs（a[i][j]）>EPS）

{

for（k=i;k<=n;k++）

swap（a[j][k],a[r][k]）;

break;

}

if（fabs（a[r][i]）

{

res++;

continue;

}

for（j=0;j

if（j!

=r&&fabs（a[j][i]）>EPS）

{

doubletmp=a[j][i]/a[r][i];

for（k=i;k<=n;k++）

a[j][k]-=tmp*a[r][k];

}

l[i]=true;

r++;

}

for（i=0;i

if（l[i]）

for（j=0;j

if（fabs（a[j][i]）>EPS）

ans[i]=a[j][n]/a[j][i];

for（i=0;i

if（fabs（ans[i]）

ans[i]=0;

returnres;

}

intmain（）

{

intn;

inti,j,res;

cin>>n;

for（i=0;i

for（j=0;j

cin>>a[i][j];

res=solve（a,l,ans,n）;

for（i=0;i

cout<

return0;

}

1.3矩阵的逆

#include

#defineMAX10

usingnamespacestd;

vectora[MAX];

vectorc[MAX];

inlinevectoroperator*（vectora,doubleb）

{

inti;

intn=a.size（）;

vectorres（n,0）;

for（i=0;i

res[i]=a[i]*b;

returnres;

}

inlinevectoroperator-（vectora,vectorb）

{

inti;

intn=a.size（）;

vectorres（n,0）;

for（i=0;i

res[i]=a[i]-b[i];

returnres;

}

inlinevoidinverse（vectora[],vectorc[],intn）

{

inti,j;

for（i=0;i

c[i]=vector（n,0）;

for（i=0;i

c[i][i]=1;

for（i=0;i

{

for（j=i;j

if（fabs（a[j][i]>0））

{

swap（a[i],a[j]）;

swap（c[i],c[j]）;

break;

}

c[i]=c[i]*（1/a[i][i]）;

a[i]=a[i]*（1/a[i][i]）;

for（j=0;j

if（j!

=i&&fabs（a[j][i]）>0）

{

c[j]=c[j]-c[i]*a[j][i];

a[j]=a[j]-a[i]*a[j][i];

}

intmain（）

{

intn,i,j;

doublex;

cin>>n;

for（i=0;i

for（j=0;j

{

cin>>x;

a[i].push_back（x）;

}

inverse（a,c,n）;

for（i=0;i

{

for（j=0;j

cout<

}

return0;

}

1.4最大公约数

#include

intgcd（inta,intb）

{

returnb==0?

gcd（b,a%b）;

}

intlcm（inta,intb）

{

returna*b/gcd（a,b）;

}

1.5欧几里得扩展

#include

usingnamespacestd;

intgcd（inta,intb,int&x,int&y）

{

if（b==0）

{

x=1;

y=0;

returna;

}

else

{

intr=gcd（b,a%b,y,x）;

y-=x*（a/b）;

returnr;

}

intmain（）

{

inta,b,x,y;

scanf（"%d%d",&a,&b）;

printf（"%d",gcd（a,b,x,y））;

printf（"%d%d",x,y）;

return0;

}

求AB的最大公约数，且求出X,Y使得AX+BY=gcd（A,B）;

1520

5-11

1.6素数表

#include

#defineMAX350000000

usingnamespacestd;

boolvalid[MAX];

intprime[MAX];

voidgetprime（intn,int&tot,intans[]）

{

inti,j;

memset（valid,true,sizeof（valid））;

for（i=2;i<=n;i++）

{

if（valid[i]）

{

tot++;

ans[tot]=i;

}

for（j=1;（j<=tot）&&（i*ans[j]<=n）;j++）

{

valid[i*ans[j]]=false;

if（i%ans[j]==0）

break;

}

intmain（）

{

inti,n,sum=0,j=0;

cin>>n;

getprime（n,sum,prime）;

for（i=1;i<=sum;i++）

{

cout<

j++;

if（j%10==0）

cout<

}

return0;

}

1.7判断素数

#include

usingnamespacestd;

longlongintrsa（longlonginta,longlongintk,longlongintm）

{

if（k==0）

return1%m;

longlonginttmp=rsa（a,k>>1,m）;

tmp=tmp*tmp%m;

if（k&1）

tmp=tmp*a%m;

returntmp;

}

booltest（intn,inta,intd）

{

if（n==2）

returntrue;

if（n==a）

returntrue;

if（（n&1）==0）

returnfalse;

while（!

（d&1））

d=d>>1;

longlongintt=rsa（a,d,n）;

while（（d!

=n-1）&&（t!

=1）&&（t!

=n-1））

{

t=t*t%n;

d=d<<1;

}

return（t==n-1）||（（d&1）==1）;

}

boolisprime（intn）

{

if（n<2）

returnfalse;

inta[]={2,3,61,4567,23456789},i;

for（i=0;i<5;i++）

if（!

test（n,a[i],n-1））

returnfalse;

returntrue;

}

intmain（）

{

longlonginti,n,sum=0;

cin>>n;

for（i=2;i<=n;i++）

if（isprime（i））

{

cout<

sum++;

if（sum%10==0）

cout<

}

return0;

}

1.8分解质因数

#include

#defineMAX10000

longlonginta[MAX],b[MAX],tot;

usingnamespacestd;

voidfactor（longlongintn,longlonginta[],longlongintb[],longlongint&tot）

{

longlonginttemp=sqrt（n）+1,now=n;

inti;

tot=0;

for（i=2;i<=temp;i++）

if（now%i==0）

{

a[++tot]=i;

b[tot]=0;

while（now%i==0）

{

b[tot]++;

now/=i;

}

temp=sqrt（now）+1;

}

if（now!

=1）

{

a[++tot]=now;

b[tot]=1;

}

intmain（）

{

longlongintn,i;

cin>>n;

//fenjie（n,2）;

factor（n,a,b,tot）;

for（i=1;i<=tot;i++）

cout<

for（i=1;i<=tot;i++）

cout<

return0;

}

/*7212345678900630630*/

1.9欧拉函数

#include

longlonginteular（longlongintn）

{

longlongintret=1,i;

for（i=2;i*i<=n;i++）

if（n%i==0）

{

n/=i,ret*=i-1;

while（n%i==0）

n/=i,ret*=i;

}

if（n>1）

ret*=n-1;

returnret;

}

intmain（）

{

longlongintn;

scanf（"%lld",&n）;

printf（"%lld",eular（n））;

return0;

}

//小于或等于n的数中与n互质的数的个数。

1.10欧拉函数表

#include

#defineMAX100

usingnamespacestd;

intmindiv[MAX],phi[MAX];

voidgenphi（intn）

{

inti,j;

for（i=1;i

mindiv[i]=i;

for（i=2;i*i

if（mindiv[i]==i）

for（j=i*i;j

mindiv[j]=i;

phi[1]=1;

for（i=2;i

{

phi[i]=phi[i/mindiv[i]];

if（（i/mindiv[i]）%mindiv[i]==0）

phi[i]*=mindiv[i];

else

phi[i]*=mindiv[i]-1;

}

intmain（）

{

intn,i;

genphi（MAX）;

for（i=1;i

cout<

return0;

}

//1122426464

//10412688166188

//121022810121812288

1.11mobius函数

#include

#defineMAX1<<20

usingnamespacestd;

intmu[MAX];

voidgenmu（intn）

{

inti,j;

for（i=1;i<=n;i++）

{

inttarget=（i==1）;

intdelta=target-mu[i];

mu[i]=delta;

for（j=i+1;j<=n;j+=i）

mu[j]+=delta;

}

intmain（）

{

intn,i;

cin>>n;

genmu（n）;

for（i=1;i

cout<

return0;

}

//1-10-11-22-34-5

//4-58-97-913-1412-13

//18-2117-1829-3123-2836-37

1.12数值积分

#include

#defineMAXN300000

usingnamespacestd;

doublef（doublex）

{

returnsin（x）/（sin（x）+cos（x））;

}

doublesimpson（doublea,doubleb,intn）

{

constdoubleh=（b-a）/n;

doubleans=f（a）+f（b）;

for（inti=1;i

ans+=4*f（a+i*h）;

for（inti=0;i

ans+=2*f（a+i*h）;

returnans*h/3;

}

intmain（）

{

doublea,b,n;

cin>>a>>b;

cout<

return0;

}

/*求f（x）在[a,b]上的积分*/

1.13数值积分（精确）

#include

usingnamespacestd;

doublef（doublex）

{

returnsqrt（1-sin（2*x））;

}

doubleRomberg（doublea,doubleb,doubleeps=1e-8）

{

doublet[64];

doubleh=b-a;

intn=1,i;

t[0]=h*（f（a）/4.0+f（b）/4.0+f（a+h/2.0）/2.0）;

t[1]=h*（f（a）/6.0+f（b）/6.0+f（a+h/2.0）/1.5）;

for（i=2;fabs（t[i-2]-t[i-1]）>eps;i++）

{

intj;

h/=2.0;

n<<=1;

doublebase=t[0]/h;

doublex=a+h/2.0;

for（j=0;j

{

base+=f（x）;

x+=h;

}

base=base*h/2.0;

doublek1=4.0/3.0,k2=1.0/3.0;

for（j=0;j

{

doubletemp=k1*base-k2*t[j];

t[j]=base;

base=temp;

k2=k2/（4.0*k1-k2）;

k1=k2+1.0;

}

t[i]=base;

}

returnt[i-1];

}

intmain（void）

{

doublea,b;

cin>>a>>b;

cout<

return0;

}

1.14快速幂求余

#include

longlongintrsa（longlonginta,longlongintk,longlongintm）

{

longlongintb=1;

while（k>=1）

{

if（k%2==1）

b=a*b%m;

a=a*a%m;

k=k/2;

}

returnb;

}

1.15进制转换

#include

usingnamespacestd;

stringtransform（intx,inty,strings）

{

inti,l;

stringres="";

intsum=0;

l=s.length（）;

for（i=0;i

{

if（s[i]=='-'）

continue;

if（s[i]>='0'&&s[i]<='9'）

sum=sum*x+s[i]-'0';

else

sum=sum*x+s[i]-'A'+10;

}

while（sum）

{

chartmp=sum%y;

sum/=y;

if（tmp<=9）

tmp+='0';

else

tmp=tmp+'A'-10;

res=tmp+res;

}

if（res.length（）==0）

res="0";

if（s[0]=='-'）

res=

展开阅读全文