第一篇：ACM中WA方面的錯(cuò)誤總結(jié)

1、Int遇到過(guò)的問(wèn)題 簡(jiǎn)介：

int是我們最常用的類(lèi)型之一。如果輸入數(shù)據(jù)是整形，一般都直接用該類(lèi)型來(lái)存放輸入數(shù)據(jù)。

錯(cuò)誤經(jīng)歷：

自己在作Equiptment Box時(shí)，因?yàn)檩斎霐?shù)據(jù)長(zhǎng)、寬均是小于50000的整數(shù)，因此就使用int來(lái)作輸入。這本身沒(méi)有問(wèn)題，但在求其斜邊長(zhǎng)時(shí)，使用的是sqrt（x * x + y * y），表面看是沒(méi)有問(wèn)題，但結(jié)果一直是Wrong Answer。后來(lái)將這一行改為pow((pow(x, 2)+ pow(y,3)), 0.5)，就Accept了！錯(cuò)誤原因：

后來(lái)經(jīng)johnbill和hewei的分析，x，y本身沒(méi)有問(wèn)題，不會(huì)越界，但使用sqrt（x*x +y*y）時(shí)，里面的x*x 和 y*y則會(huì)超出int范圍，造成溢出。而pow會(huì)將參數(shù)自動(dòng)轉(zhuǎn)換為double，就不會(huì)出錯(cuò)。

避免失誤的辦法：

（1）以后均使用pow進(jìn)行運(yùn)算。（習(xí)慣）（2）運(yùn)算時(shí)，注意做強(qiáng)行轉(zhuǎn)換。（比較麻煩）

（3）不管輸入給的類(lèi)型，直接用double來(lái)存儲(chǔ)，就不會(huì)溢出了。這種方法表面看沒(méi)有問(wèn)題，但直到這次比賽，才發(fā)現(xiàn)了一個(gè)很?chē)?yán)重的問(wèn)題！

2、double遇到過(guò)的問(wèn)題 簡(jiǎn)介：

是我們?cè)诮忸}時(shí)，和int一起是最常用的類(lèi)型。錯(cuò)誤經(jīng)歷：

因?yàn)?double上限可達(dá)1.7e308。而一般題目（非大數(shù)運(yùn)算要求）均不可能超過(guò)其限，發(fā)生溢出，所以之后我就在做題時(shí)，凡是遇到結(jié)果有些大時(shí)，均用double類(lèi)型來(lái)保存，來(lái)避免溢出?？雌饋?lái)，這樣比較方便，因?yàn)槲覀冊(cè)诒緳C(jī)上是用VC＋＋，而OnlineJudge是gcc，它們支持的長(zhǎng)整形類(lèi)型不同，一個(gè)是__int64，而一個(gè)是long long；處理格式也不同，I 64u 和 lld。而在這種情況下，“真正”的可以用double的話，那就可以將其統(tǒng)一起來(lái)。但是……昨天比賽C題時(shí)，自己也是這么遞推和用double保存，但一直Wrong Answer。和遞歸能計(jì)算出（太大的數(shù)據(jù)很耗時(shí)）的數(shù)據(jù)相比，都是正確的，不知原因何在。比賽結(jié)束后，和別人結(jié)果對(duì)照了一下，把double改成unsigned long long 就Accept了。錯(cuò)譯原因：

這是因?yàn)椋篸ouble類(lèi)型的精度只有15位??！它的上限可以很大，但只能保證15位的精度！換句話說(shuō)，只能保證15位是正確的。在數(shù)據(jù)（50，50）以后，結(jié)果都在20位以上，前面的位數(shù)是正確的，但后面的幾位就會(huì)出現(xiàn)問(wèn)題了！解決方法：

（1）定義頭文件，在本機(jī)上用__int64，提交時(shí)用long long（2）本機(jī)上使用VAC編譯(J)（奇難用！）

