ACM-ICPC 知識點 經驗

NO IMAGE
目錄

一:知識點

資料結構:
1,單,雙連結串列及迴圈連結串列
2,樹的表示與儲存,二叉樹(概念,遍歷)二叉樹的          
應用(二叉排序樹,判定樹,博弈樹,解答樹等)
3,檔案操作(從文字檔案中讀入資料並輸出到文字文       
件中)
4,圖(基本概念,儲存結構,圖的運算)
數學知識
1,離散數學知識的應用(如排列組合、簡單的圖論,數理邏輯)
2,數論知識
3,線性代數
4,組合代數
5,計算幾何

二 演算法

  1,排序演算法(冒拋法,插入排序,合併排序,快速排   
序,堆排序)
2,查詢(順序查詢,二分發)
3,回溯演算法
4,遞迴演算法
5,分治演算法
6,模擬法
7,貪心法
8,簡單搜尋演算法(深度優先,廣度優先),搜尋中的
剪枝,A*演算法
9,動態規劃的思想及基本演算法
10,高精度運算    

三、ACM競賽的題型分析

  競賽的程式設計一般只有16種型別,它們分別是:
Dynamic Programming (動態規劃) 
Greedy (貪心演算法) 
Complete Search (窮舉搜尋) 
Flood Fill (不知該如何翻譯) 
Shortest Path (最短路徑) 
Recursive Search Techniques (回溯搜尋技術) 
Minimum Spanning Tree (最小生成樹) 
Knapsack (揹包問題) 
Computational Geometry (計算幾何學) 
Network Flow (網路流) 
Eulerian Path (尤拉回路) 
Two-Dimensional Convex Hull (不知如何翻譯) 
BigNums (大數問題) 
Heuristic Search (啟發式搜尋) 
Approximate Search (近似搜尋) 
Ad Hoc Problems (雜題) 

四 ACM競賽參考書

  《實用演算法的分析與程式設計》  (吳文虎,王建德著,電子工業出版社,競賽類的黑寶書)
《青少年國際和全國資訊學(計算機)奧林匹克競賽指導)――組合數學的演算法
和程式設計》(吳文虎,王建德著,清華大學出版社,參加競賽組合數學必學)
《計算機演算法設計與分析》      (王曉東編著,最好的資料結構教材)
《資料結構與演算法》           (傅清祥,王曉東編著,我所見過的最好的演算法教材)
《資訊學奧林匹克競賽指導――1997-1998競賽試題解析》(吳文虎,王建德著,清華大學出版社)
《計算機程式設計技巧》    D.E.Kruth著,演算法書中最著名的《葵花寶典》,大師的作品,難度大)
《計算幾何》周陪德著
《ACM國際大學生程式設計競賽試題與解析(一)》  (吳文虎著,清華大學出版社)
《數學建模競賽培訓教材》         共三本 葉其孝主編
《數學模型》                    第二版 姜啟源
《隨機規劃》 
《模糊數學》 
《數學建模入門》                徐全智
《計算機演算法設計與分析》       國防科大    

五 常見的幾個網上題庫

   常用網站:
1)資訊學初學者之家:http://oibh.ioiforum.org/
(2)大榕樹程式設計世界:http://www.fjsdfz.org/~drs/program/default.asp
(3)中國教育曙光網:http://www.chinaschool.org/aosai/
(4)福建資訊學奧林匹克:http://www.cfcs.com.cn/fjas/index.htm
(5)第20屆全國青少年資訊學奧林匹克競賽:http://www.noi2003.org/
(6)第15屆國際青少年資訊學奧林匹克競賽:http://www.ioi2003.org/
(7)全美計算機奧林匹克競賽:http://ace.delos.com/usacogate
(8)美國資訊學奧林匹克競賽官方網站:http://www.usaco.org/
(9)俄羅斯Ural州立大學:http://acm.timus.ru/
(10)西班牙Valladolid大學:http://acm.uva.es/problemset
(11)ACM-ICPC:http://icpc.baylor.edu/icpc/
(12)北京大學:http://acm.pku.edu.cn/JudgeOnline/index.acm
(13)浙江大學:http://acm.zju.edu.cn/
(14)IOI:http://olympiads.win.tue.nl/ioi/
(15)2003年江蘇省資訊學奧林匹克競賽夏令營:http://jsoi.czyz.com.cn
(16)http://acm.zju.edu.cn
(17)http://acm.zsu.edu.cn
(18)www.shumo.com
(19)http://www.bepark.com/downldmanag/index.asp
(20)http://www.yh01.com    colin_fox/colin_fox 

六 如何備戰ACM/ICPC

    1,個人準備(演算法書,習題集,網上做題和討論)
2,1000題=亞洲冠軍=世界決賽
3,做好資料收集和整理工作

實驗一:遞迴與分治

1. 二分查詢
2. 合併排序
3. 快速排序

實驗二:回溯

1. 0-1揹包問題
2. 裝載問題
3. 堡壘問題(ZOJ1002)
4. *翻硬幣問題
5. 8皇后問題
6. 素數環問題
7. 迷宮問題
8. *農場灌溉問題(ZOJ2412)
9. *求影象的周長(ZOJ1047)
10. *骨牌矩陣
11. *字母轉換(ZOJ1003)
12. *踩氣球(ZOJ1004)

實驗三:搜尋

1. Floodfill
2. 電子老鼠闖迷宮
3. 跳馬
4. 獨輪車
5. 皇宮小偷
6. 分酒問題
7. *找倍數
8. *8數碼難題

實驗四:動態規劃

1. 最長公共子序列
2. 計算矩陣連乘積
3. 凸多邊形的最優三角剖分
4. 防衛導彈
5. *石子合併
6. *最小代價子母樹
7. *旅遊預算
8. *皇宮看守
9. *遊戲室問題
10. *基因問題
11. *田忌賽馬

實驗五:貪心與隨機演算法

1. 揹包問題
2. 搬桌子問題
3. *照亮的山景
4. *用隨即演算法求解8皇后問題
5. 素數測試

實驗一:遞迴與分治

實驗目的
理解遞迴演算法的思想和遞迴程式的執行過程,並能熟練編寫遞迴程式。
掌握分治演算法的思想,對給定的問題能設計出分治演算法予以解決。
實驗預習內容
程式設計實現講過的例題:二分搜尋、合併排序、快速排序。
對本實驗中的問題,設計出演算法並程式設計實現。
試驗內容和步驟
1. 二分查詢
在對線性表的操作中,經常需要查詢某一個元素線上性表中的位置。此問題的輸入是待查元素x和線性表L,輸出為x在L中的位置或者x不在L中的資訊。
程式略
2. 合併排序
程式略
3. 快速排序
程式略
實驗總結及思考
合併排序的遞迴程式執行的過程

實驗二:回溯演算法

實驗目的:熟練掌握回溯演算法
實驗內容:回溯演算法的幾種形式
    a) 用回溯演算法搜尋子集樹的一般模式
void search(int m)
{
if(m>n)           //遞迴結束條件 
output();      //相應的處理(輸出結果)
else{
a[m]=0;       //設定狀態:0表示不要該物品
search(m 1);   //遞迴搜尋:繼續確定下一個物品
a[m]=1;       //設定狀態:1表示要該物品
search(m 1);   //遞迴搜尋:繼續確定下一個物品
}
}
b) 用回溯演算法搜尋子集樹的一般模式
void search(int m)
{
if(m>n)               //遞迴結束條件 
output();          //相應的處理(輸出結果)
else
for(i=m;i<=n;i  ){
swap(m,i);     //交換a[m]和a[i]
if()
if(canplace(m))  //如果m處可放置
search(m 1); //搜尋下一層
swpa(m,i);     //交換a[m]和a[i](換回來)
}
}

習題

1. 0-1揹包問題

在0 / 1揹包問題中,需對容量為c 的揹包進行裝載。從n 個物品中選取裝入揹包的物品,每件物品i 的重量為wi ,價值為pi 。對於可行的揹包裝載,揹包中物品的總重量不能超過揹包的容量,最佳裝載是指所裝入的物品價值最高。 程式如下:
    #include
