貼一個BUPT的POJ推薦50題，最近慢慢做……

 

 

POJ推薦50題

 

 

POJ == 北京大學ACM在線評測系統(tǒng) http://acm.pku.edu.cn/JudgeOnline

 

 

 

1. 標記 難 和 稍難 的題目大家可以看看，思考一下，不做要求，當然有能力的同學可以直接切掉。

 

2. 標記為 A and B 的題目是比較相似的題目，建議大家兩個一起做，可以對比總結(jié)，且二者算作一個題目。

 

3. 列表中大約有70個題目。大家選做其中的50道，且每類題目有最低數(shù)量限制。

 

4. 這里不少題目在 BUPT ACM FTP 上面都有代碼，請大家合理利用資源。

 

5. 50個題目要求每個題目都要寫總結(jié)，養(yǎng)成良好的習慣。

 

6. 這50道題的規(guī)定是我們的建議，如果大家有自己的想法請與我們 Email 聯(lián)系。

 

7. 建議使用 C++ 的同學在 POJ 上用 G++ 提交。

 

8. 形成自己編寫代碼的風格，至少看上去美觀，思路清晰(好的代碼可以很清楚反映出解題思路)。

 

9. 這個列表的目的在于讓大家對各個方面的算法有個了解，也許要求有些苛刻，教條，請大家諒解，這些是我們這些年的經(jīng)驗總結(jié)，所以也請大家尊重我們的勞動成果。

 

10. 提交要求：一個總文件夾名為 bupt0xx (即你的比賽帳號), 這個文件夾內(nèi)有各個題目類別的子目錄(文件夾)，將相應的解題報告放入對應類別的文件夾。在本學期期末，小學期開始前，將該文件夾的壓縮包發(fā)至 buptacm@gmail.com 。

 

對于每個題目只要求一個 POJxxxx.cpp 或 POJxxxx.java (xxxx表示POJ該題題號) 的文件，注意不要加入整個 project 。

 

11. 如果有同學很早做完了要求的題目，請盡快和我們聯(lián)系，我們將指導下一步的訓練。

 

 

 

下面是一個解題報告的范例：

 

例如：POJ1000.cpp

 

 

 

//考查點：會不會編程序。

 

//思路：此題要求輸入兩個數(shù)， 輸出兩個數(shù)的和，我用 scanf 和 printf。

 

//提交情況：Wrong Answer 1次，忘了寫 printf()。

 

           Compile Error 2次，選錯了語言，由于C++ 和 G++ 在 iostream.h 的不用引用方法；少一個大括號。

 

Accepted 1次。

 

//收獲：學到了 scanf, printf 的基本用法，熟悉了 OJ 的系統(tǒng)環(huán)境。

 

//經(jīng)驗： 寫好代碼后本地編譯 而且需要靜態(tài) 觀察，杜絕編譯錯誤。

 

// AC Code

 

#include <stdio.h>

 

int main() {

 

int a,b;

 

scanf("%d%d",&a,&b);

 

printf("%d\n",a+b);

 

return 0;

 

}

 

 

 

第一類 動態(tài)規(guī)劃 (至少6題，2479 and 2593必做)

 

2479 and 2593

 

1015

 

1042 (也可貪心)

 

1141

 

1050

 

1080

 

1221

 

1260

 

2411 (稍難)

 

1276

 

 

 

第二類 搜索 (至少4題)

 

1011

 

1033

 

1129

 

2049

 

2056

 

2488

 

2492 (稍難，也可并查集?)

 

 

 

第三類 貪心 (至少2題)

 

1065

 

2054 (難)

 

1521

 

2709

 

 

 

第四類 最短路 (至少3題)

 

1062

 

1125

 

1797

 

2253

 

2679 Bellman-Ford (難)

 

 

 

第五類 最小生成樹 (至少2題, 而且 Prim 和 Kruskal 至少各用一次)

 

1251

 

1258

 

1789

 

2485

 

 

 

第六類 最大流 (至少2題)

 

1087

 

1459

 

1149

 

2516 (最小費用最大流) (難)

 

 

 

第七類 二分圖 (至少3題)

 

1325

 

1469

 

2195 (KM 算法或最小費用最大流) (難)

 

2446

 

1422 and 2594

 

 

 

第八類 并查集 (至少2題)

 

1861

 

1182 (難)

 

1308

 

2524

 

 

 

第九類 快速查找 (B-Search, Hash and so on) (至少3題)

 

2503

 

2513 (+Euler回路的判定)

 

1035

 

1200

 

2002

 

 

 

第十類 數(shù)論 (至少2題)

 

1061

 

1142

 

2262

 

2407

 

1811 (難)

 

2447 (難)

 

 

 

第十一類 線段樹 (無最少題數(shù)要求)

 

2352 (可用簡單方法)

 

2528

 

 

 

第十二類 計算幾何 (至少2題，1113凸包算法必做)

 

1113

 

1292

 

2148 (難)

 

2653

 

1584

 

 

 

第十三類 高精度 (至少3題，1001必做)

 

1001

 

1047

 

1131

 

1503

 

1504

 

1060 and 1996 (多項式)

 

SCU1002, 1003, 1004 (http://acm.scu.edu.cn/soj)

 

 

 

第十四類 模擬 (至少5題)

 

1029 and 1013

 

1083 and 2028

 

2234 and 1067

 

1012

 

1026

 

1068

 

1120

 

2271

 

2632

 

 

 

第十五類 數(shù)學 (至少4題)

 

2249

 

1023

 

2506

 

1079

 

1019 and 1095

 

1905 and 1064 (二分)