第一篇：ACM 篩素?cái)?shù)總結(jié)

【總結(jié)】關(guān)于求素?cái)?shù)的說【兩種篩法】（學(xué)習(xí)小結(jié)，請無視）

素?cái)?shù)大家都很熟了，不多說了，這里只想說一下求素?cái)?shù)。

當(dāng)然先是唯一素因子分解定理：合數(shù)a僅能以一種方式，寫成如下的乘積形式：a=p1e1p2e2…prer 其中pi為素?cái)?shù)，p1

對于一個(gè)整數(shù)n，當(dāng)其在 小于sqrt（n）范圍里有一個(gè)約數(shù)，那么必然在 大于sqrt（n)的范圍里有對應(yīng)的另一個(gè)Eratosthenes（埃拉托斯特尼篩法）都是到 sqrt（n）的范圍。①。試除法判素?cái)?shù)

對于大于1的正整數(shù)a，如果a具有小于或等于sqrt（a）的素因子，則a為合數(shù)，否則a為素?cái)?shù)。

因此，可用區(qū)間[2,sqrt(a)]內(nèi)的數(shù)去試除a，只要有一個(gè)數(shù)能整除a，則a為合數(shù)，否則a為素?cái)?shù)。這種判斷素復(fù)雜度O(sqrt(n)).IsPrime(a)for(i=2;i*i<=a;i++)if(a%i==0)return a為合數(shù)

return a為素?cái)?shù)

②。Sieve Of Eratosthenes（埃拉托斯特尼篩法）可以篩出2~n 范圍里的所有素?cái)?shù)。

1)將所有候選數(shù)2~n放入篩中;2)找出篩中最小數(shù)P，P一定為素?cái)?shù)。

3)宣布P為素?cái)?shù)，并將P的所有倍數(shù)從篩中篩去;4)重復(fù)2)至3)直到篩空.其實(shí)，當(dāng)P>sqrt(n)時(shí)篩中剩下的數(shù)就已經(jīng)都是素?cái)?shù)了。//用數(shù)組prime[MAXN]記錄是否為素?cái)?shù)； //prime[i]為0表示i為素?cái)?shù)，否則為合數(shù) int prime[MAXN]={0};for(i=2;i*i<=n;i++){ if(prime[i]==0){ for(j=i+i;j<=n;j+=i)prime[j]=1;} } ③。線性篩法

對于Sieve Of Eratosthenes，普通的篩法如果是一個(gè)合數(shù)，那么會(huì)被多次篩掉，比如6,當(dāng)2作為素?cái)?shù)時(shí)篩掉一線性篩法保證所有合數(shù)只被篩掉一次

具體詳見《ftfish利用積性函數(shù)的優(yōu)化》，講到了 積性函數(shù)（對于正整數(shù)n的一個(gè)算術(shù)函數(shù)f(n)，當(dāng)中f(1)=1且稱它為積性函數(shù)。）

for(int i = 2;i < maxn;i ++){ if(!fg[i])prim[np++] = i;//如果沒被篩掉，那么就是素?cái)?shù)

for(int j = 0;j < np && i*prim[j] < maxn;j ++){ //注意i不是素?cái)?shù)的時(shí)候也篩

fg[i*prim[j]] = 1;if(i % prim[j] == 0)break;//這一步保證了篩法是線性的，這是整個(gè)算法的關(guān)鍵

} } 摘：

利用了每個(gè)合數(shù)必有一個(gè)最小素因子。

每個(gè)合數(shù)僅被它的最小素因子篩去正好一次。所以為線性時(shí)間。代碼中體現(xiàn)在：

if(i%prime[j]==0)break;prime數(shù)組 中的素?cái)?shù)是遞增的,當(dāng) i 能整除 prime[j]，那么 i*prime[j+1] 這個(gè)合數(shù)肯定被 prime[j] 乘以某個(gè)數(shù)篩因?yàn)閕中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素?cái)?shù)同理。所以不用篩下去了。在滿足i%pr[j]==0這個(gè)條件之前以及第一次滿足改條件時(shí),pr[j]必定是pr[j]*i的最小因子。

第二篇：ACM賽后總結(jié)

賽后總結(jié)

雖然已經(jīng)是大二第二學(xué)期了，這卻是我的第一真正的ACM比賽經(jīng)歷，賽后感覺自己水平很差，感覺很不好，或許只有受到了了打擊，才會(huì)有成長，也只有在一次次的打擊中吸取經(jīng)驗(yàn)，成為自己前進(jìn)的動(dòng)力。

