備戰(zhàn)ACM資料
一：知識點
? ? 數(shù)據(jù)結(jié)構(gòu)：
? ? ? 1，單，雙鏈表及循環(huán)鏈表
? ? ? 2，樹的表示與存儲，二叉樹（概念，遍歷）二叉樹的 ? ? ? ? ?
? ? ? ? ?應用（二叉排序樹，判定樹，博弈樹，解答樹等）
? ? ? 3，文件操作（從文本文件中讀入數(shù)據(jù)并輸出到文本文 ? ? ??
? ? ? ? ?件中）
? ? ? 4，圖（基本概念，存儲結(jié)構(gòu)，圖的運算）
? ?數(shù)學知識
? ? ?1，離散數(shù)學知識的應用（如排列組合、簡單的圖論，數(shù)
? ? ? ? 理邏輯）
? ? ?2，數(shù)論知識
? ? ?3，線性代數(shù)
? ? ?4，組合代數(shù)
? ? ?5，計算幾何
二 算法
? ? ? 1，排序算法（冒拋法，插入排序，合并排序，快速排 ??
? ? ? ? ?序，堆排序）
? ? ? 2，查找（順序查找，二分發(fā)）
? ? ? 3，回溯算法
? ? ? 4，遞歸算法
? ? ? 5，分治算法
? ? ? 6，模擬法
? ? ? 7，貪心法
? ? ? 8，簡單搜索算法（深度優(yōu)先，廣度優(yōu)先），搜索中的
? ? ? ? ?剪枝，A*算法
? ? ? 9，動態(tài)規(guī)劃的思想及基本算法
? ? ? 10，高精度運算 ? ?
三、ACM競賽的題型分析
? ? ? ? ? 競賽的程序設(shè)計一般只有16種類型，它們分別是：
? ? ? Dynamic Programming （動態(tài)規(guī)劃）?
? ? ? Greedy （貪心算法）?
? ? ? Complete Search （窮舉搜索）?
? ? ? Flood Fill （不知該如何翻譯）?
? ? ? Shortest Path （最短路徑）?
? ? ? Recursive Search Techniques （回溯搜索技術(shù)）?
? ? ? Minimum Spanning Tree （最小生成樹）?
? ? ? Knapsack （背包問題）?
? ? ? Computational Geometry (計算幾何學)?
? ? ? Network Flow （網(wǎng)絡流）?
? ? ? Eulerian Path （歐拉回路）?
? ? ? Two-Dimensional Convex Hull （不知如何翻譯）?
? ? ? BigNums （大數(shù)問題）?
? ? ? Heuristic Search （啟發(fā)式搜索）?
? ? ? Approximate Search （近似搜索）?
? ? ? Ad Hoc Problems （雜題）?
四 ?ACM競賽參考書?
? 《實用算法的分析與程序設(shè)計》 ?（吳文虎，王建德著，電子工業(yè)出版社，競賽類的黑寶書）
? 《青少年國際和全國信息學（計算機）奧林匹克競賽指導）――組合數(shù)學的算法
? ? ? 和程序設(shè)計》（吳文虎，王建德著，清華大學出版社，參加競賽組合數(shù)學必學）
? 《計算機算法設(shè)計與分析》 ? ? ?（王曉東編著，最好的數(shù)據(jù)結(jié)構(gòu)教材）
? 《數(shù)據(jù)結(jié)構(gòu)與算法》 ? ? ? ? ? （傅清祥，王曉東編著，我所見過的最好的算法教材）
? 《信息學奧林匹克競賽指導――1997-1998競賽試題解析》（吳文虎，王建德著，清華大學出版社）
? 《計算機程序設(shè)計技巧》 ? ?D.E.Kruth著，算法書中最著名的《葵花寶典》，大師的作品，難度大）
? 《計算幾何》周陪德著
? 《ACM國際大學生程序設(shè)計競賽試題與解析（一）》 ?（吳文虎著，清華大學出版社）
? ?《數(shù)學建模競賽培訓教材》 ? ? ? ? 共三本 葉其孝主編
? ?《數(shù)學模型》 ? ? ? ? ? ? ? ? ? ?第二版 姜啟源
? ?《隨機規(guī)劃》?
? ?《模糊數(shù)學》?
? ?《數(shù)學建模入門》 ? ? ? ? ? ? ? ?徐全智
? ?《計算機算法設(shè)計與分析》 ? ? ? 國防科大 ? ? ??
五 常見的幾個網(wǎng)上題庫
? ?常用網(wǎng)站：
? ? 1）信息學初學者之家：http://oibh.ioiforum.org/
? ?（2）大榕樹編程世界：http://www.fjsdfz.org/~drs/program/default.asp
? ?（3）中國教育曙光網(wǎng)：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）美國信息學奧林匹克競賽官方網(wǎng)站：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?
五 如何備戰(zhàn)ACM/ICPC
? ? 1，個人準備（算法書，習題集，網(wǎng)上做題和討論）
? ? 2，1000題=亞洲冠軍=世界決賽
? ? 3，做好資料收集和整理工作
?
實驗一：遞歸與分治
1. 二分查找
2. 合并排序
3. 快速排序
實驗二：回溯
1. 0-1背包問題
2. 裝載問題
3. 堡壘問題（ZOJ1002）
4. *翻硬幣問題
5. 8皇后問題
6. 素數(shù)環(huán)問題
7. 迷宮問題
8. *農(nóng)場灌溉問題（ZOJ2412）
9. *求圖像的周長（ZOJ1047）
10. *骨牌矩陣
11. *字母轉(zhuǎn)換（ZOJ1003）
12. *踩氣球（ZOJ1004）
實驗三：搜索
1. Floodfill
2. 電子老鼠闖迷宮
3. 跳馬
4. 獨輪車
5. 皇宮小偷
6. 分酒問題
7. *找倍數(shù)
8. *8數(shù)碼難題
實驗四：動態(tài)規(guī)劃
1. 最長公共子序列
2. 計算矩陣連乘積
3. 凸多邊形的最優(yōu)三角剖分
4. 防衛(wèi)導彈
5. *石子合并
6. *最小代價子母樹
7. *旅游預算
8. *皇宮看守
9. *游戲室問題
10. *基因問題
11. *田忌賽馬
實驗五：貪心與隨機算法
1. 背包問題
2. 搬桌子問題
3. *照亮的山景
4. *用隨即算法求解8皇后問題
5. 素數(shù)測試
實驗一：遞歸與分治
實驗目的
理解遞歸算法的思想和遞歸程序的執(zhí)行過程，并能熟練編寫遞歸程序。
掌握分治算法的思想，對給定的問題能設(shè)計出分治算法予以解決。
實驗預習內(nèi)容
編程實現(xiàn)講過的例題：二分搜索、合并排序、快速排序。
對本實驗中的問題，設(shè)計出算法并編程實現(xiàn)。
試驗內(nèi)容和步驟
1． 二分查找
在對線性表的操作中，經(jīng)常需要查找某一個元素在線性表中的位置。此問題的輸入是待查元素x和線性表L，輸出為x在L中的位置或者x不在L中的信息。
程序略
2． 合并排序
程序略
3． 快速排序
程序略
實驗總結(jié)及思考
合并排序的遞歸程序執(zhí)行的過程
?
實驗二：回溯算法
實驗目的：熟練掌握回溯算法
實驗內(nèi)容：回溯算法的幾種形式
a) 用回溯算法搜索子集樹的一般模式
void search(int m)
{
if(m>n) ? ? ? ? ? //遞歸結(jié)束條件?
output(); ? ? ?//相應的處理(輸出結(jié)果)
else
{
a[m]=0; ? ? ? //設(shè)置狀態(tài)：0表示不要該物品
search(m+1); ? //遞歸搜索：繼續(xù)確定下一個物品
a[m]=1; ? ? ? //設(shè)置狀態(tài)：1表示要該物品
search(m+1); ? //遞歸搜索：繼續(xù)確定下一個物品
}
}
b) 用回溯算法搜索子集樹的一般模式
void search(int m)
{
if(m>n) ? ? ? ? ? ? ? //遞歸結(jié)束條件?
output(); ? ? ? ? ?//相應的處理(輸出結(jié)果)
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