（3）反正絕對(duì)不能使用double來(lái)計(jì)數(shù)，尤其比較大的數(shù)，但可以利用它來(lái)測(cè)試最大數(shù)據(jù)的范圍大小，這樣可以反過(guò)來(lái)幫助我們決定用什么類(lèi)型來(lái)保存。

3、float遇到過(guò)的問(wèn)題

我還記得當(dāng)時(shí)Hunter做area的時(shí)候，各方面都作了考慮，但一直是Wrong Answer。后來(lái)只是把存儲(chǔ)坐標(biāo)的float類(lèi)型改為double，就過(guò)了。原因：

應(yīng)該是float的精度不夠（具體嘛…..大家re），但題目只要求3位小數(shù)也有問(wèn)題……。所以，以后大家要使用浮點(diǎn)數(shù)計(jì)算時(shí)，直接用double，不要考慮使用float。一般內(nèi)存是不會(huì)有問(wèn)題的。

4、4舍5入的問(wèn)題：

在做Lifting the Stone時(shí)，題上要求保留到小數(shù)點(diǎn)兩位，第三位作四舍五入，自己直接用%.02來(lái)打，以為自動(dòng)會(huì)四舍五入。但一直沒(méi)過(guò)。加上處理之后就過(guò)了…….原因：

小數(shù)點(diǎn)后第三位為5時(shí)，會(huì)隨機(jī)的作進(jìn)位處理。解決辦法：

如果題上要求了四舍五入，一定要記得進(jìn)行處理：x = floor(x*100 + 0.5)/100，5、為5時(shí)，后一位奇數(shù)進(jìn)位，偶數(shù)不進(jìn)位： 這個(gè)JohnBIll講過(guò)，一般不會(huì)有這種“浪費(fèi)青春的題…..”。解決辦法：