這次比賽總結(jié)起來發(fā)現(xiàn)了我們的好多不足之處，第一個(gè)就是我們經(jīng)驗(yàn)的缺失，畢竟是我們第一次參加這樣的比賽，還有就是對做題順序的把握不好，對題目難易程度判斷不準(zhǔn)確，如果做一個(gè)題發(fā)現(xiàn)思路錯(cuò)了，我們應(yīng)該要及時(shí)改變思路，跳過去，先去做下面容易的題，等回過頭來在做，要用盡量短的時(shí)間把我們知道做的題做出來，有些題，我們有思路，不敢保證完全做出來，就放到后面再去做，還有就是比賽的時(shí)候心態(tài)不好，中間做的時(shí)候就比較焦急，這樣對自己的思路也會(huì)有影響，要調(diào)節(jié)好自己的情緒，還有就是要及時(shí)改變策略，多看榜，看到有很多人a的題目，我們肯定要去看一下，一開始我們就應(yīng)該把題目全部都看一遍，最重要的是我們的實(shí)力還是不行，對于有些簡單的題目還是不夠熟練，思路不夠清晰，下階段要進(jìn)一步有針對的加強(qiáng)訓(xùn)練！

比賽結(jié)束，我們真的是百感交集，有過遺憾，有過不甘心，有過失望，本來這次比賽應(yīng)該是很好拿獎(jiǎng)的，但最終我們還是與獎(jiǎng)狀擦肩而過，可能與經(jīng)驗(yàn)的缺乏有關(guān)，我想更多的應(yīng)該還是實(shí)力的差距，自己的實(shí)力不行，做什么都是白搭。所幸的是，我們明年還有一次機(jī)會(huì)，再努力一年，我想我們明年再戰(zhàn)的時(shí)候，一定可以取得一個(gè)很好的成績。

14物聯(lián)網(wǎng) 賈文彪

第三篇：新篩總結(jié)

新生兒疾病篩查工作總結(jié)(產(chǎn)科)

新生兒疾病篩查是一項(xiàng)減少嬰幼兒死亡和兒童殘疾，提高人口素質(zhì)的公共衛(wèi)生舉措，對提高人口素質(zhì)、家庭幸福、社會(huì)和諧以及經(jīng)濟(jì)社會(huì)發(fā)展都有非常重要的意義。新生兒遺傳病篩查以及聽力篩查作為了解新生兒的兩項(xiàng)重要篩查項(xiàng)目，在產(chǎn)科工作中有著重要的地位。

結(jié)合實(shí)際工作情況，現(xiàn)將我院新生兒疾病篩查工作的落實(shí)以及進(jìn)展情況作如下總結(jié)：

1、疾病篩查工作的學(xué)習(xí)情況

自2011年5月份起，我院先后組織相關(guān)人員參加了由市婦幼保健院組織的新生兒疾病篩查相關(guān)知識和技能培訓(xùn)，認(rèn)真學(xué)習(xí)，仔細(xì)筆記，回來后與全科同事共同學(xué)習(xí)，分享經(jīng)驗(yàn)，研究重點(diǎn)，讓相關(guān)崗位人員對于新生兒疾病篩查工作有了更加全面的認(rèn)識，并能夠進(jìn)行實(shí)際的操作，把自己的本職工作干好。隨著理論知識的學(xué)習(xí)，技術(shù)規(guī)范的操作以及熟練進(jìn)行信息錄入，每一位產(chǎn)科工作人員從思想上更加重視該項(xiàng)工作，爭取做到百分百合格。

2、相關(guān)系統(tǒng)的操作要點(diǎn)以及注意事項(xiàng)

具體到實(shí)際的新生兒疾病篩查工作內(nèi)容，可總結(jié)如下幾個(gè)方面：首先，做好疾病篩查的宣教工作。在血片采集前，將新生兒疾病篩查的目的、意義、篩查病種、方法以及費(fèi)用等情況，如實(shí)告之新生兒監(jiān)護(hù)人并獲得書面同意。其次，認(rèn)真填寫采血卡片，并由監(jiān)護(hù)人認(rèn)真核對確保信息真實(shí)無誤；血片采集時(shí)，堅(jiān)持一人一針一濾紙，嚴(yán)格無菌技術(shù)做到血片無污染，無滲血環(huán)，確保新生兒出生后72h7天之內(nèi)，充分哺乳6次以上采集。另外，特殊情況延期采血者，簽訂延期通知單，并交代具體的注意事項(xiàng)，在規(guī)定時(shí)間內(nèi)，送檢血片并據(jù)實(shí)進(jìn)行信息錄入。對可疑陽性病例協(xié)助篩查中心及時(shí)通知復(fù)查，以防延誤疾病，同時(shí)做好資料備案。

3、疾病篩查的信息化管理與網(wǎng)上錄入

自疾病篩查實(shí)行網(wǎng)上信息化統(tǒng)一管理后，對我院新生兒逐一進(jìn)行網(wǎng)上信息錄入，以便于全市新生兒信息共享與統(tǒng)一管理。通過全科工作人員的耐心宣教，讓每一位新生兒監(jiān)護(hù)人都能夠自覺接受疾病篩查，配合相關(guān)人員的工作，達(dá)到零拒篩的目標(biāo)。

疾病篩查作為一項(xiàng)十分重要的護(hù)理工作，肯定存在這樣或者那樣的問題。結(jié)合我們的具體工作，現(xiàn)就疾病篩查工作遇到的問題以及問題解決方法作如下探討：

