2010 ACM程序競(jìng)賽模板

免費(fèi)模板

2010ACM程序競(jìng)賽模板

浙江省第七屆大學(xué)生程序設(shè)計(jì)競(jìng)賽

英文隊(duì)名：OhJack&Rose

中文隊(duì)名：潘多拉星球暴力AC聯(lián)盟

哈嘻嘟

2010年4月17日

目錄

、圄論

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

1.1.最小生成樹類prim算法..................................................1

1.2.拓?fù)渑判?...............................................................4

1.3.最短源路徑Folyd實(shí)現(xiàn)...................................................5

1.4.關(guān)鍵路徑實(shí)現(xiàn)算法.......................................................6

1.5.二分圖最大匹配的匈牙利算法.............................................7

1.6.并查集...................................................................9

二、動(dòng)規(guī)...........................................................................................10

2.1.求最長(zhǎng)子序列...........................................................10

2.2.求解最長(zhǎng)升序列長(zhǎng)度及子序列............................................12

2.3.完全背包問題..........................................................13

2.4.0-1背包問題...........................................................14

2.5.母函數(shù)DP算法求組合數(shù).................................................14

2.6.滾動(dòng)數(shù)組求回文串問題..................................................17

三、貪心...........................................................................................18

3.1.時(shí)間安排問題...........................................................18

3.2.求最大子段和..........................................................19

3.3.貪心求最少非遞減序列數(shù)................................................20

四、數(shù)蹌..........................................................................................21

4.1.簡(jiǎn)單求Cnk問題........................................................21

4.2.巧求階乘位數(shù)..........................................................21

4.3.線性算法求素?cái)?shù)........................................................22

五、其他..........................................................................................22

5.1.采用位操作遞歸求解示例.................................................22

5.2.Stack和Queue用法.....................................................23

5.3.map使用詳解...........................................................24

5.4.字典樹建立與查找......................................................24

5.5.KMP匹配算法...........................................................26

5.6.后綴數(shù)組求最長(zhǎng)連續(xù)公共子序列長(zhǎng)度.....................................27

5.7.循環(huán)字符串最小位置表示及同構(gòu)判斷.....................................30

5.8.求哈夫曼樹編碼長(zhǎng)度....................................................32

5.9.堆排序算法............................................................34

5.10.線段樹著色問題.......................................................35

六、附：..........................................................................................38

6.1.C++最值常量...........................................................38

6.2.類型轉(zhuǎn)換................................................................39

6.3.String常用函數(shù)舉例.....................................................39

6.4.C++常用頭文件..........................................................40

一、圖論

1.1.最小生成樹類prim算法

第1頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

1.1.1下標(biāo)從1開始

#include<iostream>

#include<cstdio>

#include<algorithm>

usingnamespacestd;

#defineSIZE101

itdefineMAXSIZE10201

intn,nline;/*n個(gè)點(diǎn),nline行關(guān)系*/

intin[SIZE];

structPoint{

intx,y;/*編號(hào)從1開始*/

intv;/*根據(jù)實(shí)際情況更改類型*/

}p[MAXSIZE];/*n*(n-l)/2*/

intcmp(Pointa,Pointb){

returna.v<b.v;

)