除了相當(dāng)?shù)撵`活，多試，還需要運(yùn)氣了……

第二篇：ACM錯(cuò)誤提示

http://acm.nankai.edu.cn/user_message.php

F.A.Q.(Chinese)我的程序?yàn)槭裁床荒芫幾g通過(guò)呢？

Online Judge 要求C/C++程序符合Ansi標(biāo)準(zhǔn)：

ANSI 標(biāo)準(zhǔn)和 Microsoft Visual C++ 存在一些不同的地方，比如：

0)main函數(shù)必須聲明為int，也就是 void main()必須變成 int main()

VC同樣可使用int main，只是程序最后需要 return 0。

1)Microsoft Visual C++ 可以將 main 函數(shù)聲明為 void，而 ANSI 中必須為 int main

2)請(qǐng)避免使用如下方式聲明變量i

for(int i=0;i<10;i++)

{

...}

您可以在For 語(yǔ)句之前，進(jìn)行聲明。

3)itoa 不是一個(gè) ANSI 函數(shù)

4)stricmp 不是一個(gè) ANSI 函數(shù)

5)sqrt()的可能用法：sqrt(double(x));//強(qiáng)制轉(zhuǎn)換為double

6)OnlineJudge 中如何使用64位數(shù)？

定義64位數(shù)使用 long long 類(lèi)型，輸出格式串中使用 %lld 表示64位數(shù)。

雖然Free Pascal盡量設(shè)計(jì)得和Turbo Pascal接近，但是由于以下的兩個(gè)原因，兩者之間還是有一些區(qū)別的：

1．Free Pascal是一個(gè)32位的編譯器，而Turbo Pascal只是16位編譯器；

2．Free Pascal是一個(gè)跨平臺(tái)的編譯器，而Turbo Pascal只在windows上使用。

如果你的代碼是遵守ANSI Pascal的，那么代碼從Turbo Pascal移植到Free Pascal是沒(méi)有問(wèn)題的。

下面是在Turbo Pascal上可以使用，但是在Free Pascal就不能使用的一些語(yǔ)言特性：

1．函數(shù)和過(guò)程在使用時(shí)，參數(shù)的類(lèi)型必須和定義時(shí)完全一致。原因是在Free Pascal中添加了函數(shù)重載功能。

2．PROTECTED，PUBLIC，PUBLISHED，TRY，F(xiàn)INALLY，EXCEPT，RAISE成為了關(guān)鍵字，因此不能作為函數(shù)和過(guò)程的名字。

3．FAR，NEAR不再是關(guān)鍵字了。原因是Free Pascal是32位系統(tǒng)，不再需要這些關(guān)鍵字。

4．布爾表達(dá)式不一定要全部進(jìn)行計(jì)算。只要最終結(jié)果已經(jīng)能夠確定，就不再計(jì)算其它還沒(méi)有計(jì)算的部分了。

比如布爾表達(dá)式exp1 AND exp2 AND exp3，如果已知exp1的結(jié)果是false，那么怎么表達(dá)式的結(jié)果肯定是false，exp2和exp3就不用進(jìn)行計(jì)算了。

5．在Free Pascal中，集合中的元素都是4個(gè)字節(jié)長(zhǎng)的。

6．表達(dá)式執(zhí)行的順序是不確定的。比如對(duì)于表達(dá)式a:=g(2)+f(3);不保證g(2)一定在f(3)之前執(zhí)行。

7．如果用Rewrite打開(kāi)文件，那么文件就只能被寫(xiě)入了。如果需要讀取這個(gè)文件，要對(duì)文件執(zhí)行Reset。

8．Free Pascal在程序結(jié)束之前一定要關(guān)閉輸出文件，否則輸出文件可能不能被正確的寫(xiě)入。

9．Free Pascal理論上可以使用4GB的內(nèi)存，因此實(shí)際上幾乎可以使用系統(tǒng)中的所有剩余內(nèi)存（除非賽題中有內(nèi)存限制）。

這是Free Pascal由于32位的編譯器。但是對(duì)于Turbo Pascal來(lái)說(shuō)，由于是16位的編譯器，因此不能定義大小超過(guò)64KB的數(shù)據(jù)類(lèi)型和變量，并且在DOS實(shí)模式下可以使用的內(nèi)存總數(shù)只有640KB。

Online Judge 評(píng)判結(jié)果分別表示什么意思？

當(dāng)你提交的程序被Online Judge評(píng)判完畢后，通常結(jié)果將立刻返回，或者你也可以在“Solutions”頁(yè)看到評(píng)判結(jié)果。

詳細(xì)測(cè)試多數(shù)據(jù)測(cè)試模式下，將顯示出各個(gè)測(cè)試數(shù)據(jù)的測(cè)試結(jié)果，并且無(wú)論結(jié)果如何，都會(huì)用所有測(cè)試數(shù)據(jù)進(jìn)行測(cè)試。

而一般多測(cè)試模式下，如果全對(duì)，則為Accepted；若其中某次數(shù)據(jù)出錯(cuò)，則評(píng)測(cè)中止，并返回此數(shù)據(jù)出錯(cuò)的信息。

常見(jiàn)的Online Judge將評(píng)判結(jié)果分為如下幾類(lèi)：

Accepted

程序的輸出完全滿足題意，通過(guò)了全部的測(cè)試數(shù)據(jù)的測(cè)試。

Wrong Answer

你的程序順利地運(yùn)行完畢并正常退出，但是輸出的結(jié)果卻是錯(cuò)誤的。

注意：有的題包含多組測(cè)試數(shù)據(jù)，你的程序只要有一組數(shù)據(jù)是錯(cuò)誤的，結(jié)果就是WA。

Presentation Error

你的程序輸出的答案是正確的，但輸出格式不對(duì)，比如多寫(xiě)了一些空格、換行。

請(qǐng)注意，大部分程序的輸出，都要求最終輸出一個(gè)換行。

不過(guò)，計(jì)算機(jī)程序是很難準(zhǔn)確判斷PE錯(cuò)誤的，所以，很多PE錯(cuò)誤都會(huì)被評(píng)判成WA。

Compilation Error

你的程序沒(méi)有通過(guò)編譯。你可以點(diǎn)擊文字上的鏈接，查看詳細(xì)的出錯(cuò)信息，對(duì)照此信息，可以找出出錯(cuò)原因。

一般來(lái)說(shuō)，這種錯(cuò)誤主要是由 Linux 環(huán)境下相關(guān)編譯器與你使用的本地編譯器之間的差異造成的Judging

我們正在運(yùn)行你的程序進(jìn)行測(cè)試，請(qǐng)稍候。

Rejudging

我們更新了測(cè)試數(shù)據(jù)或者評(píng)判程序，并且正在進(jìn)行重測(cè)，這個(gè)過(guò)程比較耗費(fèi)資源，請(qǐng)稍候。Time Limit Exceeded

你的程序運(yùn)行的時(shí)間超過(guò)了該題規(guī)定的最大時(shí)間，你的程序被Online Judge強(qiáng)行終止。

注意：TE并不能說(shuō)明你的程序的運(yùn)行結(jié)果是對(duì)還是錯(cuò)，只能說(shuō)明你的程序用了太多的時(shí)間。Memory Limit Exceeded

你的程序運(yùn)行時(shí)使用的內(nèi)存，超過(guò)了該題規(guī)定的最大限制，或者你的程序申請(qǐng)內(nèi)存失敗，你的程序?qū)⒈籓nline Judge強(qiáng)行終止。

注意：ML并不能說(shuō)明你的程序的運(yùn)行結(jié)果是對(duì)還是錯(cuò)，只能說(shuō)明你的程序用了或者申請(qǐng)了太多的內(nèi)存。

Function Limit Exceeded

你的程序運(yùn)行時(shí)使用我們不允許使用的調(diào)用，將會(huì)得到此錯(cuò)誤，諸如文件操作等相關(guān)函數(shù)。請(qǐng)?zhí)貏e注意：system(“PAUSE”);也會(huì)導(dǎo)致此錯(cuò)誤。

Output Limit Exceeded

你的程序輸出了太多的東西。

Online Judge規(guī)定提交的程序在運(yùn)行的時(shí)候只能輸出1024K字節(jié)的東西，如果你輸出太多，將導(dǎo)致此錯(cuò)誤。

我們保證所有的題目的標(biāo)準(zhǔn)輸出都小于1024K字節(jié)。

Runtime Error

你的程序出現(xiàn)了“運(yùn)行時(shí)錯(cuò)誤”。

大部分情況下，NKOJ系統(tǒng)將返回給你一個(gè)Runtime Error的編號(hào)，由SIG或FPE開(kāi)頭，后面跟隨一個(gè)整數(shù)。具體的解釋請(qǐng)點(diǎn)擊此處查看。

System Error

系統(tǒng)發(fā)生了錯(cuò)誤。由于異常因素導(dǎo)致系統(tǒng)沒(méi)有正常運(yùn)作。我們盡力保證系統(tǒng)的穩(wěn)定運(yùn)行，但如您遇此情況，請(qǐng)聯(lián)系管理員。

Online Judge 支持哪些編程語(yǔ)言？

到目前為止，本 Online Judge 已經(jīng)支持 C、C++、PASCAL、JAVA 編程語(yǔ)言

OnlineJudge中，你的程序的輸入和輸出是相互獨(dú)立的，因此，每當(dāng)處理完一組測(cè)試數(shù)據(jù)，就應(yīng)當(dāng)按題目要求進(jìn)行相應(yīng)的輸出操作。而不必將所有結(jié)果儲(chǔ)存起來(lái)一起輸出。

定義64位數(shù)使用 long long 類(lèi)型，輸出格式串中使用 %lld 表示64位數(shù)。

本系統(tǒng)內(nèi)核部分作者：孫威、王巖，WEB部分作者：王巖。獨(dú)立自主開(kāi)發(fā)，保留一切權(quán)利。

南開(kāi)大學(xué)信息學(xué)院、南開(kāi)大學(xué)ACM協(xié)會(huì) 如果題目包含多組測(cè)試數(shù)據(jù)，我應(yīng)該在何時(shí)輸出我的結(jié)果？GCC 中如何使用64位數(shù)？關(guān)于本系統(tǒng)

Runtime Error 代號(hào)介紹

SIG(Signal,Linux系統(tǒng)信號(hào))部分：

(4)SIGILL 執(zhí)行了非法指令.通常是因?yàn)榭蓤?zhí)行文件本身出現(xiàn)錯(cuò)誤, 或者試圖執(zhí)行數(shù)據(jù)段.堆棧溢出時(shí)也有可能產(chǎn)生這個(gè)信號(hào).(6)SIGABRT 程序自己發(fā)現(xiàn)錯(cuò)誤并調(diào)用abort時(shí)產(chǎn)生.(6)SIGIOT 在PDP-11上由iot指令產(chǎn)生, 在其它機(jī)器上和SIGABRT一樣.(7)SIGBUS 非法地址, 包括內(nèi)存地址對(duì)齊(alignment)出錯(cuò).eg: 訪問(wèn)一個(gè)四個(gè)字長(zhǎng)的整數(shù), 但其地址不是4的倍數(shù).(8)SIGFPE 在發(fā)生致命的算術(shù)運(yùn)算錯(cuò)誤時(shí)發(fā)出.不僅包括浮點(diǎn)運(yùn)算錯(cuò)誤, 還包括溢出及除數(shù)為0等其它所有的算術(shù)的錯(cuò)誤.(11)SIGSEGV 試圖訪問(wèn)未分配給自己的內(nèi)存, 或試圖往沒(méi)有寫(xiě)權(quán)限的內(nèi)存地址寫(xiě)數(shù)據(jù).造成這種錯(cuò)誤的原因有很多，主要原因有三條：

一、數(shù)據(jù)下標(biāo)越界，包括越上界和越下界。

二、堆棧溢出，比如遞歸層數(shù)過(guò)多。

三、不恰當(dāng)?shù)闹羔樖褂谩?/p>

FPC(由Free Pascal 產(chǎn)生的錯(cuò)誤代碼)：

由于OJ系統(tǒng)已經(jīng)限制了程序的行為，所以以下部分代碼并不會(huì)實(shí)際出現(xiàn)，此處列舉僅僅為了文檔相對(duì)完整。Invalid function number 錯(cuò)誤的功能代碼File not found 文件未找到Path not found 目錄未發(fā)現(xiàn)Too many open files 打開(kāi)太多的文件File access denied 文件訪問(wèn)拒絕Invalid file handle 錯(cuò)誤的文件句柄Invalid file access code 錯(cuò)誤的文件訪問(wèn)代碼Invalid drive number 錯(cuò)誤的驅(qū)動(dòng)器數(shù)字Cannot remove current directory 不能移動(dòng)當(dāng)前目錄Cannot rename across drives 不能跨越驅(qū)動(dòng)器更改文件名

Disk read error 磁盤(pán)讀錯(cuò)誤

Disk write error 磁盤(pán)寫(xiě)錯(cuò)誤

File not assigned 文件未曾建立關(guān)聯(lián)

File not open 文件未打開(kāi)

File not open for input 文件不能打開(kāi)讀數(shù)據(jù)

File not open for output 文件不能打開(kāi)寫(xiě)數(shù)據(jù)

106Invalid numeric format 錯(cuò)誤的數(shù)字格式

從標(biāo)準(zhǔn)輸入(Text文件)中預(yù)期得到的數(shù)字格式不對(duì).150 Disk is write-protected

151 Bad drive request struct length

152 Drive not ready

154 CRC error in data

156 Disk seek error

157 Unknown media type

158 Sector Not Found

159 Printer out of paper

160 Device write fault

161 Device read fault

162 Hardware failure

200Division by zero

被除數(shù)為0.201Range check error

如果你編譯你的程序時(shí)設(shè)置了方位檢查,原因有可能是:

數(shù)組訪問(wèn)超過(guò)了聲明的范圍.試圖給一個(gè)變量賦值超過(guò)其范圍(例如枚舉類(lèi)型).202Stack overflow error

棧溢出

棧增長(zhǎng)超過(guò)了最大值(in which case the size of local variables should be reduced to avoid this error), or the stack has become corrupt.只有當(dāng)棧檢查時(shí)才出現(xiàn)該錯(cuò)誤.203Heap overflow error

堆溢出

堆增長(zhǎng)超過(guò)了上界.This is caused when trying to allocate memory exlicitly with New, GetMem or ReallocMem, or when a class or object instance is created and no memory is left.Please note that, by default, Free Pascal provides a growing heap, i.e.the heap will try to allocate more memory if needed.However, if the heap has reached the maximum size allowed by the operating system or hardware, then you will get this error.204Invalid pointer operation

錯(cuò)誤的指針操作

使用 Dispose or Freemem 時(shí)使用錯(cuò)誤的指針(特別的, Nil)

205Floating point overflow

浮點(diǎn)數(shù)上溢

你試圖使用或產(chǎn)生一個(gè)太大實(shí)數(shù).206Floating point underflow

你試圖使用或產(chǎn)生一個(gè)太小實(shí)數(shù).207Invalid floating point operation

錯(cuò)誤的浮點(diǎn)數(shù)操作

可能是你開(kāi)平方根或者對(duì)數(shù)時(shí)使用負(fù)數(shù).210Object not initialized

對(duì)象未初始化

When compiled with range checking on, a program will report this error if you call a virtual method without having called istr constructor.211 Call to abstract method 212 Stream registration error 213 Collection index out of range 214 Collection overflow error

215Arithmetic overflow error 數(shù)字超出范圍 例如3000000000超出長(zhǎng)整形范圍

216 General Protection fault

217 Unhandled exception occurred 219 Invalid typecast

227 Assertion failed error

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

賽后總結(jié)

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

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

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

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

第四篇：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)最小生成樹(shù)算法(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)簡(jiǎn)單并查集的應(yīng)用.(4)哈希表和二分查找等高效查找法(數(shù)的Hash,串的Hash)

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

(5)哈夫曼樹(shù)(poj3253)

(6)堆

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

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

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

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

(1)背包問(wèn)題.(poj1837,poj1276)

(2)型如下表的簡(jiǎn)單DP(可參考lrj的書(shū) 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}(最長(zhǎng)公共子序列)

(poj3176,poj1080,poj1159)

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

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

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

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

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

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

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

(poj1408,poj1584)

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

(1)C++的標(biāo)準(zhǔn)模版庫(kù)的應(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)線段樹(shù).(poj2528,poj2828,poj2777,poj2886,poj2750)

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

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

(4)RMQ.(poj3264,poj3368)

(5)并查集的高級(jí)應(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ī)劃解特別的施行商問(wèn)題等)

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

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

(3)樹(shù)型動(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.概率問(wèn)題.(poj3071,poj3440)

3.GCD、擴(kuò)展的歐幾里德(中國(guó)剩余定理)(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)掃描線算法(例如求矩形的面積和周長(zhǎng)并,常和線段樹(shù)或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)

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

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

一.基本算法要求:

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

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

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

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

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

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

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

(4)最小樹(shù)形圖(poj3164)

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

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

(2)LCA和RMQ問(wèn)題(LCA(最近公共祖先問(wèn)題)有離線算法(并查集+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)左偏樹(shù)(可合并堆).(5)后綴樹(shù)(非常有用的數(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ù)不易過(guò)大、可以考慮雙向搜索或者是輪換搜索、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.極大極小過(guò)程(poj3317,poj1085)

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

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

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

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

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

<1>青蛙過(guò)河問(wèn)題

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

2.背包類(lèi)問(wèn)題

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

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

<3>判定性背包問(wèn)題

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

<5> +-1背包問(wèn)題

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

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

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

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

<1>積木游戲問(wèn)題

<2>決斗（判定性問(wèn)題）

<3>圓的最大多邊形問(wèn)題

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

<5>棋盤(pán)分割

<6>日程安排問(wèn)題

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

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

<9>資源分配問(wèn)題

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

<11>漂亮的打印

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

<13>最高積木問(wèn)題

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

<15>2次冪和問(wèn)題

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

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

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

<1>模K問(wèn)題的dp

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

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

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

<1>1-SUM問(wèn)題

<2>2-SUM問(wèn)題

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

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

<1>凸多邊形的三角剖分問(wèn)題

<2>乘積最大問(wèn)題

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

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

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

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

<2>部分背包問(wèn)題

<3>乘船問(wèn)題

<4>貪心策略

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

8.狀態(tài)dp

<1>牛仔射擊問(wèn)題(博弈類(lèi))

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

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

9.樹(shù)型dp

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

<2>小胖守皇宮問(wèn)題

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

<4>樹(shù)中漫游問(wèn)題

<5>樹(shù)上的博弈

<6>樹(shù)的最大獨(dú)立集問(wèn)題

<7>樹(shù)的最大平衡值問(wèn)題

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

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

C語(yǔ)言篇

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

/*結(jié)構(gòu)體類(lèi)型*/ { 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 請(qǐng)輸入你的選擇（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ò)誤！請(qǐng)按照下面提示選擇?！?;}

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(“請(qǐng)輸入第1個(gè)學(xué)生學(xué)號(hào)及成績(jī)（學(xué)號(hào)與成績(jī)以空格隔開(kāi)，'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);/*開(kāi)辟下一個(gè)結(jié)點(diǎn)*/ printf(“請(qǐng)輸入第%d個(gè)學(xué)生學(xué)號(hào)及成績(jī)（學(xué)號(hào)與成績(jī)以空格隔開(kāi)，'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(“鏈表不存在，請(qǐng)先創(chuàng)建！”);

else

{

p=head;

for(;p!=NULL;)

{

printf(“%d號(hào)學(xué)生成績(jī)：%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(“鏈表不存在，請(qǐng)先創(chuàng)建！”);else

{

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

printf(“請(qǐng)輸入新結(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é)號(hào)*/ { 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)開(kāi)始查找*/

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

scanf(“%d”,&i);

getchar();

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

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

{

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號(hào)學(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 號(hào)學(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用來(lái)取p1后面的每個(gè)結(jié)點(diǎn)來(lái)與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;

/*對(duì)第一個(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請(qǐng)輸入要修改數(shù)據(jù)的學(xué)號(hào)(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請(qǐng)輸入新的數(shù)據(jù)(學(xué)號(hào) 成績(jī))：”);

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

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

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

}

else

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

scanf(“%d”,&m);

}

return(head);}

void xuehao(struct student *head)

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

int m,leap;

printf(“n請(qǐng)輸入要查找的學(xué)號(hào)：”);

scanf(“%d”,&m);

while(m!=0)

{ p=head;

leap=0;

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

{

if(p->num==m)

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

leap=1;

}

p=p->next;

}

if(leap==1)

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

else

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

scanf(“%d”,&m);

}

}

void chengji(struct student *head)

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

int leap;

float m;

printf(“n請(qǐng)輸入要查找的成績(jī)：”);

scanf(“%f”,&m);

while(m>=0)

{ p=head;

leap=0;

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

{

if(p->num==m)

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

leap=1;

}

p=p->next;

}

if(leap==1)

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

else

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

scanf(“%f”,&m);

}

}

void seach()

/*查找子菜單*/ {

int i;

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

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

case 1: xuehao(head);break;

case 2: chengji(head);break;

case 0: menu();break;

default:printf(“n選擇錯(cuò)誤！請(qǐng)按照下面提示選擇?！?;} 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ù)的類(lèi)型，其值是函數(shù)結(jié)果狀態(tài)代碼 typedef int Status;

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

typedef struct{ unsigned int weight;unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)Huffman樹(shù) 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è)值中序號(hào)小的那個(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)及對(duì)應(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)造哈夫曼樹(shù)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);