首先，從實(shí)際工作來看，存在著“宣教難，全憑嘴”的尷尬，不僅影響效率，也缺乏可信度；對于這個(gè)問題，一是加強(qiáng)業(yè)務(wù)學(xué)習(xí)，總結(jié)宣教方法，改善宣教方式；第二可以依托市婦幼系統(tǒng)，印制簡單、精美又便于理解的畫冊或者掛畫，更加直觀的宣導(dǎo)給新生兒父母及家人，直至成為人們的常識。

其次，隨著網(wǎng)上錄入信息的實(shí)行，加大了相關(guān)醫(yī)護(hù)人員的工作量，如何盡快的完成工作，除了找方法，總結(jié)經(jīng)驗(yàn)外，最起碼的網(wǎng)絡(luò)與硬件配備也應(yīng)到位，這是更加出色完成工作的基礎(chǔ)，也是我院邁向高等級醫(yī)院的必備設(shè)施，對此理應(yīng)優(yōu)先投入；

再次，以我院的實(shí)力與地位，當(dāng)依托相關(guān)衛(wèi)生部門，配備更加強(qiáng)大的人員、資源，逐步的壯大我們產(chǎn)科的隊(duì)伍，增強(qiáng)我院在產(chǎn)科護(hù)理這一塊的作用，達(dá)到全市領(lǐng)先的目標(biāo)。只有我們每一個(gè)科室發(fā)展了，我院才能夠取得本質(zhì)的發(fā)展與壯大。

隨著廣大人民群眾物質(zhì)和文化生活水平的不斷提高，人們對于兒童的關(guān)注與投入進(jìn)一步增加。新生兒疾病篩查作為一項(xiàng)重要的防護(hù)工作，理應(yīng)取得全社會(huì)的關(guān)注與支持；同時(shí)，也應(yīng)該作為產(chǎn)科工作中十分重要的一項(xiàng)工作來做。宏偉的目標(biāo)總歸只是一種理論的期望，隨著2013年的到來，作為產(chǎn)科的一員，我們首先要做的，還是從最基本的工作入手，多學(xué)習(xí)，看資料，勤培訓(xùn)，豐富理論知識的同時(shí)，加強(qiáng)技術(shù)的交流，真正提高崗位技能，做到讓千萬父母與家人的百分百滿意。真誠期待我與產(chǎn)科、與我院的共同成長！

第四篇：ACM程序設(shè)計(jì)培訓(xùn)總結(jié)

C語言篇

學(xué)生信息管理系統(tǒng) #include “stdio.h” #include “stdlib.h” #define LEN sizeof(struct student)struct student

/*結(jié)構(gòu)體類型*/ { int num;float score;struct student *next;};int n=0;

/*記錄鏈表結(jié)點(diǎn)個(gè)數(shù)*/ struct student *head;

/*鏈表頭指針*/ void menu();

/*DOS菜單函數(shù)*/ struct student *creat();

/*鏈表創(chuàng)建函數(shù)*/ void prin(struct student *head);

/*鏈表輸出函數(shù)*/ struct student *insert(struct student *head);/*鏈表添加函數(shù)*/ struct student *del(struct student *head);

/*鏈表刪除函數(shù)*/ struct student * paixu(struct student *head);/*排序函數(shù)*/ struct student *xiugai(struct student *head);/*修改函數(shù)*/ void seach();

void menu(){

int i;

printf(“n t 1t創(chuàng)建學(xué)生表n”);printf(“n t 2t添加學(xué)生數(shù)據(jù)n”);printf(“n t 3t顯示學(xué)生信息n”);printf(“n t 4t排序?qū)W生記錄n”);printf(“n t 5t修改學(xué)生記錄n”);

printf(“n t 6t刪除學(xué)生記錄n”);

printf(“n t 7t查找學(xué)生記錄n”);printf(“n t 0t退出n”);

printf(“n t 請輸入你的選擇（0-4）：”);

scanf(“%d”,&i);switch(i){

case 1: head=creat();break;

case 2: head=insert(head);break;

case 3: prin(head);break;

case 4: head=paixu(head);break;

case 5: head=xiugai(head);break;

case 6: head=del(head);break;

case 7: seach();break;

case 0: exit(0);

default:printf(“n選擇錯(cuò)誤！請按照下面提示選擇?！?;}

menu();} void main(){

menu();}

struct student *creat()