intprim(){

intdis,count,i,j;

memset(in,0,sizeof(in));

in[p[l].x]=in[p[l].y]=l;

dis=p[l].v;

count=n-l;

while(count-){/*做n-l次*/

for(j=2;j<nline;j++){

if((in[p[j].x]&&!in[p[j].y])||

(!in[p[j].x]&&in[p[j].y])){

in[pEj].x]=l;

in[p[j].y]=l;

dis+=p[j],v;

break;

returndis;

}

intmain(){

intx,y,v,i；

while(scanf("版T,&n)&&n){

if(n==l){/*有可能輸入的為1個(gè)點(diǎn)*/

printf("0\n");

第2頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

continue;

)

nline=n*(n-l)/2+l;

for(i=l;i<nline;i++){

scanf(z/%d%d%d/z,&p[i].x,y,&p[i].v);

)

sort(p+1,p+nline,cmp);

printf("%d\n",prim());

)

return0;

)

1.1.2下標(biāo)從0開始

#include<iostream>

#include<cstdio>

#include<algorithm>

usingnamespacestd;

#defineSIZE101

ttdefineMAXSIZE10201

intn,nline;/*n個(gè)點(diǎn)，nline行關(guān)系*/

intin[SIZE];

structPoint{

intx,y;/*編號(hào)從1開始*/

intv;/*根據(jù)實(shí)際情況更改類型*/

}p[MAXSIZE];/*n*(nT)/2*/

intcmp(Pointa,Pointb){

returna.v<b.v;

)

intprim(){

intdis,count,i,j;

memset(in,0,sizeof(in));

in[p[0].x]=in[p[0].y]=l;

dis=p[0].v;

count=n-l;

while(count-){/*做n-1次*/

for(j=l;j<nline;j++){

if((in[p[j].x]&&!in[p[j].y])||

(!in[p[j].x]&&in[p[j].y])){

in[p[j].x]=l;

in[p[j].y]=l;

dis+=p[j].v;

第3頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

break;

)

)

)

returndis;

)

intmain(){

intx,y,v,i;

while(scanf&n)&&n){

if(n=l){/*有可能輸入的為1個(gè)點(diǎn)*/

printf(〃0\n〃)；

continue;

}

nline=n*(n-l)/2;

for(i=0;i<nline;i++){

scanf(〃%d%d%d〃,x,&p[i].y,&p[i].v);

)

sort(p,p+nline,cmp);

printf(，/%d\n，/,prim());

)

return0;

)

1.2.拓?fù)渑判?/p>

#include<iostream>

#include<cstdio>

#include<cstring>

^defineM501

usingnamespacestd;

intmap[M][M],degree[M];

intne;/*個(gè)數(shù)*/

voidtopo(){

inti,j,k;

for(i=0;i<ne;i++){

j=l；

while(j<=ne&°ree[j])j++;

〃直到一個(gè)度為零的頂點(diǎn),這里不檢查有多個(gè)度為零的情況

〃if(j>ne){break;}不是拓?fù)浣Y(jié)構(gòu)

if(i)printf(〃〃);

printf(/z%d，z,j);

degree

for(k=l;k<=ne;k++){

第4頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

degree[k]-=map[j][k];

)

)

printf('\n");

}

intmain(){

inta,b,i,j,nline;/*nline行*/

while(scanf&ne,&nline)!=EOF){

memset(map,0,sizeof(map));

memset(degree,0,sizeof(degree));

while(nline—){

scanf&a,&b);

map[a][b]=l;/*atob*/

)

for(i=l;i<=ne;i++){

for(j=l;j<=ne;j++){

if(map[i][j])degree[j]++;

)

)

topo()；/*拓?fù)?/

)

return0;

)

1.3.最短源路徑Folyd實(shí)現(xiàn)

#include<iostream>

#include<cstdio>

#include<cstring>

^defineM201

usingnamespacestd;

intn,map[M][M],start,end;

voidfolyd(){

inti,j,k；

for(i=0;i<n;i++){

for(j=0;j<n;j++){

for(k=0;k<n;k++){

if(map[j][i]==-l||map[i][k]==-l)continue;

if(map[j][k]==-l||map[j][i]+map[i][k]<map[j][k]){

map[j]Lk]=map[j][i]+map[i][k];

)

第5頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

)

intmainO{

intnline,i,j,a,b,v;

while(scanf(，z%d%d，z,&n,&nline)!=EOF){

memset(map,-1,sizeof(map));

for(i=0;i<n;i++){

map[i]Li]=0;

)

for(i=0;i<nline;i++){

scanf(z，%d%d%d/z,&a,&b,&v);/*編號(hào)從0開始*/

if(map[a][b]==-11|map[a][b]>v){〃一個(gè)點(diǎn)到另一個(gè)有多條路

map[b][a]=map[a][b]=v;

)

}

scanf(〃％d%d〃,&start,&end);

folydO;

if(map[start][end]!=-l){

printf(〃％d\n〃,map[start][end]);

)