void readdata();
void search(int);
void checkmax();
void printresult();
int c=35, n=10;        //c: 揹包容量;n:物品數
int w[10], v[10];       //w[i]、v[i]:第i件物品的重量和價值
int a[10], max;        //a陣列存放當前解各物品選取情況;max:記錄最大價值
//a[i]=0表示不選第i件物品,a[i]=1表示選第i件物品
int main()
{
readdata();       //讀入資料
search(0);        //遞迴搜尋
printresult();
}
void search(int m)
{
if(m>=n)
checkmax();   //檢查當前解是否是可行解,若是則把它的價值與max比較
else
{
a[m]=0;       //不選第m件物品
search(m 1);  //遞迴搜尋下一件物品
a[m]=1;       //不選第m件物品
search(m 1);  //遞迴搜尋下一件物品
}
}
void checkmax()
{
int i, weight=0, value=0;
for(i=0;i
{
if(a[i]==1)                 //如果選取了該物品
{
weight = weight   w[i];  //累加重量
value = value   v[i];     //累加價值
}
}
if(weight<=c)                  //若為可行解
if(value>max)              //且價值大於max
max=value;            //替換max
}
void readdata()
{
int i;
for(i=0;i
scanf("%d%d",&w[i],&v[i]);   //讀入第i件物品重量和價值
}
void printresult()
{
printf("%d",max);
}

2. 裝載問題

有兩艘船,載重量分別是c1、 c2,n個集裝箱,重量是wi (i=1…n),且所有集裝箱的總重量不超過c1 c2。確定是否有可能將所有集裝箱全部裝入兩艘船。
提示:求出不超過c1的最大值max,若總重量-max < c2則能裝入到兩艘船。

3. 堡壘問題(ZOJ1002)

如圖城堡是一個4×4的方格,為了保衛城堡,現需要在某些格子裡修建一些堡壘。城堡中的某些格子是牆,其餘格子都是空格,堡壘只能建在空格里,每個堡壘都可以向上下左右四個方向射擊,如果兩個堡壘在同一行或同一列,且中間沒有牆相隔,則兩個堡壘都會把對方打掉。問對於給定的一種狀態,最多能夠修建幾個堡壘。程式主要部分如下:
int main()
{
readdata();           //讀入資料
search(0);            //遞迴搜尋
printresult();
}
void search(int m)
{
int row, col;
row=m/n;              //求第m個格子的行號
col=m%n;              //求第m個格子的列號
if(m>=n*n)
checkmax();       //檢查當前解是否是可行解,若是則把它的價值與max比較
else
{
search(m 1);      //該位置不放堡壘遞迴搜尋下一個位置
if(canplace(m))    //判斷第m個格子是否能放堡壘
{
place(m);     //在第m個格子上放置一個堡壘
search(m 1);  //遞迴搜尋下一個位置
takeout(m);   //去掉第m個格子上放置的堡壘
}
}
}

4. 翻硬幣問題

把硬幣擺放成32×9的矩陣,你可以隨意翻轉矩陣中的某些行和某些列,問正面朝上的硬幣最多有多少枚?
提示:(1)任意一行或一列,翻兩次等於沒有翻;
(2)對於9列的任何一種翻轉的情況,每一行翻與不翻相互獨立。

5.八皇后問題

在一個8×8的棋盤裡放置8個皇后,要求這8個皇后兩兩之間互相都不“衝突”。
        #include
#include
void search(int);
void printresult();       //列印結果
int canplace(int,int);     //判斷該位置能否放置皇后
void place(int,int);      //在該位置能否放置皇后
void takeout(int,int);    //把該位置放置皇后去掉
int a[8];              //a[i]存放第i個皇后的位置
int main()
{
search(0);            //遞迴搜尋
}
void search(int m)
{
int i;
if(m>=8)                //當已經找出一組解時
printresult();         //輸出當前結果
else
{
for(i=0;i<8;i  )        //對當前行0到7列的每一個位置
{
if(canplace(m,i))   //判斷第m個格子是否能放堡壘
{
place(m,i);    //在(m,i)格子上放置一個皇后
search(m 1);  //遞迴搜尋下一行
takeout(m,i);  //把(m,i)格子上的皇后去掉
}
}
}
}
int canplace(int row, int col)
{
int i;
for(i=0;i
if(abs(i-row)==abs(a[i]-col)||a[i]==col)
return(0);
return(1);
}
void place(int row, int col)
{
a[row]=col;
}
void takeout(int row, int col)
{
a[row]=-1;
}
void printresult()
{
int i,j;
for(i=0;i<8;i  )
{
for(j=0;j<8;j  )
if(a[i]==j)
printf(" A ");
else
printf(" . ");
printf("\n");
}
printf("\n");
}

6. 素數環問題

把從1到20這20個數擺成一個環,要求相鄰的兩個數的和是一個素數。
分析:用回溯演算法,考察所有可能的排列。
程式如下:
    #include
#include
void search(int);
void init();              //初始化
void printresult();        //列印結果
int isprime(int);         //判斷該數是否是素數
void swap(int,int);       //交換a[m]和a[i]
int a[21];                //a陣列存放素數環
int main()
{
init();
search(2);            //遞迴搜尋
}
int isprime(int num)
{
int i,k;
k=sqrt(num);
for(i=2;i<=k;i  )
if(num%i==0)
return(0);
return(1);
}
void printresult()
{
int i;
for(i=1;i<=20;i  )
printf("=",a[i]);
printf("\n");
}
void search(int m)
{
int i;
if(m>20)                       //當已經搜尋到葉結點時
{
if(isprime(a[1] a[20]))        //如果a[1] a[20]也是素數
printresult();            //輸出當前解
return;
}
else
{
for(i=m;i<=20;i  )           //(排列樹)
{
swap(m,i);              //交換a[m]和a[i]
if(isprime(a[m-1] a[m]))  //判斷a[m-1] a[m]是否是素數
search(m 1);       //遞迴搜尋下一個位置
swap(m,i);             //把a[m]和a[i]換回來
}
}
}
void swap(int m, int i)
{
int t;
t=a[m];
a[m]=a[i];
a[i]=t;
}
void init()
{
int i;
for(i=0;i<21;i  )
a[i]=i;
}

7. 迷宮問題

給一個20×20的迷宮、起點座標和終點座標,問從起點是否能到達終點。
輸入資料:’.’表示空格;’X’表示牆。
程式如下:
    #include
#include
void search(int,int);
int canplace(int,int);
void readdata();           //讀入資料
void printresult();        //列印結果
int a[20][20];             //a陣列存放迷宮
int s,t;
int main()
{
int row, col;
readdata();
row=s/20;
col=s ;
search(row,col);        //遞迴搜尋
printresult();
}
void search(int row, int col)
{
int r,c;
a[row][col]=1;
r=row;                  //左
c=col-1;
if(canplace(r,c))        //判斷(r,c)位置是否已經走過
search(r,c);        //遞迴搜尋(r,c)
r=row 1;                //下
c=col;
if(canplace(r,c))        //判斷(r,c)位置是否已經走過
search(r,c);        //遞迴搜尋(r,c)
r=row;                  //右
c=col 1;
if(canplace(r,c))        //判斷(r,c)位置是否已經走過
search(r,c);        //遞迴搜尋(r,c)
r=row-1;                //上
c=col;
if(canplace(r,c))        //判斷(r,c)位置是否已經走過
search(r,c);        //遞迴搜尋(r,c)
}
void printresult()
{
int i,j;
for(i=0;i<20;i  )
{
for(j=0;j<20;j  )
printf("=",a[i][j]);
printf("\n");
}
}
void readdata()
{
int i,j;
for(i=0;i<20;i  )
{
for(j=0;j<20;j  )
scanf("%d",&a[i][j]);
}
}
int canplace(int row, int col)
{
if(row>=0&&row<20&&col>=0&&col<20&&a[row][col]==0)
return 1;
else
return 0;
}

8. 農場灌溉問題(ZOJ2412)

一農場由圖所示的十一種小方塊組成,藍色線條為灌溉渠。若相鄰兩塊的灌溉渠相連則只需一口水井灌溉。給出若干由字母表示的最大不超過50×50具體由(m,n)表示,的農場圖,程式設計求出最小需要打的井數。每個測例的輸出佔一行。當M=N=-1時結束程式。
Sample Input
2 2
DK
HF
3 3
ADC
FJK
IHE
-1 -1
Sample Output
2
3
提示:參考迷宮問題,實現時關鍵要解決好各塊的表示問題。

9. 求影象的周長(ZOJ1047)

給一個用 . 和X表示的圖形,圖形在上、下、左、右、左上、左下、右上、右下8個方向都被看作是連通的,並且影象中間不會出現空洞,求這個圖形的邊長。
輸入:首先給出m、n、x、y四個正整數,下面給出m×n的圖形,x、y表示點選的位置,全0表示結束。
輸出:點選的圖形的周長。
Sample Input
2 2 2 2
XX
XX
6 4 2 3
.XXX
.XXX
.XXX
...X
..X.
X...
0 0 0 0 
Sample output
8
18
提示:參考迷宮問題,區別在於它是向8個方向填。

10. 骨牌矩陣

多米諾骨牌是一個小正方形方塊,每個骨牌都標有一個數字(0~6),現在有28組骨牌,每組兩個,各組編號為1~28,每組編號對應的兩個骨牌數值如下:
00  01  02  03  04  05  06
11  12  13  14  15  16  22
23  24  25  26  33  34  35
36  44  45  46  55  56  66
現將這28組骨牌排成一個7×8矩陣,此時只能看到每個骨牌上的數字(0~6),而不能知道每組的組號(如左下圖所示)。請程式設計序將每組骨牌分辨出來(如右下圖所示)。
7X8骨牌矩陣        骨牌組編號矩陣
66265241               28  28  14   7  17  17  11  11
13201034               10  10  14   7   2   2  21  23
13246654                8   4  16  25  25  13  21  23
10432112                8   4  16  15  15  13   9   9
51360455               12  12  22  22   5   5  26  26
55402603               27  24  24   3   3  18   1  19
60534203               27   6   6  20  20  18   1  19
void search(int n)
{
查詢下一個還沒放置骨牌的位置(x,y);
若沒有,則表示已經找到一個解,輸出並且返回;
嘗試放置骨牌; 
兩次嘗試都失敗,進行回溯;
}
嘗試放置骨牌
? 把在(x,y)處的骨牌作為當前骨牌組的一個骨牌;
? 把(x 1,y)處的骨牌作為當前骨牌組的另一個骨牌;
? 判斷當前骨牌組是夠未被使用,如果未被使用則遞迴放置下一個骨牌組;
? 把(x,y  1)處的骨牌作為當前骨牌組的另一個骨牌;
? 判斷當前骨牌組是否未被使用,如果未被使用則遞迴放置下一個骨牌組;

11. 字母轉換(ZOJ1003)

通過棧交換字母順序。給定兩個字串,要求所有的進棧和出棧序列(i表示進棧,o表示出棧),使得字串2在求得的進出棧序列的操作下,變成字串1。輸出結果需滿足字典序。例如TROT 到 TORT: 
[
i i i i o o o o
i o i i o o i o
]
Sample Input
madam
adamm
bahama
bahama
long
short
eric
rice
Sample Output
[
i i i i o o o i o o 
i i i i o o o o i o 
i i o i o i o i o o 
i i o i o i o o i o 
]
[
i o i i i o o i i o o o 
i o i i i o o o i o i o 
i o i o i o i i i o o o 
i o i o i o i o i o i o 
]
[
]
[
i i o i o i o o 
]

12. 踩氣球(ZOJ1004)

六一兒童節,小朋友們做踩氣球遊戲,氣球的編號是1~100,兩位小朋友各踩了一些氣球,要求他們報出自己所踩氣球的編號的乘積。現在需要你編一個程式來判斷他們的勝負,判斷的規則是這樣的:如果兩人都說了真話,數字大的人贏;如果兩人都說了假話,數字大的人贏;如果報小數字的人說的是真話而報大數字的人說謊,則報小數字的人贏(注意:只要所報的小數字是有可能的,即認為此人說了真話)。
輸入為兩個數字,0 0表示結束;
輸出為獲勝的數字。
Sample Input
36 62
49 343
0 0
Sample Output
62
49

實驗三:搜尋演算法

實驗目的:熟練掌握搜尋演算法
實驗內容:廣度優先搜尋
搜尋演算法的一般模式:
    void search()
{
closed表初始化為空;
open表初始化為空;
起點加入到open表;
while( open表非空 )
{
取open表中的一個結點u;
從open表中刪除u;
u進入closed表;
for( 對擴充套件結點u得到的每個新結點vi )
{
if(vi是目標結點)
輸出結果並返回;
if vi 的狀態與closed表和open表中的結點的狀態都不相同
vi進入open表;
}
}
}
搜尋演算法關鍵要解決好狀態判重的問題,這樣可省略closed表,一般模式可改為:
void search()
{
open表初始化為空;
起點加入到open表;
while( open表非空 )
{
取open表中的一個結點u;
從open表中刪除u;
for( 對擴充套件結點u得到的每個新結點vi )
{
if(vi是目標結點)
輸出結果並返回;
If(notused(vi))
vi進入open表;
}
}
}

1. Floodfill

給一個20×20的迷宮和一個起點座標,用廣度優先搜尋填充所有的可到達的格子。
提示:參考第2題。

2. 電子老鼠闖迷宮

如下圖12×12方格圖,找出一條自入口(2,9)到出口(11,8)的最短路徑。
本題給出完整的程式和一組測試資料。狀態:老鼠所在的行、列。程式如下:
    #include
void readdata();              //讀入資料
void init();                  //初始化
int search();                 //廣搜,並在每一個可到達的每一個空格出填上最小步數
int emptyopen();             //判棧是否為空:空:1;非空:0。
int takeoutofopen();          //從棧中取出一個元素,並把該元素從棧中刪除
int canmoveto(int,int,int*,int*,int);  //判能否移動到該方向,並帶回座標(r,c)
int isaim(int row, int col);         //判斷該點是否是目標
int used(int,int);                //判斷該點是否已經走過
void addtoopen(int,int);          //把該點加入到open表
int a[12][12];       //a存放迷宮,0表示空格,-2表示牆。
//廣搜時,未找到目標以前到達的空格,填上到達該點的最小步數
int n;             //n為迷宮邊長,注:若大於12,必須修改一些引數,如a的大小
int open[20],head,tail,openlen=20;  //open表
int s,t;                         //起點和終點
int main()
{
int number;
readdata();            //讀取資料
init();                //初始化
number=search();      //廣搜並返回最小步數
printf("%d",number);   //列印結果
}
int search()
{
int u, row, col, r, c, i, num;
while(!emptyopen())         //當棧非空
{
u=takeoutofopen();      //從棧中取出一個元素,並把該元素從棧中刪除
row=u/n;              //計算該點的座標
col=u%n;
num=a[row][col];       //取得該點的步數
for(i=0;i<4;i  )
{
if(canmoveto(row,col,&r,&c,i))  //判能否移動到該方向,並帶回座標(r,c)
{
if(isaim(r,c))            //如果是目標結點
return(num 1);      //返回最小步數
if(!used(r,c))            //如果(r,c)還未到達過
{
a[r][c]=num 1;      //記錄該點的最小步數
addtoopen(r,c);      //把該點加入到open表
}
}
}
}
}
int emptyopen()
{
if(head==tail)
return(1);
else
return(0);
}
int takeoutofopen()
{
int u;
if(head==tail)
{
printf("errer: stack is empty");
return(-1);
}
u=open[head  ];
head=head%openlen;
return(u);
}
int canmoveto(int row, int col, int *p, int *q, int direction)
{
int r,c;
r=row;
c=col;
switch(direction)
{
case 0: c--;            //左
break;
case 1: r  ;           //下
break;
case 2: c  ;           //右
break;
case 3: r--;            //上
}
*p=r;
*q=c;
if(r<0||r>=n||c<0||c>=n)   //如果越界返回0
return(0);
if(a[r][c]==0)           //如果是空格返回1
return(1);
return(0);              //其餘情況返回0
}
int isaim(int row, int col)
{
if(row*n col==t)
return(1);
else
return(0);
}
int used(int row, int col)
{
if(a[row][col]==0)      // 0表示空格
return(0);
else
return(1);
}
void addtoopen(int row, int col)
{
int u;
u=row*n col;
open[tail  ]= u;
tail=tail%openlen;
}
void readdata()
{
int i,j,row,col;
char str[20];
scanf("%d",&n);
scanf("%d%d",&row,&col);  //起點座標
s=row*n col;
scanf("%d%d",&row,&col);  //終點座標
t=row*n col;
gets(str);
for(i=0;i
{
gets(str);
for(j=0;j
if(str[j]=='.')
a[i][j]=0;   //0表示空格
else
a[i][j]=-2;  //-2表示牆
}
}
void init()
{
head=0;
tail=1;
open[0]=s;
}
測試資料如下:
12 10 7 1 8
XXXXXXXXXXXX
X......X.XXX
X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX
注:測試資料可在執行時貼上上去(點選視窗最左上角按鈕,在選單中選則“編輯”/“貼上”即可)。
想一想:此程式都存在哪些問題,如果openlen太小程式會不會出錯,加入程式碼使程式能自動報出此類錯誤。

3. 跳馬

給一個200×200的棋盤,問國際象棋的馬從給定的起點到給定的終點最少需要幾步。
Sample Input  0 0 1 1  Sample output  4
狀態:馬所在的行、列。
程式如下:
#include
void readdata();                //讀入資料
void init();                    //初始化
int search();                   //廣度優先搜尋
int emptyopen();                //判棧是否為空:空:1;非空:0。
long takeoutofopen();           //從棧中取出一個元素,並把該元素從棧中刪除
int canmoveto(int,int,int*,int*,int);    //判能否移動到該方向,並帶回座標(r,c)
int isaim(int row, int col);             //判斷該點是否是目標
int used(int,int);                       //判斷該點是否已經走過
void addtoopen(int,int);                 //把該點加入到open表
int a[200][200],n=200;                   //a存放棋盤,n為迷宮邊長
long open[2000],head,tail,openlen=2000;  //open表1367
long s,t;                                //起點和終點
int search()
{
long u;
int row, col, r, c, i, num;
while(!emptyopen())         //當棧非空
{
u=takeoutofopen();      //從棧中取出一個元素,並把該元素從棧中刪除
row=u/n;              //計算該點所在的行
col=u%n;             //計算該點所在的列
num=a[row][col];      //取得該點的步數
for(i=0;i<8;i  )
{
if(canmoveto(row,col,&r,&c,i))   //判能否移動到該方向,並帶回座標(r,c)
{
if(isaim(r,c))              //如果是目標結點
return(num 1);       //返回最小步數
if(!used(r,c))              //如果(r,c)還未到達過
{
a[r][c]=num 1;       //記錄該點的最小步數
addtoopen(r,c);       //把該點加入到open表
}
}
}
}
return -1;
}
int main()                //為了讓search()顯示在一頁內和main函式換了以下
{                       //一般的演算法程式main函式寫在最上面讀起來更方便
int number;
readdata();           //讀取資料
init();               //初始化
number=search();     //廣搜並返回最小步數
printf("%d",number);  //列印結果
}
int emptyopen()
{
if(head==tail)
return(1);
else
return(0);
}
long takeoutofopen()
{
long u;
if(head==tail)
{
printf("errer: stack is empty");
return(-1);
}
u=open[head  ];
head=head%openlen;
return(u);
}
int used(int row, int col)
{
if(a[row][col]==0)
return(0);
else
return(1);
}
void addtoopen(int row, int col)
{
int u;
if((head-tail)%openlen==1)
printf("open table overflow");
u=row;
u=u*n col;
open[tail  ]= u;
tail=tail%openlen;
}
void readdata()
{
long row,col;
scanf("%ld%ld",&row,&col);  //起點座標
s=row*n col;
scanf("%ld%ld",&row,&col);  //終點座標
t=row*n col;
}
void init()
{
head=0;
tail=1;
open[0]=s;
}
int isaim(int row, int col)
{
if(row*n col==t)
return(1);
else
return(0);
}
思考:參考第4題,改為用結構體表示狀態寫此程式。

4. 獨輪車

獨輪車的輪子上有5種顏色,每走一格顏色變化一次,獨輪車只能往前推,也可以在原地旋轉,每走一格,需要一個單位的時間,每轉90度需要一個單位的時間,轉180度需要兩個單位的時間。現給定一個20×20的迷宮、一個起點、一個終點和到達終點的顏色,問獨輪車最少需要多少時間到達。
狀態:獨輪車所在的行、列、當前顏色、方向。
另外為了方便在結點中加上到達該點的最小步數。
程式如下:
#include
struct colornode
{
int row;                        //該狀態的行
int col;                         //        列
int color;                       //        顏色
int direction;                    //        方向
int num;                       //        最小步數
};
int search();                        //廣搜返回目標結點的最小步數
void readdata();                     //讀入資料
void init();                         //初始化
struct colornode moveahead(struct colornode u);  //返回u向前走一格得到的結點
int used(struct colornode v);        //判斷該結點是否是到達過的結點
void addtoopen(struct colornode v);  //加入到open表
int islegal(struct colornode v);      //如果該結點是合法的結點(未越界且是空格)
int isaim(struct colornode v);       //判斷該結點是否是目標結點
struct colornode takeoutofopen();    //從open表中取出一個結點並把該結點從open表中刪除
struct colornode turntoleft(struct colornode u);     //u向左轉得到新結點v
struct colornode turntoright(struct colornode u);    //u向左轉得到新結點v
struct colornode s,t;                //s:起始結點;t目標結點
struct colornode open[200];          //open表
int head,tail,openlen=200;           //open表相關資料
int direct[4][2]={{0,-1},{1,0},{0,1},{-1,0}};//向左、下、右、上四個方向轉時,行列的增加值
int a[20][20],n=20;                  //a陣列表示迷宮;n為迷宮邊長
int b[20][20][5][4];                 //b陣列表示搜尋時的所有狀態(0:未訪問;1:已訪問)
int main()
{
int number;
readdata();
init();
number=search();
printf("%d\n",number);
}
int search()                        //廣搜返回目標結點的最小步數
{
struct colornode u,v;
while(head!=tail)
{
u=takeoutofopen();
v=moveahead(u);          //u向前走一格得到新結點v
if(islegal(v))                  //如果該結點是合法的結點(未越界且是空格)
{
if(isaim(v))               //判是否是目標結點
return(v.num);
if(!used(v))               //如果是未到達過的結點
addtoopen(v);        //加入到open表
}
v=turntoleft(u);           //u向左轉得到新結點v
if(!used(v))
addtoopen(v);
v=turntoright(u);         //u向右轉得到新結點v
if(!used(v))
addtoopen(v);
}
}
int used(struct colornode v)        //判斷該結點是否是到達過的結點
{
if(b[v.row][v.col][v.color][v.direction]==0)
return(0);
else
return(1);
}
void addtoopen(struct colornode v)  //加入到open表
{
open[tail  ]=v;
tail=tail%openlen;
b[v.row][v.col][v.color][v.direction]=1;
}
struct colornode takeoutofopen()    //從open表中取出一個結點並把該結點從open表中刪除
{
struct colornode v;
v=open[head  ];
head=head%openlen;
return(v);
}
void init()                         //初始化
{
int i,j,k,l;
for(i=0;i
for(j=0;j
for(k=0;k<5;k  )
for(l=0;l<4;l  )
b[i][j][k][l]=0;
head=0;
tail=0;
addtoopen(s);                   //把起始點加入到open表
}
void readdata()                     //讀入資料
{
char str[50]; int i,j;
for(i=0;i
{
gets(str);
for(j=0;j
if(str[j]=='.')          //讀入資料'.'表示空格
a[i][j]=0;           //儲存時  0:表示空格
else
a[i][j]=1;           //        1:表示牆
}
scanf("%d%d%d%d",&s.row,&s.col,&s.color,&s.direction);  //讀入起始結點資訊
scanf("%d%d%d",&t.row,&t.col,&t.color);                 //讀入目標結點資訊
}
int isaim(struct colornode v)       //判斷該結點是否是目標結點
{
if(v.row==t.row&&v.col==t.col&&v.color==t.color)
return 1;
else
return 0;
}
int islegal(struct colornode v)     //如果該結點是合法的結點(未越界且是空格)
{
if(v.row<0||v.row>=n||v.col<0||v.col>=n)  //若越界
return 0;
if(a[v.row][v.col]==0)                 //0:表示空格
return 1;
return 0;
}
struct colornode moveahead(struct colornode u)  //返回u向前走一格得到的結點
{
struct colornode v;
v.row=u.row direct[u.direction][0];
v.col=u.col direct[u.direction][1];
v.color=(u.color 1)%5;
v.direction=u.direction;
v.num=u.num 1;
return(v);
}
struct colornode turntoleft(struct colornode u)     //u向左轉得到新結點v
{
struct colornode v;
v=u;
v.direction=(v.direction 1)%4;
v.num=v.num 1;
return(v);
}
struct colornode turntoright(struct colornode u)     //u向左轉得到新結點v
{
struct colornode v;
v=u;
v.direction=(v.direction 3)%4;
v.num=v.num 1;
return(v);
}
測試資料:
XXXXXXXXXXXXXXXXXXXX
.....XXXX......X.XXX
X.........X.XX.....X
X.XXX.XX..X.XX.XXX.X
X.........X.XX.....X
X.XXX.XX..X.XX.XXX.X
.X.....XX.X.....X..X
X....X..X...X.X....X
...XXXX.X.XXX...XXXX
...........X.......X
XXXXXX....XXXXXX..XX
...........X.......X
.X.....XX.X.....X..X
XXXXXX....XXXXXXXX.X
X....X..X...X.X....X
...XXXX.X.XXX...XXXX
...........X.......X
XXX.X.XXXXX.XXXX.X.X
....X.XX....XXX.....
XXXX.....XX.........
1 1 1 1 4 8 1

5. 皇宮小偷

有一個小偷要到皇宮裡偷取寶物,經過仔細的偵察,他發現皇宮實際上是一個20×20的迷宮,並且有一名衛兵巡邏,衛兵巡邏的路線是固定的,每單位時間移動一格,每4個單位時間迴圈一次。小偷每單位時間移動一格或在原地不動。任何時刻,小偷和衛兵在同一格,或衛兵能看到小偷,小偷將會被衛兵殺死。現在小偷已經得到了皇宮的地圖,衛兵巡邏的起點,衛兵連續四次移動的方向和寶物的位置,請你設計一個程式判斷小偷能否偷得寶物。
提示:參考第3題、第4題

6. 分酒問題

有一酒瓶裝有8斤酒,沒有量器,只有分別裝5斤和3斤的空酒瓶。設計一程式將8斤酒分成兩個4斤,並以最少的步驟給出答案。

7. 找倍數

對於每個輸入的數字(如:2),則要求 給出一個由1,0構成的十進位制整數,且該整數為輸入數字的某個倍數(如2對應的10,6的倍數100100100100100100)。

8. 8數碼難題

由左圖變到右圖最少需要幾步,並演示移動過程。

實驗四:動態規劃

實驗目的:理解動態規劃的基本思想,理解動態規劃演算法的兩個基本要素最優子結構性質和子問題的重疊性質。熟練掌握典型的動態規劃問題。掌握動態規劃思想分析問題的一般方法,對較簡單的問題能正確分析,設計出動態規劃演算法,並能快速程式設計實現。
實驗內容:程式設計實現講過的例題:最長公共子序列問題、矩陣連乘問題、凸多邊形最優三角剖分問題、電路佈線問題等。本實驗中的問題,設計出演算法並程式設計實現。
習題

1. 最長公共子序列

一個給定序列的子序列是在該序列中刪去若干元素後得到的序列。確切地說,若給定序列X=,則另一序列Z=是X的子序列是指存在一個嚴格遞增的下標序列 ,使得對於所有j=1,2,…,k有
解答如下:
a) 最長公共子序列的結構
若用窮舉搜尋法,耗時太長,演算法需要指數時間。
易證最長公共子序列問題也有最優子結構性質
設序列X=和Y=的一個最長公共子序列Z=,則:
i. 若xm=yn,則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列; 
ii. 若xm≠yn且zk≠xm ,則Z是Xm-1和Y的最長公共子序列; 
iii. 若xm≠yn且zk≠yn ,則Z是X和Yn-1的最長公共子序列。 
其中Xm-1=,Yn-1=,Zk-1=。
最長公共子序列問題具有最優子結構性質。

b) 子問題的遞迴結構

由最長公共子序列問題的最優子結構性質可知,要找出X=和Y=的最長公共子序列,可按以下方式遞迴地進行:當xm=yn時,找出Xm-1和Yn-1的最長公共子序列,然後在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。當xm≠yn時,必須解兩個子問題,即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。
由此遞迴結構容易看到最長公共子序列問題具有子問題重疊性質。例如,在計算X和Y的最長公共子序列時,可能要計算出X和Yn-1及Xm-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題,即計算Xm-1和Yn-1的最長公共子序列。
我們來建立子問題的最優值的遞迴關係。用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=,Yj=。當i=0或j=0時,空序列是Xi和Yj的最長公共子序列,故c[i,j]=0。建立遞迴關係如下:

c) 計算最優值

由於在所考慮的子問題空間中,總共只有θ(m*n)個不同的子問題,因此,用動態規劃演算法自底向上地計算最優值能提高演算法的效率。
計算最長公共子序列長度的動態規劃演算法LCS_LENGTH(X,Y)以序列X=和Y=作為輸入。輸出兩個陣列c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]儲存Xi與Yj的最長公共子序列的長度,b[i,j]記錄指示c[i,j]的值是由哪一個子問題的解達到的,這在構造最長公共子序列時要用到。最後,X和Y的最長公共子序列的長度記錄於c[m,n]中。
程式如下:
#include
#include
int lcs_length(char x[], char y[]);
int main()
{
char x[100],y[100];
int len;
while(1)
{
scanf("%s%s",x,y);
if(x[0]=='0')           //約定第一個字串以‘0’開始表示結束
break;
len=lcs_length(x,y);
printf("%d\n",len);
}
}
int lcs_length(char x[], char y[] )
{
int m,n,i,j,l[100][100];
m=strlen(x);
n=strlen(y);
for(i=0;i
l[i][0]=0;
for(j=0;j
l[0][j]=0;
for(i=1;i<=m;i  )
for(j=1;j<=n;j  )
if(x[i-1]==y[j-1])     //i,j從1開始,但字串是從0開始
l[i][j]=l[i-1][j-1] 1;
else if(l[i][j-1]>l[i-1][j])
l[i][j]=l[i][j-1];
else
l[i][j]=l[i-1][j];
return l[m][n];
}
由於每個陣列單元的計算耗費Ο(1)時間,演算法lcs_length耗時Ο(mn)。
思考:空間能節約嗎?

2. 計算矩陣連乘積

在科學計算中經常要計算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數等於矩陣B的行數。若A是一個p×q的矩陣,B是一個q×r的矩陣,則其乘積C=AB是一個p×r的矩陣。由該公式知計算C=AB總共需要pqr次的數乘。其標準計算公式為:
現在的問題是,給定n個矩陣{A1,A2,…,An}。其中Ai與Ai 1是可乘的,i=1,2,…,n-1。要求計算出這n個矩陣的連乘積A1A2…An。
遞迴公式:  
程式如下:
#include
int main()
{
int p[101],i,j,k,r,t,n;
int m[101][101];            //為了跟講解時保持一致陣列從1開始
int s[101][101];            //記錄從第i到第j個矩陣連乘的斷開位置
scanf("%d",&n);
for(i=0;i<=n;i  ) 
scanf("%d",&p[i]);      //讀入p[i]的值(注意:p[0]到p[n]共n 1項)
for(i=1;i<=n;i  )           //初始化m[i][i]=0
m[i][i]=0;
for(r=1;r
for(i=1;i
{
j=i r;              //j為列
m[i][j]=m[i 1][j] p[i-1]*p[i]*p[j];    //給m[i][j]賦初值
s[i][j]=i;
for(k=i 1;k
{
t=m[i][k] m[k 1][j] p[i-1]*p[k]*p[j];
if(t
{
m[i][j]=t;                //m[i][j]取最小值
s[i][j]=k;
}
}
}
printf("%d",m[1][n]);
}

3. 凸多邊形的最優三角剖分

   多邊形是平面上一條分段線性的閉曲線。也就是說,多邊形是由一系列首尾相接的直線段組成的。組成多邊形的各直線段稱為該多邊形的邊。多邊形相接兩條邊的連線點稱為多邊形的頂點。若多邊形的邊之間除了連線頂點外沒有別的公共點,則稱該多邊形為簡單多邊形。一個簡單多邊形將平面分為3個部分:被包圍在多邊形內的所有點構成了多邊形的內部;多邊形本身構成多邊形的邊界;而平面上其餘的點構成了多邊形的外部。當一個簡單多邊形及其內部構成一個閉凸集時,稱該簡單多邊形為凸多邊形。也就是說凸多邊形邊界上或內部的任意兩點所連成的直線段上所有的點均在該凸多邊形的內部或邊界上。
通常,用多邊形頂點的逆時針序列來表示一個凸多邊形,即P=表示具有n條邊v0v1,v1v2,… ,vn-1vn的一個凸多邊形,其中,約定v0=vn 。
若vi與vj是多邊形上不相鄰的兩個頂點,則線段vivj稱為多邊形的一條弦。弦 將多邊形分割成凸的兩個子多邊形和。多邊形的三角剖分是一個將多邊形分割成互不重迭的三角形的弦的集合T。如圖是一個凸多邊形的兩個不同的三角剖分。
凸多邊形最優三角剖分的問題是:給定一個凸多邊形P=以及定義在由多邊形的邊和絃組成的三角形上的權函式ω。要求確定該凸多邊形的一個三角剖分,使得該三角剖分對應的權即剖分中諸三角形上的權之和為最小。
可以定義三角形上各種各樣的權函式W。例如:定義ω(△vivjvk)=|vivj| |vivk| |vkvj|,其中,|vivj|是點vi到vj的歐氏距離。相應於此權函式的最優三角剖分即為最小弦長三角剖分。(注意:解決此問題的演算法必須適用於任意的權函式)

4. 防衛導彈

   一種新型的防衛導彈可截擊多個攻擊導彈。它可以向前飛行,也可以用很快的速度向下飛行,可以毫無損傷地截擊進攻導彈,但不可以向後或向上飛行。但有一個缺點,儘管它發射時可以達到任意高度,但它只能截擊比它上次截擊導彈時所處高度低或者高度相同的導彈。現對這種新型防衛導彈進行測試,在每一次測試中,發射一系列的測試導彈(這些導彈發射的間隔時間固定,飛行速度相同),該防衛導彈所能獲得的資訊包括各進攻導彈的高度,以及它們發射次序。現要求編一程式,求在每次測試中,該防衛導彈最多能截擊的進攻導彈數量,一個導彈能被截擊應滿足下列兩個條件之一:
a)它是該次測試中第一個被防衛導彈截擊的導彈;
b)它是在上一次被截擊導彈的發射後發射,且高度不大於上一次被截擊導彈的高度的導彈。
輸入資料:第一行是一個整數n,以後的n各有一個整數表示導彈的高度。
輸出資料:截擊導彈的最大數目。
分析:定義l[i]為選擇截擊第i個導彈,從這個導彈開始最多能截擊的導彈數目。
由於選擇了第i枚導彈,所以下一個要截擊的導彈j的高度要小於等於它的高度,所以l[i]應該等於從i+1到n的每一個j,滿足h[j]<=h[i]的j中l[j]的最大值。
程式如下:
#include
int main()
{
int i,j,n,max,h[100],l[100];
scanf("%d",&n);
for(i=0;i
scanf("%d",&h[i]);
l[n-1]=1;
for(i=n-2;i>=0;i--)
{
max=0;
for(j=i 1;j
if(h[i]>h[j]&&max
max=l[j];
l[i]=max 1;
}
printf("%d",l[0]);
}

5. 石子合併

在一個圓形操場的四周擺放著n堆石子(n<= 100),現要將石子有次序地合併成一堆。規定每次只能選取相鄰的兩堆合併成新的一堆,並將新的一堆的石子數,記為該次合併的得分。編一程式,由檔案讀入堆疊數n及每堆疊的石子數(<=20)。
選擇一種合併石子的方案,使得做n-1次合併,得分的總和最小;
輸入資料:
第一行為石子堆數n;
第二行為每堆的石子數,每兩個數之間用一個空格分隔。
輸出資料:
從第一至第n行為得分最小的合併方案。第n 1行是空行.從第n 2行到第2n 1行是得分最大合併方案。每種合併方案用n行表示,其中第i行(1<=i<=n)表示第i次合併前各堆的石子數(依順時針次序輸出,哪一堆先輸出均可)。要求將待合併的兩堆石子數以相應的負數表示。
Sample Input
4
4 5 9 4
Sample Output
-4 5 9 -4
-8 -5 9
-13 -9
22 4 -5 -9 4
4 -14 -4
-4 -18
22

6. 最小代價子母樹

設有一排數,共n個,例如:22 14 7 13 26 15 11。任意2個相鄰的數可以進行歸併,歸併的代價為該兩個數的和,經過不斷的歸併,最後歸為一堆,而全部歸併代價的和稱為總代價,給出一種歸併演算法,使總代價為最小。
輸入、輸出資料格式與“石子合併”相同。
Sample Input
4
12 5 16 4
Sample Output
-12 -5 16 4
17 -16 -4
-17 -20
37

7. 商店購物

某商店中每種商品都有一個價格。例如,一朵花的價格是2 ICU(ICU 是資訊學競賽的貨幣的單位);一個花瓶的價格是5 ICU。為了吸引更多的顧客,商店提供了特殊優惠價。特殊優惠商品是把一種或幾種商品分成一組。並降價銷售。例如:3朵花的價格不是6而是5 ICU;2個花瓶加1朵花是10 ICU不是12 ICU。
編一個程式,計算某個顧客所購商品應付的費用。要充分利用優惠價以使顧客付款最小。請注意,你不能變更顧客所購商品的種類及數量,即使增加某些商品會使付款總數減小也不允許你作出任何變更。假定各種商品價格用優惠價如上所述,並且某顧客購買物品為:3朵花和2個花瓶。那麼顧客應付款為14 ICU因為:
1朵花加2個花瓶優惠價:10 ICU
2朵花正常價:4 ICU
輸入資料:第一個檔案INPUT.TXT描述顧客所購物品(放在購物筐中);第二個檔案描述商店提供的優惠商品及價格(檔名為OFF ER.TXT)。 兩個檔案中都只用整數。
第一個檔案INPUT.TXT的格式為:第一行是一個數字B(0≤B≤5),表示所購商品種類數。下面共B行,每行中含3個數C,K,P。 C 代表商品的編碼(每種商品有一個唯一的編碼),1≤C≤999。K代表該種商品購買總數,1≤K≤5。P 是該種商品的正常單價(每件商品的價格),1≤P≤999。請注意,購物筐中最多可放5*5=25件商品。
第二個檔案OFFER.TXT的格式為:第一行是一個數字S(0≤S≤9 9),表示共有S 種優惠。下面共S行,每一行描述一種優惠商品的組合中商品的種類。下面接著是幾個數字對(C,K),其中C代表商品編碼,1≤C≤9 99。K代表該種商品在此組合中的數量,1≤K≤5。本行最後一個數字P(1≤ P≤9999)代表此商品組合的優惠價。當然, 優惠價要低於該組合中商品正常價之總和。
輸出資料:在輸出檔案OUTPUT.TXT中寫 一個數字(佔一行),該數字表示顧客所購商品(輸入檔案指明所購商品)應付的最低貨款。

8. 旅遊預算

一個旅行社需要估算乘汽車從某城市到另一城市的最小費用,沿路有若干加油站,每個加油站收費不一定相同。旅遊預算有如下規則:
若油箱的油過半,不停車加油,除非油箱中的油不可支援到下一站;每次加油時都加滿;在一個加油站加油時,司機要花費2元買東西吃;司機不必為其他意外情況而準備額外的油;汽車開出時在起點加滿油箱;計算精確到分(1元=100分)。編寫程式估計實際行駛在某路線所需的最小費用。
輸入資料:從當前目錄下的文字檔案“route.dat”讀入資料。按以下格式輸入若干旅行路線的情況:
第一行為起點到終點的距離(實數)
第二行為三個實數,後跟一個整數,每兩個資料間用一個空格隔開。其中第一個數為汽車油箱的容量(升),第二個數是每升汽油行駛的公里數,第三個數是在起點加滿油箱的費用,第四個數是加油站的數量。(〈=50)。接下去的每行包括兩個實數,每個資料之間用一個空格分隔,其中第一個數是該加油站離起點的距離,第二個數是該加油站每升汽油的價格(元/升)。加油站按它們與起點的距離升序排列。所有的輸入都有一定有解。
輸出資料:答案輸出到當前目錄下的文字檔案“route.out”中。該檔案包括兩行。第一行為一個實數和一個整數,實數為旅行的最小費用,以元為單位,精確到分,整數表示途中加油的站的N。第二行是N個整數,表示N個加油的站的編號,按升序排列。資料間用一個空格分隔,此外沒有多餘的空格。
Sample Input
516.3 38.09 1
15.7 22.1 20.87 3 2 
125.4 1.259 
297.9 1.129 
345.2 0.999
Sample Output
38.09 1
2

9. 皇宮看守

太平王世子事件後,陸小鳳成了皇上特聘的御前一品侍衛。皇宮以午門為起點,直到後宮嬪妃們的寢宮,呈一棵樹的形狀;某些宮殿間可以互相望見。大內保衛森嚴,三步一崗,五步一哨,每個宮殿都要有人全天候看守,在不同的宮殿安排看守所需的費用不同。可是陸小鳳手上的經費不足,無論如何也沒法在每個宮殿都安置留守侍衛。
請你程式設計計算幫助陸小鳳佈置侍衛,在看守全部宮殿的前提下,使得花費的經費最少。
輸入資料:輸入資料由檔名為intput.txt的文字檔案提供。輸入檔案中資料表示一棵樹,描述如下:
第1行 n,表示樹中結點的數目。
第2行至第n 1行,每行描述每個宮殿結點資訊,依次為:該宮殿結點標號i(0
對於一個n(0 < n <= 1500)個結點的樹,結點標號在1到n之間,且標號不重複。
輸出資料:輸出到output.txt檔案中。輸出檔案僅包含一個數,為所求的最少的經費。
如右圖的輸入資料示例:
Sample Input
6 
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0
Sample Output
25

10. 遊戲室問題

有一個遊戲室裡有多個遊戲室,並且這每個遊戲室裡還有多個遊戲室,每個遊戲室裡面還有遊戲室,依此類推。進入每個遊戲室都可得到一定的快樂,每個遊戲室的門票價格都大於等於0,都有一個快樂值,並且只有進入了一個遊戲室,才可以進入它內部的遊戲室,小明現在有n元錢,問最大能得到多少的快樂。

11. *基因問題

已知兩個基因序列如s:AGTAGT;t:ATTAG。現要你給序列中增加一些空格後,首先使得兩個序列的長度相等,其次兩個串對應符號匹配得到的值最大。基因只有四種分別用A、G、C、T表示,匹配中不允許兩個空格相對應,任意兩符號的匹配值由下表給出:
A G C T ︺
A 5 -2 -1 -2 -4
G -2 5 -4 -3 -2
C -1 -4 5 -5 -1
T -2 -3 -5 5 -2
︺ -4 -2 -1 -2
提示:定義問題l[i][j]為取第一個序列的前i項,和第二個序列的前j項,這兩個序列加空格匹配的最大值。它的最優值與三個子問題有關,l[i-1][j-1]、l[i][j-1]、l[i-1][j]。
建立遞迴公式如下:
其中m[0][t[j]表示表中空格和t[j]匹配的對應值。
思考:本問題的初始化。

12. 田忌賽馬

田忌與齊王賽馬,雙方各有n匹馬參賽(n<=100),每場比賽賭注為1兩黃金,現已知齊王與田忌的每匹馬的速度,並且齊王肯定是按馬的速度從快到慢出場,現要你寫一個程式幫助田忌計算他最好的結果是贏多少兩黃金(輸用負數表示)。
分析:先排序,齊王的馬的速度放在陣列a中,田忌的馬的速度放在陣列b中。本問題應用的演算法是動態規劃和貪心演算法相結合解決的。從兩人的最弱的馬入手:
若田忌的馬快,就讓這兩匹馬比賽;
若田忌的馬慢,乾脆就讓他對付齊王最快的馬;
若兩匹馬的速度相等,這時有兩種選擇方案,或者它倆比賽,或者對付齊王最快的馬。
定義子問題:l(i,j)為齊王的從第i匹馬開始的j匹馬與田忌的最快的j匹馬比賽,田忌所獲得的最大收益。
則: 
程式具體實現時,為了適合c資料從0開始,稍加變動,定義子問題:l(i,j)為齊王的從第i匹馬開始到第i+j匹馬共j 1匹馬與田忌的最快的j 1匹馬比賽,田忌所獲得的最大收益。初始化時:l[i][0]表示齊王的第i匹馬與田忌最快的馬比賽的結果。
程式如下:
#include
void readdata();
void init();
int n,a[100],b[100],l[100][100];
int main()
{
int i,j;
readdata();
init();
for(i=n-2;i>=0;i--)
for(j=1;j
if(a[i j]
l[i][j]=l[i][j-1] 1;
else if(a[i j]>b[j])
l[i][j]=l[i 1][j-1]-1;
else if(l[i 1][j-1]-1>l[i][j-1])
l[i][j]=l[i 1][j-1]-1;
else
l[i][j]=l[i][j-1];
printf("%d",l[0][n-1]);
}
void readdata()
{
int i;
scanf("%d",&n);
for(i=0;i
scanf("%d",&a[i]);
for(i=0;i
scanf("%d",&b[i]);
}
void init()
{
int i;
// qsort(a,n);          //略
for(i=0;i
{
if(a[i]
l[i][0]=1;
else if(a[i]==b[0])
l[i][0]=0;
else
l[i][0]=-1;
}
}

實驗五:貪心演算法和隨機演算法

1. 揹包問題

有一個揹包,揹包容量是M=150。有7個物品,物品可以分割成任意大小。
要求儘可能讓裝入揹包中的物品總價值最大,但不能超過總容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30

2. 照亮的山景

在一片山的上空,高度為T處有N個處於不同位置的燈泡,如圖。如果山的邊界上某一點於某燈i的連線不經過山的其它點,我們稱燈i可以照亮該點。開儘量少的燈,使得整個山景都被照亮。山被表示成有m個轉折點的折線。
提示:照亮整個山景相當於照亮每一個轉折點。

3. 搬桌子問題

某教學大樓一層有n個教室,從左到右依次編號為1、2、…、n。現在要把一些課桌從某些教室搬到另外一些教室,每張桌子都是從編號較小的教室搬到編號較大的教室,每一趟,都是從左到右走,搬完一張課桌後,可以繼續從當前位置或往右走搬另一張桌子。輸入資料:先輸入n、m,然後緊接著m行輸入這m張要搬課桌的起始教室和目標教室。輸出資料:最少需要跑幾趟。
Sample Input
10  5
1  3
3  9
4  6
6  10
7  8
Sample Output
3
分析:貪心演算法,把課桌按起點從小到大排序,每次都是搬離當前位置最近的課桌。
程式如下:
#include
int main()
{
struct
{
int start;
int end;
}a[100];
int i,j;
int n,m,min,num,temp,used[100]={0};
scanf("%d%d",&m,&n);
for(i=0;i
scanf("%d%d",&a[i].start,&a[i].end);
// sort(a,n);         //按start從小到大對陣列a排序
min=0;
num=0;
while(num
{
temp=0;
for(i=0;i
if(used[i]==0&&a[i].start>=temp)
{
temp=a[i].end;
used[i]=1;
num  ;
}
min  ;
}
printf("%d",min);
}

4. 用隨即演算法求解8皇后問題

5. 素數測試

附錄:邏輯推理問題

對於較難的邏輯推理問題,看上去難於解決,不知道該從哪裡下手時,認真的讀題從最簡單最特殊的情況入手

1. 月薪30K的面試題

小明和小強都是張老師的學生,張老師的生日是m月n日,2人都知道張老師的生日是下列10組中的一天,張老師把m值告訴了小明,把n值告訴了小強,張老師問他們知道他的生日是那一天嗎?
3月4日 3月5日 3月8日 
6月4日 6月7日 
9月1日 9月5日 
12月1日 12月2日 12月8日 
小明說:如果我不知道的話,小強肯定也不知道 
小強說:本來我也不知道,但是現在我知道了 
小明說:哦,那我也知道了
提示:做西服有的需要幾分鐘,有的需要幾百道工序。只要認真就能做好。
此題做對的人很少,不是因為題目太難,而是因為不夠認真。

2. 微軟面試題

一個大院子裡住了50戶人家,每家都養了一條狗,有一天他們接到通知說院子裡有狗生病了,並要求所有主人在發現自己家狗生病的當天就要把狗槍殺掉。然而所有主人和他們的狗都不能夠離開自己的房子,主人與主人之間也不能通過任何方式進行溝通,他們能做的只是通過窗戶觀察別人家的狗是否生病從而判斷自己的狗病否。(就是說,每個主人只能看出其他 49家的狗是不是生病,單獨看自己的狗是看不出來的)第一天沒有槍聲,第二天還是沒有槍聲,第三天傳出一陣槍聲,問有多少條狗被槍殺。
提示:上面的大字

3. 海盜分金塊問題

海盜,大家聽說過吧。這是一幫亡命之徒,在海上搶人錢財,奪人性 命,乾的是刀頭上舔血的營生。在我們的印象中,他們一般都瞎一隻 眼,用條黑布或者講究點的用個黑皮眼罩把壞眼遮上。他們還有在地 下埋寶的好習慣,而且總要畫上一張藏寶圖,以方便後人掘取。不過 大家是否知道,他們是世界上最民主的團體。參加海盜的都是桀驁不 馴的漢子,是不願聽人命令的,船上平時一切事都由投票解決。船長 的唯一特權,是有自己的一套餐具--可是在他不用時,其他海盜是 可以借來用的。船上的唯一懲罰,就是被丟到海里去餵魚。
現在船上有若干個海盜,要分搶來的若干枚金幣。自然,這樣的問題 他們是由投票來解決的。投票的規則如下:先由最凶猛的海盜來提出 分配方案,然後大家一人一票表決,如果有50%或以上的海盜同意這個 方案,那麼就以此方案分配,如果少於50%的海盜同意,那麼這個提出 方案的海盜就將被丟到海里去餵魚,然後由剩下的海盜中最凶猛的那 個海盜提出方案,依此類推。
我們先要對海盜們作一些假設。
1)每個海盜的凶猛性都不同,而且所有海盜都知道別人的凶猛性,也就是說,每個海盜都知道自己和別人在這個提出方案的序列中的位置。另外,每個海盜的數學和邏輯都很好,而且很理智。最後,海盜間私底下的交易是不存在的,因為海盜除了自己誰都不相信。
2)一枚金幣是不能被分割的,不可以你半枚我半枚。
3)每個海盜當然不願意自己被丟到海里去餵魚,這是最重要的。
4)每個海盜當然希望自己能得到儘可能多的金幣。
5)每個海盜都是現實主義者,如果在一個方案中他得到了1枚金幣,而下一個方案中,他有兩種可能,一種得到許多金幣,一種得不到金幣,他會同意目前這個方案,而不會有僥倖心理。總而言之,他們相信二 鳥在林,不如一鳥在手。
6)最後,每個海盜都很喜歡其他海盜被丟到海里去餵魚。在不損害自己利益的前提下,他會儘可能投票讓自己的同伴餵魚。
現在,如果有10個海盜要分100枚金幣,將會怎樣?
提示:同上

4. 囚犯放風問題

有100個無期徒刑囚徒,被關在100個獨立的小房間,互相無法通訊。每天會有一個囚徒被隨機地抽出來放風,隨機就是說可能被抽到多次,也可能一次抽不到。
放風的地方有一盞燈,囚徒可以開啟或者關上,除囚徒外,沒有別人會去動這個燈。每個人除非出來放風,是看不到這個燈的。一天,全體囚徒大會,國王大赦,給大家一個機會:
如果某一天,某個囚徒能夠明確表示,所有的囚徒都已經被放過風了,而且的確如此,那麼所有囚徒釋放;如果仍有囚徒未被放過風,那麼所有的囚徒一起處死!囚徒大會後給大家20分鐘時間討論,囚徒們能找到方法麼?除了那個燈以外,囚徒們不能以其他方式聯絡 
提示:說過了

5. 天盟筆試的最後一道題目

一段文章,中有逗號若干,現求一演算法,搜尋某一逗號位置。要求:
1、只搜尋文章一遍
2、搜尋過程中只能儲存一個逗號的位置
3、對於每個逗號,被搜尋到的機率是相等的
提示:書讀百遍其意自見

6.

現有100個黑球和100個白球,每次從中任意取出兩個球,若顏色相同,則給這堆球中放入一個黑球,若顏色不同,則給這堆球中放入一個白球,這樣當這堆球中只剩下一個球時這個球是什麼顏色,請證明你的結論。
提示:多讀仔細分析就能抓住關鍵。

7.

下面用數學歸納法證明“所有的馬的顏色都相同”的證明是否正確,如不正確指出錯誤的原因。
(1)基礎:當n=1時顯然正確。
(2)歸納:假設n=k時命題成立,當n=k 1時,從中間取出一匹馬,這是隻有k匹馬,根據假設,這k匹馬的顏色是相同的,再從中取出一匹馬,把剛才這匹馬放回,這是又是k匹馬,根據假設,這k匹馬的顏色是相同的,所以這k 1匹馬的顏色是相同的。
由以上兩步可知,所有的馬的顏色都是相同的。
提示:不需要什麼,除了知識。

8.

 現在小明一家過一座橋,過橋時候是黑夜,所以必須有燈。現在小明過橋要1秒,小明的弟弟要3秒,小明的爸爸要6秒,小明的媽媽要8秒,小明的爺爺要12秒。每次此橋最多可過兩人,而過橋的速度依過橋最慢者而定,而且燈在點燃後30秒就會熄滅。問小明一家如何過橋?(再加一點,如果是5個人,6個人呢?)

9.

小明早晨6:00從山腳下開始爬山,中午12:00到達山頂;第二天早晨6:00從山頂開始下山,中午12:00到達山腳下。上山的路只有一條沒有任何岔路,你能否證明:小明在同一個時間經過了同一個點。

10

一男孩和一女孩分別在離家2千米和1千米且方向相反的兩所學校上學每天同時以4千米/時和2千米/時的速度步行上學一小狗以6千米/時的速度從男孩奔向女孩又從女孩處奔向男孩,如此往返當兩人到達學校時小狗在何處?
然後一步一步分析

ACM競賽須掌握的知識

圖論

    拓撲排序 
有向無環圖與動態規劃的關係
二分圖匹配問題 
一般圖問題與二分圖問題的轉換思路 
最大匹配 
有向圖的最小路徑覆蓋 
0 / 1矩陣的最小覆蓋 
完備匹配 
最優匹配 
穩定婚姻
網路流問題 
網路流模型的簡單特徵和與線性規劃的關係 
最大流最小割定理 
最大流問題 
有上下界的最大流問題 
迴圈流 
最小費用最大流 / 最大費用最大流
弦圖的性質和判定

組合數學

   解決組合數學問題時常用的思想 
逼近 
遞推 / 動態規劃 
概率問題 
Polya定理

計算幾何 / 解析幾何

   計算幾何的核心:叉積 / 面積 
解析幾何的主力:複數
基本形 
點 
直線,線段 
多邊形
凸多邊形 / 凸包 
凸包演算法的引進,捲包裹法
Graham掃描法 
水平序的引進,共線凸包的補丁
完美凸包演算法
相關判定 
兩直線相交 
兩線段相交 
點在任意多邊形內的判定 
點在凸多邊形內的判定
經典問題 
最小外接圓 
近似O(n)的最小外接圓演算法 
點集直徑 
旋轉卡殼,對踵點 
多邊形的三角剖分

數學 / 數論

   最大公約數 
Euclid演算法 
擴充套件的Euclid演算法 
同餘方程 / 二元一次不定方程 
同餘方程組
線性方程組 
高斯消元法 
解mod 2域上的線性方程組 
整係數方程組的精確解法
矩陣 
行列式的計算 
利用矩陣乘法快速計算遞推關係
分數 
分數樹 
連分數逼近
數論計算 
求N的約數個數 
求phi(N) 
求約數和 
快速數論變換 
……
素數問題 
概率判素演算法 
概率因子分解

資料結構

   組織結構 
二叉堆 
左偏樹 
二項樹 
勝者樹 
跳躍表 
樣式圖示 
斜堆 
reap
統計結構 
樹狀陣列 
虛二叉樹 
線段樹 
矩形面積並 
圓形面積並
關係結構 
Hash表 
並查集 
路徑壓縮思想的應用
STL中的資料結構 
vector 
deque 
set / map

動態規劃 / 記憶化搜尋

       動態規劃和記憶化搜尋在思考方式上的區別
最長子序列系列問題 
最長不下降子序列 
最長公共子序列
一類NP問題的動態規劃解法
樹型動態規劃
揹包問題
動態規劃的優化 
四邊形不等式 
函式的凸凹性 
狀態設計 
規劃方向
線性規劃

常用思想

   二分 
最小表示法
串 
KMP 
Trie結構 
字尾樹/字尾陣列 
LCA/RMQ 
有限狀態自動機理論
排序 
選擇/冒泡 
快速排序 
堆排序 
歸併排序 
基數排序 
拓撲排序 
排序網路
題目均為POJ上的
http://acm.pku.edu.cn

個別題目的分類並不準確


OJ上的一些水題(可用來練手和增加自信) 
(poj3299,poj2159,poj2739
,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)

初期:

一.基本演算法:

    (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[i] 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)

下面是另一版本POJ推薦,基本都比較難,很多題目與黑書配套

推薦一些題目,希望對參與ICPC競賽的同學有所幫助。
POJ上一些題目在
http://162.105.81.202/course/problemSolving/ 
可以找到解題報告。
《演算法藝術與資訊學競賽》的習題提示在網上可搜到

一.動態規劃

參考資料:
劉汝佳《演算法藝術與資訊學競賽》
《演算法導論》
推薦題目:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1141 
簡單
http://acm.pku.edu.cn/JudgeOnline/problem?id=2288 
中等,經典TSP問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2411 
中等,狀態壓縮DP
http://acm.pku.edu.cn/JudgeOnline/problem?id=1112 
中等
http://acm.pku.edu.cn/JudgeOnline/problem?id=1848 
中等,樹形DP。
可參考《演算法藝術與資訊學競賽》動態規劃一節的樹狀模型
http://acm.zju.edu.cn/show_problem.php?pid=1234 
中等,《演算法藝術與資訊學競賽》中的習題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1947 
中等,《演算法藝術與資訊學競賽》中的習題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1946 
中等,《演算法藝術與資訊學競賽》中的習題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1737 
中等,遞推
http://acm.pku.edu.cn/JudgeOnline/problem?id=1821 
中等,需要減少冗餘計算
http://acm.zju.edu.cn/show_problem.php?pid=2561 
中等,四邊形不等式的簡單應用
http://acm.pku.edu.cn/JudgeOnline/problem?id=1038 
較難,狀態壓縮DP,《演算法藝術與資訊學競賽》中有解答
http://acm.pku.edu.cn/JudgeOnline/problem?id=1390 
較難,《演算法藝術與資訊學競賽》中有解答
http://acm.pku.edu.cn/JudgeOnline/problem?id=3017 
較難,需要配合資料結構優化(我的題目^_^)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1682 
較難,寫起來比較麻煩
http://acm.pku.edu.cn/JudgeOnline/problem?id=2047 
較難
http://acm.pku.edu.cn/JudgeOnline/problem?id=2152 
難,樹形DP
http://acm.pku.edu.cn/JudgeOnline/problem?id=3028 
難,狀態壓縮DP,題目很有意思
http://acm.pku.edu.cn/JudgeOnline/problem?id=3124 
難
http://acm.pku.edu.cn/JudgeOnline/problem?id=2915 
非常難

二.搜尋

參考資料:
劉汝佳《演算法藝術與資訊學競賽》
推薦題目:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1011 
簡單,深搜入門題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1324 
中等,廣搜
http://acm.pku.edu.cn/JudgeOnline/problem?id=2044 
中等,廣搜
http://acm.pku.edu.cn/JudgeOnline/problem?id=2286 
較難,廣搜
http://acm.pku.edu.cn/JudgeOnline/problem?id=1945 
難,IDA*,迭代加深搜尋,需要較好的啟發函式
http://acm.pku.edu.cn/JudgeOnline/problem?id=2449 
難,可重複K最短路,A*。
可參考解題報告:
http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144 
http://acm.pku.edu.cn/JudgeOnline/problem?id=1190 
難,深搜剪枝,《演算法藝術與資訊學競賽》中有解答
http://acm.pku.edu.cn/JudgeOnline/problem?id=1084 
難,《演算法藝術與資訊學競賽》習題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2989 
難,深搜
http://acm.pku.edu.cn/JudgeOnline/problem?id=1167 
較難,《演算法藝術與資訊學競賽》中有解答
http://acm.pku.edu.cn/JudgeOnline/problem?id=1069 
很難

三. 常用資料結構

參考資料:
劉汝佳《演算法藝術與資訊學競賽》
《演算法導論》
線段樹資料:
http://home.ustc.edu.cn/~zhuhcheng/ACM/segment_tree.pdf 
樹狀陣列資料
http://home.ustc.edu.cn/~zhuhcheng/ACM/tree.ppt 
關於線段樹和樹狀陣列更多相關內容可在網上搜到
字尾陣列資料
http://home.ustc.edu.cn/~zhuhcheng/ACM/suffix_array.pdf 
http://home.ustc.edu.cn/~zhuhcheng/ACM/linear_suffix.pdf 
推薦題目
http://acm.pku.edu.cn/JudgeOnline/problem?id=2482 
較難,線段樹應用,《演算法藝術與資訊學競賽》中有解答
http://acm.pku.edu.cn/JudgeOnline/problem?id=1151 
簡單,線段樹應用矩形面積並,《演算法藝術與資訊學競賽》中有解答
http://acm.pku.edu.cn/JudgeOnline/problem?id=3225 
較難,線段樹應用,可參考解題報告
http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1233 
http://acm.pku.edu.cn/JudgeOnline/problem?id=2155 
難,二維樹狀陣列。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2777 
中等,線段樹應用。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2274 
難,堆的應用,《演算法藝術與資訊學競賽》中有解答
http://acm.zju.edu.cn/show_problem.php?pid=2334 
中等,左偏樹,二項式堆或其他可合併堆的應用。
左偏樹參考http://www.nist.gov/dads/HTML/leftisttree.html 
二項式堆參見《演算法導論》相關章節
http://acm.pku.edu.cn/JudgeOnline/problem?id=1182 
中等,並查集
http://acm.pku.edu.cn/JudgeOnline/problem?id=1816 
中等,字典樹
http://acm.pku.edu.cn/JudgeOnline/problem?id=2778 
較難,多串匹配樹
參考:http://home.ustc.edu.cn/~zhuhcheng/ACM/zzy2004.pdf 
http://acm.pku.edu.cn/JudgeOnline/problem?id=1743 
難,字尾陣列
http://acm.pku.edu.cn/JudgeOnline/problem?id=2774 
較難,最長公共子串,經典問題,字尾陣列
http://acm.pku.edu.cn/JudgeOnline/problem?id=2758 
很難,字尾陣列
可參考解題報告
http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1178 
http://acm.pku.edu.cn/JudgeOnline/problem?id=2448 
很難,資料結構綜合運用

四.圖論基礎

參考資料:
劉汝佳《演算法藝術與資訊學競賽》
《演算法導論》
《網路演算法與複雜性理論》謝政
推薦題目: 
http://acm.pku.edu.cn/JudgeOnline/problem?id=2337 
簡單,尤拉路
http://acm.pku.edu.cn/JudgeOnline/problem?id=3177 
中等,無向圖割邊
http://acm.pku.edu.cn/JudgeOnline/problem?id=2942 
較難,無向圖雙連通分支
http://acm.pku.edu.cn/JudgeOnline/problem?id=1639 
中等,最小度限制生成樹,《演算法藝術與資訊學競賽》中有解答
http://acm.pku.edu.cn/JudgeOnline/problem?id=2728 
中等,最小比率生成樹,《演算法藝術與資訊學競賽》中有解答
http://acm.pku.edu.cn/JudgeOnline/problem?id=3013 
簡單,最短路問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1275 
中等,差分約束系統,Bellman-Ford求解,《演算法藝術與資訊學競賽》中有解答
http://acm.pku.edu.cn/JudgeOnline/problem?id=1252 
簡單,Bellman-Ford
http://acm.pku.edu.cn/JudgeOnline/problem?id=1459 
中等,網路流
http://acm.pku.edu.cn/JudgeOnline/problem?id=2391 
較難,網路流
http://acm.pku.edu.cn/JudgeOnline/problem?id=1325 
中等,二部圖最大匹配
http://acm.pku.edu.cn/JudgeOnline/problem?id=2226 
較難,二部圖最大匹配
http://acm.pku.edu.cn/JudgeOnline/problem?id=2195 
中等,二部圖最大權匹配
KM演算法參考《網路演算法與複雜性理論》
http://acm.pku.edu.cn/JudgeOnline/problem?id=2516 
較難,二部圖最大權匹配
http://acm.pku.edu.cn/JudgeOnline/problem?id=1986 
中等,LCA(最近公共祖先)問題
參考Tarjan's LCA algorithm 《演算法導論》第21章習題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2723 
較難,2-SAT問題
參考:http://home.ustc.edu.cn/~zhuhcheng/ACM/2-SAT.PPT 
http://acm.pku.edu.cn/JudgeOnline/problem?id=2749 
較難,2-SAT問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=3164 
較難,最小樹形圖
參考《網路演算法與複雜性理論》中朱-劉演算法
五.數論及組合計數基礎
http://acm.pku.edu.cn/JudgeOnline/problem?id=1811 
簡單,素數判定,大數分解
參考演算法導論相關章節
http://acm.pku.edu.cn/JudgeOnline/problem?id=2888 
較難,Burnside引理
http://acm.pku.edu.cn/JudgeOnline/problem?id=2891 
中等,解模方程組
http://acm.pku.edu.cn/JudgeOnline/problem?id=2154 
中等,經典問題,波利亞定理
http://cs.scu.edu.cn/soj/problem.action?id=2703 
難,極好的題目,Burnside引理 模線性方程組
http://acm.pku.edu.cn/JudgeOnline/problem?id=2764 
較難,需要數學方法,該方法在《具體數學》第七章有講
http://acm.pku.edu.cn/JudgeOnline/problem?id=1977 
簡單,矩陣快速乘法
/*