/*此函數(shù)帶回一個(gè)指向鏈表頭的指針*/ {

struct student *head,*p1,*p2;n=0;head=NULL;p1=(struct student *)malloc(LEN);/*創(chuàng)建第一個(gè)結(jié)點(diǎn)*/ printf(“請輸入第1個(gè)學(xué)生學(xué)號及成績（學(xué)號與成績以空格隔開，'0 0'結(jié)束）:”);scanf(“%d%f”,&p1->num,&p1->score);p1->next=NULL;while(p1->num!=0)

/*應(yīng)該將結(jié)點(diǎn)加入鏈表*/ { ++n;if(n==1)head=p1;

/*是第一個(gè)結(jié)點(diǎn),作表頭*/ else p2->next=p1;

/*不是第一個(gè)結(jié)點(diǎn),作表尾*/ p2=p1;p1=(struct student*)malloc(LEN);/*開辟下一個(gè)結(jié)點(diǎn)*/ printf(“請輸入第%d個(gè)學(xué)生學(xué)號及成績（學(xué)號與成績以空格隔開，'0 0'結(jié)束）:”,n+1);scanf(“%d%f”,&p1->num,&p1->score);p1->next=NULL;} free(p1);

/*釋放最后一個(gè)結(jié)點(diǎn)所占的內(nèi)存*/ return(head);/*返回鏈表的頭指針*/ }

void prin(struct student *head)

/*鏈表輸出函數(shù)*/ {

struct student *p;

if(head==NULL)

printf(“鏈表不存在，請先創(chuàng)建！”);

else

{

p=head;

for(;p!=NULL;)

{

printf(“%d號學(xué)生成績：%fn”,p->num,p->score);

p=p->next;

}

} }

struct student *insert(struct student *head){ struct student*p0,*p1,*p2;int i;char ch='y';p1=head;

/*p1指向第一個(gè)結(jié)點(diǎn)*/

if(head==NULL)printf(“鏈表不存在，請先創(chuàng)建！”);else

{

while(ch=='Y'||ch=='y'){ p0=(struct student*)malloc(LEN);

printf(“請輸入新結(jié)點(diǎn)的數(shù)據(jù)，輸入'0 0'放棄插入：”);

scanf(“%d%f”,&p0->num,&p0->score);p0->next=NULL;

if(p0->num==0)

{ free(p0);

}

else

{ printf(“輸入結(jié)點(diǎn)插入的位置：”);

scanf(“%d”,&i);

if(i==0)

/*作為表頭*/

{

p0->next=head;

head=p0;

}

else

{

while(i>1&&(p1!=NULL))

{

p2=p1;

p1=p1->next;

i--;

}

/*找插入點(diǎn)*/

p0->next=p1;

/*插到p2指向的結(jié)點(diǎn)之后*/

p2->next=p0;

}

++n;

/*結(jié)點(diǎn)數(shù)加1*/

}

printf(“n數(shù)據(jù)添加成功！是否繼續(xù)（y或Y繼續(xù),任意鍵退出):”);

getchar();

ch=getchar();} } return(head);}

struct student *del(struct student *head)/*形參num為需刪除的學(xué)號*/ { int i;

char ch='y';struct student *p1,*p2;

while(ch=='Y'||ch=='y'){ if(head==NULL){ printf(“n鏈表不存在!n”);break;

/*鏈表為空*/ } else {

p1=head;

/*從頭結(jié)點(diǎn)開始查找*/

printf(“請輸入要?jiǎng)h除的學(xué)生學(xué)號：”);

scanf(“%d”,&i);

getchar();

while(i!=p1->num&&p1->next!=NULL)

/*p1指向的不是所要找的結(jié)點(diǎn),并且沒有到表尾*/

{

p2=p1;

p1=p1->next;

/*后移一個(gè)結(jié)點(diǎn)*/

}

if(i==p1->num)

/*找到了需刪除的結(jié)點(diǎn)*/

{

if(p1==head)

/*p1指向的是頭結(jié)點(diǎn)*/

head=p1->next;/*第二個(gè)結(jié)點(diǎn)成為新的頭結(jié)點(diǎn)*/

else

p2->next=p1->next;/*后繼結(jié)點(diǎn)的地址賦給前一結(jié)點(diǎn)*/

printf(“%d號學(xué)生已經(jīng)被刪除n”,i);

free(p1);

/*釋放結(jié)點(diǎn)所占的內(nèi)存*/

n--;

/*鏈表結(jié)點(diǎn)數(shù)減1*/

printf(“n數(shù)據(jù)刪除成功！是否繼續(xù)（y或Y繼續(xù),任意鍵退出):”);

ch=getchar();

}

else

{

printf(“%d 號學(xué)生不存在或已經(jīng)被刪除!n”,i);/*找不到刪除結(jié)點(diǎn)*/

printf(“n是否繼續(xù)（y或Y繼續(xù),任意鍵退出):”);

ch=getchar();

} }

}

return(head);}

struct student * paixu(struct student *head)

