第一篇：ACM中WA方面的錯誤總結
1、Int遇到過的問題 簡介：
int是我們最常用的類型之一。如果輸入數據是整形，一般都直接用該類型來存放輸入數據。
錯誤經歷：
自己在作Equiptment Box時，因為輸入數據長、寬均是小于50000的整數，因此就使用int來作輸入。這本身沒有問題，但在求其斜邊長時，使用的是sqrt（x * x + y * y），表面看是沒有問題，但結果一直是Wrong Answer。后來將這一行改為pow((pow(x, 2)+ pow(y,3)), 0.5)，就Accept了！錯誤原因：
后來經johnbill和hewei的分析，x，y本身沒有問題，不會越界，但使用sqrt（x*x +y*y）時，里面的x*x 和 y*y則會超出int范圍，造成溢出。而pow會將參數自動轉換為double，就不會出錯。
避免失誤的辦法：
（1）以后均使用pow進行運算。（習慣）（2）運算時，注意做強行轉換。（比較麻煩）
（3）不管輸入給的類型，直接用double來存儲，就不會溢出了。這種方法表面看沒有問題，但直到這次比賽，才發現了一個很嚴重的問題！
2、double遇到過的問題 簡介：
是我們在解題時，和int一起是最常用的類型。錯誤經歷：
因為 double上限可達1.7e308。而一般題目（非大數運算要求）均不可能超過其限，發生溢出，所以之后我就在做題時，凡是遇到結果有些大時，均用double類型來保存，來避免溢出。看起來，這樣比較方便，因為我們在本機上是用VC＋＋，而OnlineJudge是gcc，它們支持的長整形類型不同，一個是__int64，而一個是long long；處理格式也不同，I 64u 和 lld。而在這種情況下，“真正”的可以用double的話，那就可以將其統一起來。但是……昨天比賽C題時，自己也是這么遞推和用double保存，但一直Wrong Answer。和遞歸能計算出（太大的數據很耗時）的數據相比，都是正確的，不知原因何在。比賽結束后，和別人結果對照了一下，把double改成unsigned long long 就Accept了。錯譯原因：
這是因為：double類型的精度只有15位！！它的上限可以很大，但只能保證15位的精度！換句話說，只能保證15位是正確的。在數據（50，50）以后，結果都在20位以上，前面的位數是正確的，但后面的幾位就會出現問題了！解決方法：
（1）定義頭文件，在本機上用__int64，提交時用long long（2）本機上使用VAC編譯(J)（奇難用！）
（3）反正絕對不能使用double來計數，尤其比較大的數，但可以利用它來測試最大數據的范圍大小，這樣可以反過來幫助我們決定用什么類型來保存。
3、float遇到過的問題
我還記得當時Hunter做area的時候，各方面都作了考慮，但一直是Wrong Answer。后來只是把存儲坐標的float類型改為double，就過了。原因：
應該是float的精度不夠（具體嘛…..大家re），但題目只要求3位小數也有問題……。所以，以后大家要使用浮點數計算時，直接用double，不要考慮使用float。一般內存是不會有問題的。
4、4舍5入的問題：
在做Lifting the Stone時，題上要求保留到小數點兩位，第三位作四舍五入，自己直接用%.02來打，以為自動會四舍五入。但一直沒過。加上處理之后就過了…….原因：
小數點后第三位為5時，會隨機的作進位處理。解決辦法：
如果題上要求了四舍五入，一定要記得進行處理：x = floor(x*100 + 0.5)/100，5、為5時，后一位奇數進位，偶數不進位： 這個JohnBIll講過，一般不會有這種“浪費青春的題…..”。解決辦法：
除了相當的靈活，多試，還需要運氣了……
第二篇：ACM錯誤提示
http://acm.nankai.edu.cn/user_message.php
F.A.Q.(Chinese)我的程序為什么不能編譯通過呢？
Online Judge 要求C/C++程序符合Ansi標準：
ANSI 標準和 Microsoft Visual C++ 存在一些不同的地方，比如：
0)main函數必須聲明為int，也就是 void main()必須變成 int main()
VC同樣可使用int main，只是程序最后需要 return 0。
1)Microsoft Visual C++ 可以將 main 函數聲明為 void，而 ANSI 中必須為 int main
2)請避免使用如下方式聲明變量i
for(int i=0;i<10;i++)
{
...}
您可以在For 語句之前，進行聲明。
3)itoa 不是一個 ANSI 函數
4)stricmp 不是一個 ANSI 函數
5)sqrt()的可能用法：sqrt(double(x));//強制轉換為double
6)OnlineJudge 中如何使用64位數？
定義64位數使用 long long 類型，輸出格式串中使用 %lld 表示64位數。
雖然Free Pascal盡量設計得和Turbo Pascal接近，但是由于以下的兩個原因，兩者之間還是有一些區別的：
1．Free Pascal是一個32位的編譯器，而Turbo Pascal只是16位編譯器；
2．Free Pascal是一個跨平臺的編譯器，而Turbo Pascal只在windows上使用。
如果你的代碼是遵守ANSI Pascal的，那么代碼從Turbo Pascal移植到Free Pascal是沒有問題的。
下面是在Turbo Pascal上可以使用，但是在Free Pascal就不能使用的一些語言特性：
1．函數和過程在使用時，參數的類型必須和定義時完全一致。原因是在Free Pascal中添加了函數重載功能。
2．PROTECTED，PUBLIC，PUBLISHED，TRY，FINALLY，EXCEPT，RAISE成為了關鍵字，因此不能作為函數和過程的名字。
3．FAR，NEAR不再是關鍵字了。原因是Free Pascal是32位系統，不再需要這些關鍵字。
4．布爾表達式不一定要全部進行計算。只要最終結果已經能夠確定，就不再計算其它還沒有計算的部分了。
比如布爾表達式exp1 AND exp2 AND exp3，如果已知exp1的結果是false，那么怎么表達式的結果肯定是false，exp2和exp3就不用進行計算了。
5．在Free Pascal中，集合中的元素都是4個字節長的。
6．表達式執行的順序是不確定的。比如對于表達式a:=g(2)+f(3);不保證g(2)一定在f(3)之前執行。
7．如果用Rewrite打開文件，那么文件就只能被寫入了。如果需要讀取這個文件，要對文件執行Reset。
8．Free Pascal在程序結束之前一定要關閉輸出文件，否則輸出文件可能不能被正確的寫入。
9．Free Pascal理論上可以使用4GB的內存，因此實際上幾乎可以使用系統中的所有剩余內存（除非賽題中有內存限制）。
這是Free Pascal由于32位的編譯器。但是對于Turbo Pascal來說，由于是16位的編譯器，因此不能定義大小超過64KB的數據類型和變量，并且在DOS實模式下可以使用的內存總數只有640KB。
Online Judge 評判結果分別表示什么意思？
當你提交的程序被Online Judge評判完畢后，通常結果將立刻返回，或者你也可以在“Solutions”頁看到評判結果。
詳細測試多數據測試模式下，將顯示出各個測試數據的測試結果，并且無論結果如何，都會用所有測試數據進行測試。
而一般多測試模式下，如果全對，則為Accepted；若其中某次數據出錯，則評測中止，并返回此數據出錯的信息。
常見的Online Judge將評判結果分為如下幾類：
Accepted
程序的輸出完全滿足題意，通過了全部的測試數據的測試。
Wrong Answer
你的程序順利地運行完畢并正常退出，但是輸出的結果卻是錯誤的。
注意：有的題包含多組測試數據，你的程序只要有一組數據是錯誤的，結果就是WA。
Presentation Error
你的程序輸出的答案是正確的，但輸出格式不對，比如多寫了一些空格、換行。
請注意，大部分程序的輸出，都要求最終輸出一個換行。
不過，計算機程序是很難準確判斷PE錯誤的，所以，很多PE錯誤都會被評判成WA。
Compilation Error
你的程序沒有通過編譯。你可以點擊文字上的鏈接，查看詳細的出錯信息，對照此信息，可以找出出錯原因。
一般來說，這種錯誤主要是由 Linux 環境下相關編譯器與你使用的本地編譯器之間的差異造成的Judging
我們正在運行你的程序進行測試，請稍候。
Rejudging
我們更新了測試數據或者評判程序，并且正在進行重測，這個過程比較耗費資源，請稍候。Time Limit Exceeded
你的程序運行的時間超過了該題規定的最大時間，你的程序被Online Judge強行終止。
注意：TE并不能說明你的程序的運行結果是對還是錯，只能說明你的程序用了太多的時間。Memory Limit Exceeded
你的程序運行時使用的內存，超過了該題規定的最大限制，或者你的程序申請內存失敗，你的程序將被Online Judge強行終止。
注意：ML并不能說明你的程序的運行結果是對還是錯，只能說明你的程序用了或者申請了太多的內存。
Function Limit Exceeded
你的程序運行時使用我們不允許使用的調用，將會得到此錯誤，諸如文件操作等相關函數。請特別注意：system(“PAUSE”);也會導致此錯誤。
Output Limit Exceeded
你的程序輸出了太多的東西。
Online Judge規定提交的程序在運行的時候只能輸出1024K字節的東西，如果你輸出太多，將導致此錯誤。
我們保證所有的題目的標準輸出都小于1024K字節。
Runtime Error
你的程序出現了“運行時錯誤”。
大部分情況下，NKOJ系統將返回給你一個Runtime Error的編號，由SIG或FPE開頭，后面跟隨一個整數。具體的解釋請點擊此處查看。
System Error
系統發生了錯誤。由于異常因素導致系統沒有正常運作。我們盡力保證系統的穩定運行，但如您遇此情況，請聯系管理員。
Online Judge 支持哪些編程語言？
到目前為止，本 Online Judge 已經支持 C、C++、PASCAL、JAVA 編程語言
OnlineJudge中，你的程序的輸入和輸出是相互獨立的，因此，每當處理完一組測試數據，就應當按題目要求進行相應的輸出操作。而不必將所有結果儲存起來一起輸出。
定義64位數使用 long long 類型，輸出格式串中使用 %lld 表示64位數。
本系統內核部分作者：孫威、王巖，WEB部分作者：王巖。獨立自主開發，保留一切權利。
南開大學信息學院、南開大學ACM協會 如果題目包含多組測試數據，我應該在何時輸出我的結果？GCC 中如何使用64位數？關于本系統
Runtime Error 代號介紹
SIG(Signal,Linux系統信號)部分：
(4)SIGILL 執行了非法指令.通常是因為可執行文件本身出現錯誤, 或者試圖執行數據段.堆棧溢出時也有可能產生這個信號.(6)SIGABRT 程序自己發現錯誤并調用abort時產生.(6)SIGIOT 在PDP-11上由iot指令產生, 在其它機器上和SIGABRT一樣.(7)SIGBUS 非法地址, 包括內存地址對齊(alignment)出錯.eg: 訪問一個四個字長的整數, 但其地址不是4的倍數.(8)SIGFPE 在發生致命的算術運算錯誤時發出.不僅包括浮點運算錯誤, 還包括溢出及除數為0等其它所有的算術的錯誤.(11)SIGSEGV 試圖訪問未分配給自己的內存, 或試圖往沒有寫權限的內存地址寫數據.造成這種錯誤的原因有很多，主要原因有三條：
一、數據下標越界，包括越上界和越下界。
二、堆棧溢出，比如遞歸層數過多。
三、不恰當的指針使用。
FPC(由Free Pascal 產生的錯誤代碼)：
由于OJ系統已經限制了程序的行為，所以以下部分代碼并不會實際出現，此處列舉僅僅為了文檔相對完整。Invalid function number 錯誤的功能代碼File not found 文件未找到Path not found 目錄未發現Too many open files 打開太多的文件File access denied 文件訪問拒絕Invalid file handle 錯誤的文件句柄Invalid file access code 錯誤的文件訪問代碼Invalid drive number 錯誤的驅動器數字Cannot remove current directory 不能移動當前目錄Cannot rename across drives 不能跨越驅動器更改文件名
Disk read error 磁盤讀錯誤
Disk write error 磁盤寫錯誤
File not assigned 文件未曾建立關聯
File not open 文件未打開
File not open for input 文件不能打開讀數據
File not open for output 文件不能打開寫數據
106Invalid numeric format 錯誤的數字格式
從標準輸入(Text文件)中預期得到的數字格式不對.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
被除數為0.201Range check error
如果你編譯你的程序時設置了方位檢查,原因有可能是:
數組訪問超過了聲明的范圍.試圖給一個變量賦值超過其范圍(例如枚舉類型).202Stack overflow error
棧溢出
棧增長超過了最大值(in which case the size of local variables should be reduced to avoid this error), or the stack has become corrupt.只有當棧檢查時才出現該錯誤.203Heap overflow error
堆溢出
堆增長超過了上界.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
錯誤的指針操作
使用 Dispose or Freemem 時使用錯誤的指針(特別的, Nil)
205Floating point overflow
浮點數上溢
你試圖使用或產生一個太大實數.206Floating point underflow
你試圖使用或產生一個太小實數.207Invalid floating point operation
錯誤的浮點數操作
可能是你開平方根或者對數時使用負數.210Object not initialized
對象未初始化
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 數字超出范圍 例如3000000000超出長整形范圍
216 General Protection fault
217 Unhandled exception occurred 219 Invalid typecast
227 Assertion failed error
第三篇：ACM賽后總結
賽后總結
雖然已經是大二第二學期了，這卻是我的第一真正的ACM比賽經歷，賽后感覺自己水平很差，感覺很不好，或許只有受到了了打擊，才會有成長，也只有在一次次的打擊中吸取經驗，成為自己前進的動力。
這次比賽總結起來發現了我們的好多不足之處，第一個就是我們經驗的缺失，畢竟是我們第一次參加這樣的比賽，還有就是對做題順序的把握不好，對題目難易程度判斷不準確，如果做一個題發現思路錯了，我們應該要及時改變思路，跳過去，先去做下面容易的題，等回過頭來在做，要用盡量短的時間把我們知道做的題做出來，有些題，我們有思路，不敢保證完全做出來，就放到后面再去做，還有就是比賽的時候心態不好，中間做的時候就比較焦急，這樣對自己的思路也會有影響，要調節好自己的情緒，還有就是要及時改變策略，多看榜，看到有很多人a的題目，我們肯定要去看一下，一開始我們就應該把題目全部都看一遍，最重要的是我們的實力還是不行，對于有些簡單的題目還是不夠熟練，思路不夠清晰，下階段要進一步有針對的加強訓練！
比賽結束，我們真的是百感交集，有過遺憾，有過不甘心，有過失望，本來這次比賽應該是很好拿獎的，但最終我們還是與獎狀擦肩而過，可能與經驗的缺乏有關，我想更多的應該還是實力的差距，自己的實力不行，做什么都是白搭。所幸的是，我們明年還有一次機會，再努力一年，我想我們明年再戰的時候，一定可以取得一個很好的成績。
14物聯網 賈文彪
第四篇：ACM算法總結——超有用!
初期: 一.基本算法:
(1)枚舉.(poj1753,poj2965)
(2)貪心(poj1328,poj2109,poj2586)
(3)遞歸和分治法.(4)遞推.(5)構造法.(poj3295)
(6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.圖算法:
(1)圖的深度優先遍歷和廣度優先遍歷.(2)最短路徑算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成樹算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓撲排序(poj1094)
(5)二分圖的最大匹配(匈牙利算法)(poj3041,poj3020)
(6)最大流的增廣路算法(KM算法).(poj1459,poj3436)三.數據結構.(1)串(poj1035,poj3080,poj1936)
(2)排序(快排、歸并排(與逆序數有關)、堆排)(poj2388,poj2299)
(3)簡單并查集的應用.(4)哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼樹(poj3253)
(6)堆
(7)trie樹(靜態建樹、動態建樹)(poj2513)四.簡單搜索
(1)深度優先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)
(2)廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.動態規劃
(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]}.(最優二分檢索樹問題)六.數學
(1)組合數學:
1.加法原理和乘法原理.2.排列組合.3.遞推關系.(POJ3252,poj1850,poj1019,poj1942)
(2)數論.1.素數與整除問題
2.進制位.3.同余模運算.(poj2635, poj3292,poj1845,poj2115)
(3)計算方法.1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)七.計算幾何學.(1)幾何公式.(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等).(poj2031,poj1039)
(3)多邊型的簡單算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
(4)凸包.(poj2187,poj1113)中級: 一.基本算法:
(1)C++的標準模版庫的應用.(poj3096,poj3007)
(2)較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)二.圖算法:
(1)差分約束系統的建立和求解.(poj1201,poj2983)
(2)最小費用最大流(poj2516,poj2516,poj2195)
(3)雙連通分量(poj2942)
(4)強連通分支及其縮點.(poj2186)
(5)圖的割邊和割點(poj3352)
(6)最小割模型、網絡流規約(poj3308,)三.數據結構.(1)線段樹.(poj2528,poj2828,poj2777,poj2886,poj2750)
(2)靜態二叉檢索樹.(poj2482,poj2352)
(3)樹狀樹組(poj1195,poj3321)
(4)RMQ.(poj3264,poj3368)
(5)并查集的高級應用.(poj1703,2492)
(6)KMP算法.(poj1961,poj2406)四.搜索
(1)最優化剪枝和可行性剪枝
(2)搜索的技巧和優化(poj3411,poj1724)
(3)記憶化搜索(poj3373,poj1691)
五.動態規劃
(1)較為復雜的動態規劃(如動態規劃解特別的施行商問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)記錄狀態的動態規劃.(POJ3254,poj2411,poj1185)
(3)樹型動態規劃(poj2057,poj1947,poj2486,poj3140)六.數學
(1)組合數學:
1.容斥原理.2.抽屜原理.3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).4.遞推關系和母函數.(2)數學.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題.(poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩余定理)(poj3101)
(3)計算方法.1.0/1分數規劃.(poj2976)
2.三分法求解單峰(單谷)的極值.3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)隨機化算法(poj3318,poj2454)
(5)雜題.(poj1870,poj3296,poj3286,poj1095)七.計算幾何學.(1)坐標離散化.(2)掃描線算法(例如求矩形的面積和周長并,常和線段樹或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多邊形的內核(半平面交)(poj3130,poj3335)
(4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高級:
一.基本算法要求:
(1)代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保證正確性和高效性.poj3434 二.圖算法:
(1)度限制最小生成樹和第K最短路.(poj1639)
(2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最優比率生成樹.(poj2728)
(4)最小樹形圖(poj3164)
(5)次小生成樹.(6)無向圖、有向圖的最小環
三.數據結構.(1)trie圖的建立和應用.(poj2778)
(2)LCA和RMQ問題(LCA(最近公共祖先問題)有離線算法(并查集+dfs)和 在線算法
(RMQ+dfs)).(poj1330)
(3)雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的 目的).(poj2823)
(4)左偏樹(可合并堆).(5)后綴樹(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)四.搜索
(1)較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*算法.(poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*算法.(poj3131,poj2870,poj2286)五.動態規劃
(1)需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)
(2)四邊形不等式理論.(3)較難的狀態DP(poj3133)六.數學
(1)組合數學.1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.(2)博奕論.1.極大極小過程(poj3317,poj1085)
2.Nim問題.七.計算幾何學.(1)半平面求交(poj3384,poj2540)
(2)可視圖的建立(poj2966)
(3)點集最小圓覆蓋.(4)對踵點(poj2079)八.綜合題.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)
Dp狀態設計與方程總結
1.不完全狀態記錄
<1>青蛙過河問題
<2>利用區間dp
2.背包類問題
<1> 0-1背包，經典問題
<2>無限背包，經典問題
<3>判定性背包問題
<4>帶附屬關系的背包問題
<5> +-1背包問題
<6>雙背包求最優值
<7>構造三角形問題
<8>帶上下界限制的背包問題(012背包)
3.線性的動態規劃問題
<1>積木游戲問題
<2>決斗（判定性問題）
<3>圓的最大多邊形問題
<4>統計單詞個數問題
<5>棋盤分割
<6>日程安排問題
<7>最小逼近問題(求出兩數之比最接近某數/兩數之和等于某數等等)
<8>方塊消除游戲(某區間可以連續消去求最大效益)
<9>資源分配問題
<10>數字三角形問題
<11>漂亮的打印
<12>郵局問題與構造答案
<13>最高積木問題
<14>兩段連續和最大
<15>2次冪和問題
<16>N個數的最大M段子段和
<17>交叉最大數問題
4.判定性問題的dp(如判定整除、判定可達性等)
<1>模K問題的dp
<2>特殊的模K問題，求最大(最小)模K的數
<3>變換數問題
5.單調性優化的動態規劃
<1>1-SUM問題
<2>2-SUM問題
<3>序列劃分問題(單調隊列優化)
6.剖分問題(多邊形剖分/石子合并/圓的剖分/乘積最大)
<1>凸多邊形的三角剖分問題
<2>乘積最大問題
<3>多邊形游戲(多邊形邊上是操作符,頂點有權值)
<4>石子合并(N^3/N^2/NLogN各種優化)
7.貪心的動態規劃
<1>最優裝載問題
<2>部分背包問題
<3>乘船問題
<4>貪心策略
<5>雙機調度問題Johnson算法
8.狀態dp
<1>牛仔射擊問題(博弈類)
<2>哈密頓路徑的狀態dp <3>兩支點天平平衡問題
<4>一個有向圖的最接近二部圖
9.樹型dp
<1>完美服務器問題(每個節點有3種狀態)
<2>小胖守皇宮問題
<3>網絡收費問題
<4>樹中漫游問題
<5>樹上的博弈
<6>樹的最大獨立集問題
<7>樹的最大平衡值問題
<8>構造樹的最小環
第五篇：ACM程序設計培訓總結
C語言篇
學生信息管理系統 #include “stdio.h” #include “stdlib.h” #define LEN sizeof(struct student)struct student
/*結構體類型*/ { int num;float score;struct student *next;};int n=0;
/*記錄鏈表結點個數*/ struct student *head;
/*鏈表頭指針*/ void menu();
/*DOS菜單函數*/ struct student *creat();
/*鏈表創建函數*/ void prin(struct student *head);
/*鏈表輸出函數*/ struct student *insert(struct student *head);/*鏈表添加函數*/ struct student *del(struct student *head);
/*鏈表刪除函數*/ struct student * paixu(struct student *head);/*排序函數*/ struct student *xiugai(struct student *head);/*修改函數*/ void seach();
void menu(){
int i;
printf(“n t 1t創建學生表n”);printf(“n t 2t添加學生數據n”);printf(“n t 3t顯示學生信息n”);printf(“n t 4t排序學生記錄n”);printf(“n t 5t修改學生記錄n”);
printf(“n t 6t刪除學生記錄n”);
printf(“n t 7t查找學生記錄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選擇錯誤！請按照下面提示選擇。”);}
menu();} void main(){
menu();}
struct student *creat()
/*此函數帶回一個指向鏈表頭的指針*/ {
struct student *head,*p1,*p2;n=0;head=NULL;p1=(struct student *)malloc(LEN);/*創建第一個結點*/ printf(“請輸入第1個學生學號及成績（學號與成績以空格隔開，'0 0'結束）:”);scanf(“%d%f”,&p1->num,&p1->score);p1->next=NULL;while(p1->num!=0)
/*應該將結點加入鏈表*/ { ++n;if(n==1)head=p1;
/*是第一個結點,作表頭*/ else p2->next=p1;
/*不是第一個結點,作表尾*/ p2=p1;p1=(struct student*)malloc(LEN);/*開辟下一個結點*/ printf(“請輸入第%d個學生學號及成績（學號與成績以空格隔開，'0 0'結束）:”,n+1);scanf(“%d%f”,&p1->num,&p1->score);p1->next=NULL;} free(p1);
/*釋放最后一個結點所占的內存*/ return(head);/*返回鏈表的頭指針*/ }
void prin(struct student *head)
/*鏈表輸出函數*/ {
struct student *p;
if(head==NULL)
printf(“鏈表不存在，請先創建！”);
else
{
p=head;
for(;p!=NULL;)
{
printf(“%d號學生成績：%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指向第一個結點*/
if(head==NULL)printf(“鏈表不存在，請先創建！”);else
{
while(ch=='Y'||ch=='y'){ p0=(struct student*)malloc(LEN);
printf(“請輸入新結點的數據，輸入'0 0'放棄插入：”);
scanf(“%d%f”,&p0->num,&p0->score);p0->next=NULL;
if(p0->num==0)
{ free(p0);
}
else
{ printf(“輸入結點插入的位置：”);
scanf(“%d”,&i);
if(i==0)
/*作為表頭*/
{
p0->next=head;
head=p0;
}
else
{
while(i>1&&(p1!=NULL))
{
p2=p1;
p1=p1->next;
i--;
}
/*找插入點*/
p0->next=p1;
/*插到p2指向的結點之后*/
p2->next=p0;
}
++n;
/*結點數加1*/
}
printf(“n數據添加成功！是否繼續（y或Y繼續,任意鍵退出):”);
getchar();
ch=getchar();} } return(head);}
struct student *del(struct student *head)/*形參num為需刪除的學號*/ { int i;
char ch='y';struct student *p1,*p2;
while(ch=='Y'||ch=='y'){ if(head==NULL){ printf(“n鏈表不存在!n”);break;
/*鏈表為空*/ } else {
p1=head;
/*從頭結點開始查找*/
printf(“請輸入要刪除的學生學號：”);
scanf(“%d”,&i);
getchar();
while(i!=p1->num&&p1->next!=NULL)
/*p1指向的不是所要找的結點,并且沒有到表尾*/
{
p2=p1;
p1=p1->next;
/*后移一個結點*/
}
if(i==p1->num)
/*找到了需刪除的結點*/
{
if(p1==head)
/*p1指向的是頭結點*/
head=p1->next;/*第二個結點成為新的頭結點*/
else
p2->next=p1->next;/*后繼結點的地址賦給前一結點*/
printf(“%d號學生已經被刪除n”,i);
free(p1);
/*釋放結點所占的內存*/
n--;
/*鏈表結點數減1*/
printf(“n數據刪除成功！是否繼續（y或Y繼續,任意鍵退出):”);
ch=getchar();
}
else
{
printf(“%d 號學生不存在或已經被刪除!n”,i);/*找不到刪除結點*/
printf(“n是否繼續（y或Y繼續,任意鍵退出):”);
ch=getchar();
} }
}
return(head);}
struct student * paixu(struct student *head)
/*排序函數*/ {
struct student *p0,*p1,*p2,*pt;
/*p0代表p1的前個結點*/
/*p1代表當前正排序的結點*/
/*p2用來取p1后面的每個結點來與P1比較*/ int i;
/*i=1表示頭結點排序*/ if(head==NULL)
{
printf(“鏈表不存在，先創建！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;
/*對第一個結點排序時處理*/
else
/*其他結點排序時處理*/
{ p0->next=p1;
p0=p1;
}
p2=p1->next;
p1=p1->next;
}
prin(head);
/*調用輸出函數*/
}
return(head);}
struct student *xiugai(struct student *head)
/*修改函數*/ { struct student *p;
int m;
printf(“n請輸入要修改數據的學號(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請輸入新的數據(學號 成績)：”);
scanf(“%d%f”,&p->num,&p->score);
printf(“n修改成功！”);
printf(“n若繼續修改，請輸入學號(0退出)：”);
}
else
printf(“n該學生不存在，請重新輸入學號(0退出)：”);
scanf(“%d”,&m);
}
return(head);}
void xuehao(struct student *head)
/*按學號查找函數*/ { struct student *p;
int m,leap;
printf(“n請輸入要查找的學號：”);
scanf(“%d”,&m);
while(m!=0)
{ p=head;
leap=0;
for(;p->next!=NULL;)
{
if(p->num==m)
{printf(“n你要查找的學生信息為： 學號 %d 成績 %fn”,p->num,p->score);
leap=1;
}
p=p->next;
}
if(leap==1)
printf(“n若繼續查找，請輸入學號(0退出)：”);
else
printf(“n該學生不存在，請重新輸入學號(0退出)：”);
scanf(“%d”,&m);
}
}
void chengji(struct student *head)
/*按成績查找函數*/ { 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你要查找的學生信息為： 學號 %d 成績 %fn”,p->num,p->score);
leap=1;
}
p=p->next;
}
if(leap==1)
printf(“n若繼續查找，請輸入成績(負數退出)：”);
else
printf(“n該學生不存在，請重新輸入成績(負數退出)：”);
scanf(“%f”,&m);
}
}
void seach()
/*查找子菜單*/ {
int i;
printf(“n t 1 按學號查找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選擇錯誤！請按照下面提示選擇。”);} seach();}
數據結構篇
//huffman.cpp 求Huffman編碼 #define UNIT_MAX 65535
//函數結果狀態代碼
#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0
#define INFEASIBLE-1 #define OVERFLOW-2
#include
//Status 是函數的類型，其值是函數結果狀態代碼 typedef int Status;
//Huffman樹＆Huffman編碼的存儲表示
typedef struct{ unsigned int weight;unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree;//動態分配數組存儲Huffman樹 typedef char **HuffmanCode;/* int min(HuffmanTree t,int i){ //函數void select()調用
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為最小的兩個值中序號小的那個 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++) //選出兩個權值最小的根結點 { if(t[j].parent==0) if(t[j].weight { small2=small1; //改變最小權、次小權及對應的位置 small1=t[j].weight; s2=s1; s1=j; } else { if(t[j].weight { small2=t[j].weight;//改變次小權及位置 s2=j; } } } } void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){ // 算法6.12 // w存放n個字符的權值(均>0)，構造哈夫曼樹HT，// 并求出n個字符的哈夫曼編碼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? 卡特勒數 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]); } } } 篩選法 七夕節 除了篩選素數外，還能篩選因子（倍數的運用）#include 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;} 母函數 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 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;} 貪心算法（排序函數）#incluide
點擊咨詢 