elseprintf(〃-l\n〃)；

)

return0;

1.4.關(guān)鍵路徑實(shí)現(xiàn)算法

#include<iostream>

#include<cstdio>

#include<cstring>

#defineM501

usingnamespacestd;

intmap[M][M],degree[M],dp[M];

intne;/*個(gè)數(shù)*/

inttopoplus(){

inti,j,k,maxnum;

for(i=0;i<ne;i++){

J=l；

while(j<=ne&°ree[j])j++;

〃直到一個(gè)度為零的頂點(diǎn),這里不檢查有多個(gè)度為零的情況

//if(j>ne){break;}不是拓?fù)浣Y(jié)構(gòu)

degree

for(k=l;k<=ne;k++){

第6頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

if(map[j][k]){

if(map[j][k]+dp[j]>dp[k]){

dp[k]=mapLj][k]+dp[j];

}

degree[k]--；

for(i=0;i<=ne;i++){

if(dp[i]>maxnum){

maxnum=dp[i];

returnmaxnum;

)

intmain(){

inta,b,v,i,j,nline;/*nline行*/

while(scanf(zz%d%d，z,&ne,fenline)!=EOF){

memset(map,0,sizeof(map));

memset(degree,0,sizeof(degree));

memset(dp,0,sizeof(dp));

while(nline—){

scanf&a,&b,&v);

map[a][b]=v;/*atob,v>0*/

)

for(i=l;i<=ne;i++){

for(j=l;j<=ne;j++){

if(map[i][j])degree[j]++;

)

}

printf(，，%d\n，/,topoplus());/*拓?fù)涓倪M(jìn)*/

}

return0;

1.5.二分圖最大匹配的匈牙利算法

#include<iostream>

#include<cstdio>

第7頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

#defineN301

usingnamespacestd;

intisuse[N];〃記錄y中節(jié)點(diǎn)是否使用

intlk[N];〃記錄當(dāng)前與y節(jié)點(diǎn)相連的x的節(jié)點(diǎn)

intmat[N][N];//記錄連接x和y的邊，如果i和j之間有邊則為1,否則為0

intgn,gm;〃二分圖中x和y中點(diǎn)的數(shù)目

intcan(intt){

inti;

for(i=l;i<=gm;i++){〃下標(biāo)從1開始

if(isuse[i]==0&&mat[t][i]){

isuse[i]=l;

if(lk[i]==-l||can(lk[i])){

lk[i]=t;

return1;

)

)

)

return0;

)

intMaxMatchO{

inti,num=0;

memset(Ik,-1,sizeof(Ik));

for(i=l;i<=gn;i++){

memset(isuse,0,sizeof(isuse));

if(can(i))num++;

)

returnnum;

)

intmainO{

intt,i,j,k,tmp;

scanf(〃%d〃，&t);

while(t--){

scanf(〃%d%d〃,&gn,&gm);

memset(mat,0,sizeof(mat));〃主要得到mat這個(gè)數(shù)組

for(i=l;i<=gn;i++){

scanf&k);

for(j=l;j<=k;j++){

scanf(〃％d〃,&tmp);

[tmp]=1;〃注意從1開始

第8頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

if(MaxMatch()==gn){

printf("YES\n");

)

elseprintf("N0\n");

)

return0;

)

/*

In:

2

33

3123

212

11

33

213

213

11

Out:

YES

NO

*/

1.6.并查集

#include<iostream>

#include<cstdio>

usingnamespacestd;

constintN=1010;

intpre[N];

voidMerge(intx,inty){

inti,t,rx=x,ry=y;

while(pre[rx]!=-1)〃搜索x的樹根

rx=pre[rx];

while(pre[ry]!=T)〃搜索y的樹根

ry=pre[ry];

i=x;

〃壓縮x

while(pre[i]!=-l){

t=pre[i];

pre[i]=rx;

i=t;

}

i=y;〃壓縮y

while(preLi]!=-l){

第9頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

t=pre[i];

pre[i]=rx;

i=t;

)

if(ry!=rx)//合并

pre[ry]=rx;

return;

)

intmain(){

intx,y,i,ans,n,m;

while(scanf("%d",&n)&&n){

scanf(線d",&m);

memset(pre,-1,sizeof(pre));

for(i=0;i<m;i++){

〃x與y連通

scanf(z/%d%d”,&x,&y);

Merge(x,y);

)

ans=0;

for(i=l;i<=n;i++)

if(pre[i]==-l)

ans++;

printf("96d\n”,ans'l);

/*

http://acm.hdu.edu.cn/showproblem.php?pid=1232

in:

42

13

43

9990

0

out:

1

998

*/

二、動(dòng)機(jī)

2.1.求最長(zhǎng)子序列

#include<iostream>

第10頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

#include<cstdio>

#defineM1001

usingnamespacestd;

chara[M],b[M];

intdp[M+l][M+l],lena,lenb;

voidinit(){

inti,j;

for(i=0;i<=lena;i++){

for(j=0;j<=lenb;j++){

dp[i][j]=0;

)

)

)

intcmax(intx,inty){

returnx>y?x:y;

)

intmain(){

inti,j,len;

//，，

while(scanf(%s>a)!=E0F){

scanfb);

init();

〃下面這步很重要，否則會(huì)超時(shí)

lena=strlen(a);

lenb=strlen(b);

for(i=0;i<lena;i++){

for(j=0;j<lenb;j++){

if(a[i]==b[j]){

dp[i+l][j+l]=dp[i][j]+l;

)

else{

dp[i+l][j+l]=cmax(dp[i][j+1],dp[i+l][j]);

}

)

)

〃子序列長(zhǎng)度

printf("%d\n",dp[i][j]);

/*打印出子序列*/

len=l;

for(i=l;i<=lena;i++){

for(j=l;j<=lenb;j++){

if(len==dp[i][j]){

printf("枇"，a[i-l]);

len++;

第11頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

break;

printf(〃\n〃)；

)

return0;

2.2.求解最長(zhǎng)升序列長(zhǎng)度及子序列

#include<iostream>

#include<cstdio>

ftdefineM1001

usingnamespacestd;

inta[M],dp[M];

voidinit(intn){

inti;

for(i=0;i<n;i++){

dp[i]=l;

)

}

intlis(intn){

inti,j,maxlen=l;//初始長(zhǎng)度為1

for(i=n-2;i>=0;i—){

for(j=n-l;j>i;j—){

if(a[i]<a[j]){

if(dp[j]+l>dp[i]){

dp[i]=dp[j]+l;

)

if(dp[i]>maxlen)maxlen=dpLi];

returnmaxlen;

)

voidshowlis(intn,intmaxlen){

inti;

for(i=0;i<n;i++){

if(dp[i]==maxlen){

printf("96d”,a[i]);

maxlen―;

第12頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

printf(〃\n〃)；

intmainO{

intt,n,i,maxlen;

scanf(〃%d〃,&t);

while(t-){

/*l<=n<=1000*/

scanf(〃%d〃,&n);

for(i=0;i<n;i++){

scanf(〃%d〃,&a[i]);

}

init(n);

maxlen=lis(n);

printf(〃%d\n〃,maxlen);

〃顯示最長(zhǎng)升序列

showlis(n,maxlen);

)

return0;

2.3.完全背包問題

#include<iostream>

#include<cstring>

#include<cstdio>

usingnamespacestd;

inttype□={150,200,350};〃種類

intdpClOOOl];

intmax(inta,intb){

returna>b?a:b;

)

intmainO{

intt,n,i,j;

scanf(〃%d〃，&t);

while(t--){

scanf(〃%d〃,&n);

memset(dp,0,sizeof(dp));

for(i=0;i<3;i++){

for(j=type[i];j<=n;j++){

〃剩余容量為j時(shí)裝的東西量最大

dp[j]=max(dp[j],dp[j-type[i]]+type[i]);

printf(，z%d\n，z,n-dp[n]);

第13頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

}

return0;

2.4.0-1背包問題

#include<iostream>

#include<cstdio>

#include<cstring>

#defineM1002

usingnamespacestd;

intval[M],wei[M],dp[M][M];

intcmax(inta,intb){

returna>b?a:b;

)

intmain(){

intt,n,w,i,j;

scanf(〃%d〃,&t);

while(t--){

scanf(〃%d%d〃，&n,&w);

for(i=l;i<=n;i++){

scanf(〃刎〃，&val[i]);

}

for(i=l;i<=n;i++){

scanf(級(jí)d〃,&wei[i]);

)

memset(dp,0,sizeof(dp));

for(i=l;i<=n;i++){

for(j=0;j<=w;j++){

if(j>=wei[i])

dp[i][j]=cmax(dp[i-l][j-wei[i]]+val[i],dp[i-l][j]);

elsedp[i][j]=dp[i-l][j];

)

}

printfr%d\n",dp[n][w]);

)

return0;

2.5.母函數(shù)DP算法求組合數(shù)

2.5.1.求母函數(shù)各系數(shù)值DP

Sinclude<iostream>

#defineM17

第14頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

#defineMAX305

usingnamespacestd;

intcl[MAX],c2[MAX],add[M+l];〃add口保存M種類

voidinit(){

inti;

for(i=l;i<=M;i++){

add[i]=i*i;

}

)

intsolve(intn)

(

inti,j,k;

〃cl[k],c2[k]表示展開式中x~k的系數(shù)

memset(cl,0,sizeof(cl));

memset(c2,0,sizeof(c2));

cl[0]=c2[0]=l;

〃使用前i種幣時(shí)的情況，也即母函數(shù)展開前i個(gè)多項(xiàng)式的乘積

for(i=l;i<=M;i++){

〃求新的多項(xiàng)式中的系數(shù)

for(j=0;j<n;j++){

for(k=l;j+k*add[i]<=n;k++){

c2[j+k*add[i]]+=c1[j];

)

)

for(k=0;k〈=n;k++){〃滾動(dòng)數(shù)組

cl[k]=c2[k];

)

)

returncl[n];

)

intmain(){

intn;

init();

while(scanf("%d",&n)&&n){

printf("%d\n",solve(n));

}

return0;

}

2.5.2.狀態(tài)繼承類DP求某個(gè)和是否存在

#include<cstdio>

#include<iostream>

#include<cstring>

usingnamespacestd;

第15頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

booldp[250002];

intval[101],num[101];〃對(duì)應(yīng)的值和數(shù)量

intmain(){

intn,i,j,sum,k;

while(scanf&n)&&n〉0){

sum=0;

for(i=0;i<n;i++){

scanf("%d%d”,&val[i],&num[i]);

sum+=val[i]*num[i];

)

//dp中保存所有可能的組合

memset(dp,0,sizeof(dp));

dp[0]=l;

〃遍歷n種物品

for(i=0;i<n;i++){

〃對(duì)區(qū)間求

for(j=sum/2;j>=0;j—){

if(!dp[j]){

for(k=l;k<=num[i]&&k*val[i]<=j;k++){

dp[j]=dp[j-k*val[i]];

)

)

)

)

for(i=sum/2;i>=0;i一){

if(dp[i]){

printf(，z%d%d\n，z,sum-i,i);

break;

)

)

)

return0;

)

/*

in:

2

101

201

3

101

202

301

-1

out:

第16頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

2010

4040

*/

2.6.滾動(dòng)數(shù)組求回文串問題

#include<cstdio>

#include<iostream>

#include<cstring>

SdefineM5001

usingnamespacestd;

charstr[M],rstr[M];

intdp⑵[M];〃滾動(dòng)DP

intcmax(intx,inty){

returnx>y?x:y;

)

intmain(){

intn,i,j,si,s2;

while(scanf(zz%dz，,&n)!=EOF){

scanf(〃%s",str);

〃反轉(zhuǎn)字符數(shù)組

for(i=0;i<n;i++){

rstr[n-i-l]=str[i];

)

rstr[n]=，\0';

memset(dp,0,sizeof(dp));

for(i=0;i<n;i++){

for(j=0;j<n;j++){

sl=i%2;

s2=(i+l)%2;

if(str[i]==rstrLj]){

dp[sl][j+l]=dp[s2][j]+l;

)

else{

dp[sl][j+l]=cmax(dp[s2][j+1],dpLsl][j]);

)

)

}

printf(〃%d\n〃,n-dp[(n-l)%2][n]);

)

return0;

)

/*

http://acm.hdu.edu.cn/showproblem.php?pid=1513

第17頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

in:

5

Ab3bd

out:

2

*/

三、貪心

3.1.時(shí)間安排問題

#include<iostream>

#include<cstdio>

#include<algorithm>

#defineM101

usingnamespacestd;

intn;

structPoint{

ints,e;

}p[M];

intcmp(Pointa,Pointb){

if(a.s==b.s)

returna.e<b.e;

elsereturna.s<b.s;

)

intarrange(){

intstart,end,i,count=l;

start=p[0].s;

end=p[0].e;

for(i=l;i<n;i++){

if(p[i].s>=start&&p[i].e<=end){

start=p[i].s;

end=p[i].e;

}

elseif(p[i].s>=end){

count++;

end=p[i].e;

}

)

returncount;

)

intmain(){

inti;

while(scanf(，z%dz，,&n)&&n){

第18頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

for(i=0;i<n;i++){

scanf(，z%d%d，z,&p[i].s,&p[i].e);

)

sort(p,p+n,cmp);

printf(〃％d\n〃,arrange());

)

return0;

3.2.求最大子段和

#include<iostream>

usingnamespacestd;

intmainO{

intt,n,i,a[100002];

intbeg,end,x,y,cursum,maxsum;

cin?t;

while(t-){

cin>>n;

for(i=0;i<n;i++){

cin>>a[i];

}

beg=end=l;

cursum=maxsum=a[O];

x=y=l;

for(i=l;i<n;i++){

if(a[i]+cursum<aEi]){

cursum=a[i];

x=i+1;

)

else{

cursum+=a[i];

)

if(cursum>maxsum){

maxsum=cursum;

beg二x;

end=i+l;

)

)

cout?maxsum<<，z，，?beg?z//z?end<<endl;

)

return0;

)

/*

第19頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

in:

2

56-154-7

706-11-67-5

out:

1414

716

*/

3.3.貪心求最少非遞減序列數(shù)

#include<iostream>

#include<cstdio>

#include<cstring>

usingnamespacestd;

inta[1001];

intmain(){

intn,i,j,len,count,high;

while(scanf(zz%dz，,&n)!=EOF){

for(i=0;i<n;i++){

scanf(〃%d〃,&a[i]);

}

count=0;

len=n;

while(len){

count++;

high=30005;〃最高值

for(i=0;i<n;i++){

if(a[i]&&a[i]<high){

high=a[i];

a[i]=0;〃標(biāo)記已用值

len一;

)

printf(，/%d\n，/,count);

)

return0;

)

/*

in:

838920715530029917015865

out:

2

第20頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

*/

皿、數(shù)是

4.1.簡(jiǎn)單求Cnk問題

#include<iostream>

usingnamespacestd;

intmainO{

intn,k,i;

doublesum;

while(cin>>n?k){

if(n==0&&k==0)break;

if(k>n-k)k=n-k;

sum=l;

for(i=l;i<=k;i++){

sum*二(double)(n-k+i)/i*L000000000001;〃必需要乘

)

cout<<(int)sum<<endl;

)

return0;

4.2.巧求階乘位數(shù)

#include<iostream>

#include<cmath>

usingnamespacestd;

constdoublepi=acos(-l.0);//NOTES:pi

constdoublee=

2.71828182845904523536028747135266249775724709369995957;

intmainO

{

longlongn,tt;

cin?tt;

while(tt--)

(

cin?n;

longlongans=(longlong)

((double)loglO(sqrt(2*pi*n))+n*logl0(n/e))+l;

cout<<ans<<endl;

)

return0;

第21頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

4.3.線性算法求素?cái)?shù)

constintMAX=10000000;〃求⑵MAX]間的素?cái)?shù)

boolisprime[MAX+l];

intprime[MAX];〃保存素?cái)?shù)

〃返回素?cái)?shù)表元素總數(shù)

intgetprime(){

inti,j,pnum=0;

//memset(isprime,0,sizeof(isprime));

for(i=2;i<=MAX;i++){

if(!isprimeti])

prime[pnum++]=i;

for(j=0;j<pnum&&prime[j]*i<=MAX;j++){

isprime[prime[j]*i]=l;

if(i%prime[j]==0)break;

)

)

returnpnum;

)

五、其他

5.1.采用位操作遞歸求解示例

#include<iostream>

#include<cstdio>

usingnamespacestd;

unsignedshortin[50001],ste;/*用16位的ste保存16種狀態(tài)*/

unsignedshortpower[]=

{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768);

intn,m,maxnum,i,j;

voiddfs(ints,intcount){

if(count>maxnum)maxnum=count;

for(i=s;i<m;i++){

if(!(ste&in[i])){/*如果相與為0,說明材料未被使用*/

ste=ste|in[i];

dfs(i+1,count+1);

ste=ste&(^in[i]);

}

)

)

intmain(){

第22頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

inttn,t;

while(scanf(zz%d%d，/,&n,&m)!=E0F){

if(n==0||m==0){

printf(〃0\n〃)；

continue;

)

for(i=0;i<m;i++){

scanf("%d”,&tn);

in[i]=0;

for(j=l;j<=tn;j++){

scanf("%d",&t);

/*材料編號(hào)降為從0開始，防止益處*/

in[i]=in[i]|power[t-l];

)

)

ste=0;maxnum=0;

dfs(O,0);

printf("%d\n",maxnum);

)

return0;

)

5.2.Stack和Queue用法

#include<iostream>

#include<stack>

#include<queue>

usingnamespacestd;

intmain(){

stack<int>s;

queue<int>q;

inta[]={l,2,3,4);

/*加入*/

for(inti=0;i<4;i++){

s.push(a[i]);

q.push(a[i]);

)

/*讀取stack*/

cout<<z，stack-size://<<s.size()?endl;

for(inti=0;i<4;i++){

cout<<s.top()<<z/"\

s.pop();

}

cout<<endl<<，/queue-size:，z?q.size()<<endl;

第23頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

/*讀取queue*/

cout<<，，front:〃<<q?front()〈〈“back:〃<<q.back()<<endl;

for(inti=0;i<4;i++){

cout?q.front()?z/;

q.pop();

)

cout<<endl;

return0;

)

5.3.map使用詳解

#include<iostream>

#include<map>

#include<string>

#include<iterator>

usingnamespacestd;

intmain(){

map<string,int>m;

map<string,int>::iteratorp;

map<string,int>::reverse_iteratorq;

m[〃bd〃]=2;m[〃ba〃]=1;m[〃aa〃]=3;m[〃bd〃]=4;

〃按從小到大遍歷

for(p=m.begin();p!=m.end();p++){〃注意不能使用p<m.end()

cout<<p->first<<，z，z<<p->second<<endl;

)

〃按從大到小遍歷

for(q=m.rbegin();q!=m.rend();q++){

cout<<q->first<<，/zz<<q->second<<endl;

)

m.erase(m.begin());

cout<<m.size()<<endl;

〃清楚全部

m.clear();

cout<<m.empty()<<endl;

return0;

)

5.4.字典樹建立與查找

#include<iostream>

#include<cstring>

#include<cstdio>

第24頁(yè)

哈嘻嘟-浙江省第七屆程序設(shè)計(jì)-2010-4-17

SdefineM26

usingnamespacestd;

intii;〃只在Tree中使用

structTree{

Tree*next[M];

intval;

Tree(){

for(ii=O;ii<M;ii++){

next[ii]=0;

)

val=0;

)

^TreeO(

for(ii=0;ii<M;ii++){

delete(next[ii]);

}

)

}；

intmain(){

charword[20];

intlen,i,j,count;

Tree*root=newTree;

Tree*p;

〃建立字典樹過程

while(gets(word)){

if(strcmp(word,〃〃)==0)break;

len=strlen(word);