/*排序函數(shù)*/ {

struct student *p0,*p1,*p2,*pt;

/*p0代表p1的前個(gè)結(jié)點(diǎn)*/

/*p1代表當(dāng)前正排序的結(jié)點(diǎn)*/

/*p2用來取p1后面的每個(gè)結(jié)點(diǎn)來與P1比較*/ int i;

/*i=1表示頭結(jié)點(diǎn)排序*/ if(head==NULL)

{

printf(“鏈表不存在，先創(chuàng)建！n”);

}

else if(n>1)

{

p0=p2=p1=head;

for(i=1;p1->next!=NULL;i++)

/*選擇法排序算法*/

{

for(;p2->next!=NULL;)

if(p1->num>p2->next->num)

{

pt=p1;

p1=p2->next;

p2->next=p1->next;

p1->next=pt;

}

else p2=p2->next;

/*若不要交換，則p2指針后移*/

if(i==1)p0=head=p1;

/*對第一個(gè)結(jié)點(diǎn)排序時(shí)處理*/

else

/*其他結(jié)點(diǎn)排序時(shí)處理*/

{ p0->next=p1;

p0=p1;

}

p2=p1->next;

p1=p1->next;

}

prin(head);

/*調(diào)用輸出函數(shù)*/

}

return(head);}

struct student *xiugai(struct student *head)

/*修改函數(shù)*/ { struct student *p;

int m;

printf(“n請輸入要修改數(shù)據(jù)的學(xué)號(0退出)：”);

scanf(“%d”,&m);

while(m!=0)

{ p=head;

for(;p->num!=m&&p->next!=NULL;)

p=p->next;

if(p->num==m)

{ printf(“n請輸入新的數(shù)據(jù)(學(xué)號 成績)：”);

scanf(“%d%f”,&p->num,&p->score);

printf(“n修改成功！”);

printf(“n若繼續(xù)修改，請輸入學(xué)號(0退出)：”);

}

else

printf(“n該學(xué)生不存在，請重新輸入學(xué)號(0退出)：”);

scanf(“%d”,&m);

}

return(head);}

void xuehao(struct student *head)

/*按學(xué)號查找函數(shù)*/ { struct student *p;

int m,leap;

printf(“n請輸入要查找的學(xué)號：”);

scanf(“%d”,&m);

while(m!=0)

{ p=head;

leap=0;

for(;p->next!=NULL;)

{

if(p->num==m)

{printf(“n你要查找的學(xué)生信息為： 學(xué)號 %d 成績 %fn”,p->num,p->score);

leap=1;

}

p=p->next;

}

if(leap==1)

printf(“n若繼續(xù)查找，請輸入學(xué)號(0退出)：”);

else

printf(“n該學(xué)生不存在，請重新輸入學(xué)號(0退出)：”);

scanf(“%d”,&m);

}

}

void chengji(struct student *head)

/*按成績查找函數(shù)*/ { struct student *p;

int leap;

float m;

printf(“n請輸入要查找的成績：”);

scanf(“%f”,&m);

while(m>=0)

{ p=head;

leap=0;

for(;p->next!=NULL;)

{

if(p->num==m)

{printf(“n你要查找的學(xué)生信息為： 學(xué)號 %d 成績 %fn”,p->num,p->score);

leap=1;

}

p=p->next;

}

if(leap==1)

printf(“n若繼續(xù)查找，請輸入成績(負(fù)數(shù)退出)：”);

else

printf(“n該學(xué)生不存在，請重新輸入成績(負(fù)數(shù)退出)：”);

scanf(“%f”,&m);

}

}

void seach()

/*查找子菜單*/ {

int i;

printf(“n t 1 按學(xué)號查找n”);printf(“n t 2 按成績查找n”);printf(“n t 0 返回上級菜單n”);printf(“n t

請輸入你的選擇：”);scanf(“%d”,&i);switch(i){

case 1: xuehao(head);break;

case 2: chengji(head);break;

case 0: menu();break;

default:printf(“n選擇錯(cuò)誤！請按照下面提示選擇。”);} seach();}

數(shù)據(jù)結(jié)構(gòu)篇

//huffman.cpp 求Huffman編碼 #define UNIT_MAX 65535

//函數(shù)結(jié)果狀態(tài)代碼

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define INFEASIBLE-1 #define OVERFLOW-2

#include #include #include #include

//Status 是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼 typedef int Status;

//Huffman樹＆Huffman編碼的存儲(chǔ)表示

typedef struct{ unsigned int weight;unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)Huffman樹 typedef char **HuffmanCode;/* int min(HuffmanTree t,int i){ //函數(shù)void select()調(diào)用

int j,flag;unsigned int k=UNIT_MAX;for(j=1;j<=i;j++)

if(t[j].weight

{

k=t[j].weight;

flag=j;

} t[flag].parent=1;

return flag;}

void select(HuffmanTree t,int i,int &s1,int &s2){ //s1為最小的兩個(gè)值中序號小的那個(gè)

int j;s1=min(t,i);s2=min(t,i);if(s1>s2){

j=s1;

s1=s2;

s2=j;} } */

void select(HuffmanTree t,int i,int &s1,int &s2){ int j;s1=0;s2=0;

unsigned int small1,small2;

small1=UNIT_MAX;small2=UNIT_MAX;

for(j=1;j<=i;j++)

//選出兩個(gè)權(quán)值最小的根結(jié)點(diǎn)

{

if(t[j].parent==0)

if(t[j].weight

{

small2=small1;

//改變最小權(quán)、次小權(quán)及對應(yīng)的位置

small1=t[j].weight;

s2=s1;

s1=j;

}

else

{

if(t[j].weight

{

small2=t[j].weight;//改變次小權(quán)及位置

s2=j;

}

} } }

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){ // 算法6.12 // w存放n個(gè)字符的權(quán)值(均>0)，構(gòu)造哈夫曼樹HT，// 并求出n個(gè)字符的哈夫曼編碼HC int m,i,s1,s2;unsigned c,cdlen;

HuffmanTree p;char *cd;

if(n<=1)return;m = 2 * n1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs.Every number must be connected to exactly one another.And, no two segments are allowed to intersect.It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right? 卡特勒數(shù)

import java.math.*;import java.util.*;public class Main{

public static void main(String args[])

{

Scanner as=new Scanner(System.in);

int n,i;

BigDecimal[] a=new BigDecimal[101];

a[0]=BigDecimal.valueOf(1);

for(i=1;i<101;i++)

{

a[i]=a[i-1].multiply(BigDecimal.valueOf(4*i-2));

a[i]=a[i].divide(BigDecimal.valueOf(i+1));

}

while(i>0)

{

n=as.nextInt();

if(n==-1)

break;

System.out.println(a[n]);

}

} }

篩選法 七夕節(jié)

除了篩選素?cái)?shù)外，還能篩選因子（倍數(shù)的運(yùn)用）#include #define max 500000 int a[max+1]={0};int main(){ int t,n,i,j;a[0]=a[1]=0;for(i=1;i<=max/2;i++)

for(j=i+i;j<=max;j+=i)

a[j]+=i;

scanf(“%d”,&t);

while(t--)

{

scanf(“%d”,&n);

printf(“%dn”,a[n]);

}

return 0;}

母函數(shù)

Ignatius and the Princess III

“Well, it seems the first problem is too easy.I will let you know how foolish you are later.” feng5166 says.“The second problem is, given an positive integer N, we define an equation like this: N=a[1]+a[2]+a[3]+...+a[m];a[i]>0,1<=m<=N;My question is how many different equations you can find for a given N.For example, assume N is 4, we can find: 4 = 4;4 = 3 + 1;4 = 2 + 2;4 = 2 + 1 + 1;4 = 1 + 1 + 1 + 1;so the result is 5 when N is 4.Note that ”4 = 3 + 1“ and ”4 = 1 + 3“ is the same in this problem.Now, you do it!” Input The input contains several test cases.Each test case contains a positive integer N(1<=N<=120)which is mentioned above.The input is terminated by the end of file.Output For each test case, you have to output a line contains an integer P which indicate the different equations you have found.#include using namespace std;const int lmax=10000;int c1[lmax+1],c2[lmax+1];int main(){

int n,i,j,k;

while(cin>>n)

{

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

{

c1[i]=0;

c2[i]=0;

}

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

c1[i]=1;

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

{

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

for(k=0;k+j<=n;k+=i)

{

c2[j+k]+=c1[j];

}

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

{

c1[j]=c2[j];

c2[j]=0;

}

}

cout<

}

return 0;} 貪心算法（排序函數(shù)）#incluide Int cmp(const void *a,const void *b){ return *(int *)a-*(int *)b;} Qsort(a[0],n,sizeof(a[0]),cmp);

第五篇：ACM算法總結(jié)——超有用!

初期: 一.基本算法:

(1)枚舉.(poj1753,poj2965)

(2)貪心(poj1328,poj2109,poj2586)

(3)遞歸和分治法.(4)遞推.(5)構(gòu)造法.(poj3295)

(6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.圖算法:

(1)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷.(2)最短路徑算法(dijkstra,bellman-ford,floyd,heap+dijkstra)

(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)

(3)最小生成樹算法(prim,kruskal)

(poj1789,poj2485,poj1258,poj3026)

(4)拓?fù)渑判?poj1094)

(5)二分圖的最大匹配(匈牙利算法)(poj3041,poj3020)

(6)最大流的增廣路算法(KM算法).(poj1459,poj3436)三.數(shù)據(jù)結(jié)構(gòu).(1)串(poj1035,poj3080,poj1936)

(2)排序(快排、歸并排(與逆序數(shù)有關(guān))、堆排)(poj2388,poj2299)

(3)簡單并查集的應(yīng)用.(4)哈希表和二分查找等高效查找法(數(shù)的Hash,串的Hash)

(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)

(5)哈夫曼樹(poj3253)

(6)堆

(7)trie樹(靜態(tài)建樹、動(dòng)態(tài)建樹)(poj2513)四.簡單搜索

(1)深度優(yōu)先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)

(2)廣度優(yōu)先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

(3)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.動(dòng)態(tài)規(guī)劃

(1)背包問題.(poj1837,poj1276)

(2)型如下表的簡單DP(可參考lrj的書 page149):

1.E[j]=opt{D+w(i,j)}(poj3267,poj1836,poj1260,poj2533)

2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij}(最長公共子序列)

(poj3176,poj1080,poj1159)

3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優(yōu)二分檢索樹問題)六.數(shù)學(xué)

(1)組合數(shù)學(xué):

1.加法原理和乘法原理.2.排列組合.3.遞推關(guān)系.(POJ3252,poj1850,poj1019,poj1942)

(2)數(shù)論.1.素?cái)?shù)與整除問題

2.進(jìn)制位.3.同余模運(yùn)算.(poj2635, poj3292,poj1845,poj2115)

(3)計(jì)算方法.1.二分法求解單調(diào)函數(shù)相關(guān)知識.(poj3273,poj3258,poj1905,poj3122)七.計(jì)算幾何學(xué).(1)幾何公式.(2)叉積和點(diǎn)積的運(yùn)用(如線段相交的判定,點(diǎn)到線段的距離等).(poj2031,poj1039)

(3)多邊型的簡單算法(求面積)和相關(guān)判定(點(diǎn)在多邊型內(nèi),多邊型是否相交)

(poj1408,poj1584)

(4)凸包.(poj2187,poj1113)中級: 一.基本算法:

(1)C++的標(biāo)準(zhǔn)模版庫的應(yīng)用.(poj3096,poj3007)

(2)較為復(fù)雜的模擬題的訓(xùn)練(poj3393,poj1472,poj3371,poj1027,poj2706)二.圖算法:

(1)差分約束系統(tǒng)的建立和求解.(poj1201,poj2983)

(2)最小費(fèi)用最大流(poj2516,poj2516,poj2195)

(3)雙連通分量(poj2942)

(4)強(qiáng)連通分支及其縮點(diǎn).(poj2186)

(5)圖的割邊和割點(diǎn)(poj3352)

(6)最小割模型、網(wǎng)絡(luò)流規(guī)約(poj3308,)三.數(shù)據(jù)結(jié)構(gòu).(1)線段樹.(poj2528,poj2828,poj2777,poj2886,poj2750)

(2)靜態(tài)二叉檢索樹.(poj2482,poj2352)

(3)樹狀樹組(poj1195,poj3321)

(4)RMQ.(poj3264,poj3368)

(5)并查集的高級應(yīng)用.(poj1703,2492)

(6)KMP算法.(poj1961,poj2406)四.搜索

(1)最優(yōu)化剪枝和可行性剪枝

(2)搜索的技巧和優(yōu)化(poj3411,poj1724)

(3)記憶化搜索(poj3373,poj1691)

五.動(dòng)態(tài)規(guī)劃

(1)較為復(fù)雜的動(dòng)態(tài)規(guī)劃(如動(dòng)態(tài)規(guī)劃解特別的施行商問題等)

(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)

(2)記錄狀態(tài)的動(dòng)態(tài)規(guī)劃.(POJ3254,poj2411,poj1185)

(3)樹型動(dòng)態(tài)規(guī)劃(poj2057,poj1947,poj2486,poj3140)六.數(shù)學(xué)

(1)組合數(shù)學(xué):

1.容斥原理.2.抽屜原理.3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).4.遞推關(guān)系和母函數(shù).(2)數(shù)學(xué).1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)

2.概率問題.(poj3071,poj3440)

3.GCD、擴(kuò)展的歐幾里德(中國剩余定理)(poj3101)

(3)計(jì)算方法.1.0/1分?jǐn)?shù)規(guī)劃.(poj2976)

2.三分法求解單峰(單谷)的極值.3.矩陣法(poj3150,poj3422,poj3070)

4.迭代逼近(poj3301)

(4)隨機(jī)化算法(poj3318,poj2454)

(5)雜題.(poj1870,poj3296,poj3286,poj1095)七.計(jì)算幾何學(xué).(1)坐標(biāo)離散化.(2)掃描線算法(例如求矩形的面積和周長并,常和線段樹或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)

(3)多邊形的內(nèi)核(半平面交)(poj3130,poj3335)

(4)幾何工具的綜合應(yīng)用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高級:

一.基本算法要求:

(1)代碼快速寫成,精簡但不失風(fēng)格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

(2)保證正確性和高效性.poj3434 二.圖算法:

(1)度限制最小生成樹和第K最短路.(poj1639)

(2)最短路,最小生成樹,二分圖,最大流問題的相關(guān)理論(主要是模型建立和求解)

(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446

(3)最優(yōu)比率生成樹.(poj2728)

(4)最小樹形圖(poj3164)

(5)次小生成樹.(6)無向圖、有向圖的最小環(huán)

三.數(shù)據(jù)結(jié)構(gòu).(1)trie圖的建立和應(yīng)用.(poj2778)

(2)LCA和RMQ問題(LCA(最近公共祖先問題)有離線算法(并查集+dfs)和 在線算法

(RMQ+dfs)).(poj1330)

(3)雙端隊(duì)列和它的應(yīng)用(維護(hù)一個(gè)單調(diào)的隊(duì)列,常常在動(dòng)態(tài)規(guī)劃中起到優(yōu)化狀態(tài)轉(zhuǎn)移的 目的).(poj2823)

(4)左偏樹(可合并堆).(5)后綴樹(非常有用的數(shù)據(jù)結(jié)構(gòu),也是賽區(qū)考題的熱點(diǎn)).(poj3415,poj3294)四.搜索

(1)較麻煩的搜索題目訓(xùn)練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

(2)廣搜的狀態(tài)優(yōu)化:利用M進(jìn)制數(shù)存儲(chǔ)狀態(tài)、轉(zhuǎn)化為串用hash表判重、按位壓縮存儲(chǔ)狀態(tài)、雙向廣搜、A*算法.(poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

(3)深搜的優(yōu)化:盡量用位運(yùn)算、一定要加剪枝、函數(shù)參數(shù)盡可能少、層數(shù)不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*算法.(poj3131,poj2870,poj2286)五.動(dòng)態(tài)規(guī)劃

(1)需要用數(shù)據(jù)結(jié)構(gòu)優(yōu)化的動(dòng)態(tài)規(guī)劃.(poj2754,poj3378,poj3017)

(2)四邊形不等式理論.(3)較難的狀態(tài)DP(poj3133)六.數(shù)學(xué)

(1)組合數(shù)學(xué).1.MoBius反演(poj2888,poj2154)

2.偏序關(guān)系理論.(2)博奕論.1.極大極小過程(poj3317,poj1085)

2.Nim問題.七.計(jì)算幾何學(xué).(1)半平面求交(poj3384,poj2540)

(2)可視圖的建立(poj2966)

(3)點(diǎn)集最小圓覆蓋.(4)對踵點(diǎn)(poj2079)八.綜合題.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

Dp狀態(tài)設(shè)計(jì)與方程總結(jié)

1.不完全狀態(tài)記錄

<1>青蛙過河問題

<2>利用區(qū)間dp

2.背包類問題

<1> 0-1背包，經(jīng)典問題

<2>無限背包，經(jīng)典問題

<3>判定性背包問題

<4>帶附屬關(guān)系的背包問題

<5> +-1背包問題

<6>雙背包求最優(yōu)值

<7>構(gòu)造三角形問題

<8>帶上下界限制的背包問題(012背包)

3.線性的動(dòng)態(tài)規(guī)劃問題

<1>積木游戲問題

<2>決斗（判定性問題）

<3>圓的最大多邊形問題

<4>統(tǒng)計(jì)單詞個(gè)數(shù)問題

<5>棋盤分割

<6>日程安排問題

<7>最小逼近問題(求出兩數(shù)之比最接近某數(shù)/兩數(shù)之和等于某數(shù)等等)

<8>方塊消除游戲(某區(qū)間可以連續(xù)消去求最大效益)

<9>資源分配問題

<10>數(shù)字三角形問題

<11>漂亮的打印

<12>郵局問題與構(gòu)造答案

<13>最高積木問題

<14>兩段連續(xù)和最大

<15>2次冪和問題

<16>N個(gè)數(shù)的最大M段子段和

<17>交叉最大數(shù)問題

4.判定性問題的dp(如判定整除、判定可達(dá)性等)

<1>模K問題的dp

<2>特殊的模K問題，求最大(最小)模K的數(shù)

<3>變換數(shù)問題

5.單調(diào)性優(yōu)化的動(dòng)態(tài)規(guī)劃

<1>1-SUM問題

<2>2-SUM問題

<3>序列劃分問題(單調(diào)隊(duì)列優(yōu)化)

6.剖分問題(多邊形剖分/石子合并/圓的剖分/乘積最大)

<1>凸多邊形的三角剖分問題

<2>乘積最大問題

<3>多邊形游戲(多邊形邊上是操作符,頂點(diǎn)有權(quán)值)

<4>石子合并(N^3/N^2/NLogN各種優(yōu)化)

7.貪心的動(dòng)態(tài)規(guī)劃

<1>最優(yōu)裝載問題

<2>部分背包問題

<3>乘船問題

<4>貪心策略

<5>雙機(jī)調(diào)度問題Johnson算法

8.狀態(tài)dp

<1>牛仔射擊問題(博弈類)

<2>哈密頓路徑的狀態(tài)dp <3>兩支點(diǎn)天平平衡問題

<4>一個(gè)有向圖的最接近二部圖

9.樹型dp

<1>完美服務(wù)器問題(每個(gè)節(jié)點(diǎn)有3種狀態(tài))

<2>小胖守皇宮問題

<3>網(wǎng)絡(luò)收費(fèi)問題

<4>樹中漫游問題

<5>樹上的博弈

<6>樹的最大獨(dú)立集問題

<7>樹的最大平衡值問題

<8>構(gòu)造樹的最小環(huán)