2015省信息學奧賽培訓在teacher上-競賽指導

成功

+睿智的思想

+不懈的努力為什么要參加編程比賽，能力的提高學到很多書本上和大學里面學不到的知識和技能有機會云游四海，可以和眾多武林高手同場交到很多志同道合的朋友$$,出國的機會對未來極其有利保研大公司不僅關注、同時自己舉辦各類編程競賽、非常重視選手的編程比賽經(jīng)歷和成績編程競賽非常有趣！各種有趣的編程比賽報名時間：4月7日至5月8日http

/codejam程序設計大賽http/htt/nanti/報名時間：3月29日至5月23日http:

/tchtt/nanti/樓教主千秋萬載，一統(tǒng)江湖樓教主君臨斯德哥爾摩ACM

經(jīng)典ACRush:切題就是升級,比賽就是PKPetrMitrichev兩次ACM世界總決賽亞軍TCOChampionTCCCChampionGCJChampion有朝一日，我可能像這些人一樣牛嗎？初學者如何進行What’s

needed

in

Contest精通算法穩(wěn)定快速實現(xiàn)算法的能力數(shù)學水平心理素質(zhì)兩個ht

/usacogate(USACO)基本功訓練基本算法講解、訓練每個題做出后有講解、代碼闖關模式初學者

Chapter1-4,Chapter5-6

性較強http:

/tcAlgorithm

Competition

-

Single

Round

Match(SRM)一個月3次左右，有rating分兩個版(Div

I,

DivII)參加人數(shù)眾多每次比賽后有詳細的解題報告、代碼比賽結束后有Practice

Room可以繼續(xù)做可以查看每一個人的代碼Forum很熱鬧，外國人非常有時候有$哦TopcoderTopcoderTopcoderTopcoderTopcoderTopcoder

RatingHandle

:exod40國內(nèi)題庫http:/

http

http

自己的OJ杭州電子科技大學http:

/vjudge華

大虛擬OJhttp

浙江大學國外題庫數(shù)學題較多，OI選手必做國外最大題庫，人很多，F(xiàn)orum也很熱鬧題較難PKU

Online

Judge可能收到的反饋信息包括：Compile

ErrorRuntime

ErrorTime

Limit

ExceededWrong

AnswerPresentation

ErrorAccepted搜索貪心遞歸分治動態(tài)規(guī)劃程序=算法+數(shù)據(jù)結構計博弈一：有若干個

，兩人輪流取，可以取一或二或三個輾，轉(zhuǎn)取相得除最法后一個的人失敗If(a==0)retuElse

return

g二：有若干堆，每堆若干漢個諾，塔兩問人題輪流取，可以從任m意ov一e(堆t1,中t2取,t3任,n)意{多個（至少一個）m，ov取e(得t1,最t3后,t2一,n-1)個的人失敗print(“Move

t1->t2”)move(t3,t1,t2.n-1)}化搜索一道經(jīng)典例題給你一個數(shù)字三角形,形式如下:12

33

1

17

2

4

1找出從底層到頂層的一條路,使得所經(jīng)過的權值之和最小算法：f(i,

j)=a[i,

j]

+

min{f(i+1,

j)，f(i+1,

j

+

1)}時間復雜度：N*N動態(tài)規(guī)劃串、棧、隊列樹堆并查集哈希表程序=算法+數(shù)據(jù)結構樹的術語：根結點葉子結點結點的度

父親結點

兒子結點

兄弟結點

祖先結點

結點的層次樹的高度ADCBFEGJIHLKM堆父親節(jié)點權值小于兒子節(jié)點堆除了最底層，為滿二叉樹完全二叉樹有兩個兒子節(jié)點二叉樹節(jié)點和邊樹同余模堆的應用堆排序：將N個數(shù)一次插入堆中，然后做N次刪除堆頂元素操作，就可以獲得順序的排列。時間復雜度：O(n*log(n))樹二叉樹線段樹伸展樹AVL樹樹并查字典樹生成樹122多叉樹250300110200991052302161、數(shù)論2、組合數(shù)學3、圖論數(shù)學和常用模型1.素數(shù)與整除問題2.進制位3.同余模運算數(shù)論秦九韶算法：二進制數(shù)(10110)=1*16+1*4+1*2=((((1*2)*2)+1)*2+1)*2中國剩余定理：已知X

mod

M[i]=A[i]，求X篩法2，3，4，5，6，7，8，9，10……2，3，5，7，9，11，13，15……2，3，5，7，11，13，17，19……偽素數(shù)費馬小定理隨機判斷a^(p-1) mod

p=1Miller-Rabbin測試素數(shù)的判定圖的定義1、點V2、邊3、邊權E=(u,v,w)圖論1E=(u,v

2435661655563421.圖的遍歷（連通性）2.生成樹問題4.網(wǎng)絡流問題5.匹配問題圖論最大流費用流最小割最大二分圖匹配最小生成樹最小度限制生成樹最優(yōu)比例生成樹3.最短路問題深度優(yōu)先遍歷強連通塊橋、割點廣度優(yōu)先遍歷帶權匹配最小路徑覆蓋1、Bellman-Ford2、Dijkstra3、Floyd最短路算法計算幾何一個簡單的問題判斷兩條線段是否相交（不包含端點）？程，求出交點，判斷交解析幾何寫出兩條點的位交點的情點，唯一交點求出交點是不是太多余？只是判斷線段各種浮點計算誤差需要更簡單的做法——計算幾何！！一個簡單的問題AB和CD相交，那么線的異側，問題的轉(zhuǎn)化如何判斷點在直線的哪C、D也位于AB所在一側？一個簡單的問題有向線段規(guī)定直線具有一個正方向，直線將平面劃分成兩個區(qū)域：直線的左側和右側叉積現(xiàn)在的問題：是否存在一種運算，能判斷向量a位于向量b的哪一側？第一象限的情況：通過斜率來比較Yb/Xb-Ya/Xa>0?無法推廣，除法代價高、誤差大對其通分，得到：Xa*Yb-Xb*Ya經(jīng)過實踐檢驗，當a，b成右手系時，上式的結果總為正；當a，b成左手系時，上式的結果總為負；當a，b共線時，上式結果總為零。叉積叉 的面積兩個向量的叉積：a×b=Xa*Yb-Xb*Ya有向面積力學中的四邊形法則有向面積一個很當o

有價值的概念！

面積，左手系是為

積叉積的幾何形式a×b=|a|*|b|*sinθ用叉積判斷線段是否相交struct

Point{double

x,y;};double

xmult(Point

p1,Point

p2,Point

p0){return

(p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);}//叉積，計算(p1-p0)×(p2-p0)bool

cross(Point

a,Point

b,Point

c,Point

d){return

xmult(a,b,c)*xmult(a,b,d)<0&&xmult(c,d,a)*xmult(c,d,b)<0}//判斷線段ab和cd是否相交，不包括端點用叉積判斷線段是否相交精度問題epsdouble

eps=1e-8；int

dblcmp(double

x){if(fabs(x)<eps)

return

0;return

x>0?1:-1;}從今天開始練習poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094簡單題用來練手熟悉OJ從今天開始練習基本算法:(1)枚舉.(poj1753,poj2965)(2)貪心(poj1328,poj2109,poj2586)(3)遞歸和分治法.(4)遞推.(5)構造法.(poj3295)從今天開始練習圖算法:(1)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷.(2)最短路徑算法poj1860,poj3259,poj1062,poj2253,poj1125,poj2240(3)最小生成樹算法poj1789,poj2485,poj1258,poj3026(4)拓撲排序poj1094從今天開始練習數(shù)據(jù)結構(1)串(poj1035,poj3080,poj1936)(2)排序(poj2388,poj2299)(3)簡單并查集的應用.(4)哈夫曼樹(poj3253)(5)堆從今天開始練習簡單搜索(1)深度優(yōu)先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)(2)廣度優(yōu)先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)從今天開始練習數(shù)學(1)組合數(shù)學:1.加法原理和乘法原理.2.排列組合.3.遞推關系.(POJ3252,poj1850,poj1019,poj1942)從今天開始練習數(shù)學(2)數(shù)論.1.素數(shù)與整除問題2.進制位.3.同余模運算.

(poj2635,poj3292,poj1845,poj2115)建議初學時做一定量的題目打基礎針對特定的經(jīng)典算法，做相應的題目練習參加各種

編程比賽和訓練賽，練習寫代碼的準確性和速度，積累比賽經(jīng)驗。（比賽預報：http:/

/

/re

hp?tid=125）過題數(shù)并不重要，做題數(shù)的

也不重要。參考書算法導論英文版入門級讀物初讀時，前面的數(shù)學部分建立基本概念即可，無需深究算法的正確性證明、復雜度分析一定要扎實掌握(Master

Theorem要會用，攤還分析了解)數(shù)據(jù)結構部分理解是關鍵，一些過于復雜的數(shù)據(jù)結構對于初學者并不一定要求實現(xiàn)(

樹、二項堆、Fibbonacci堆），但基本的數(shù)據(jù)結構一定要熟練掌握，要能熟練實現(xiàn)圖論經(jīng)典算法要熟練掌握動態(tài)規(guī)劃要熟練掌握高級部分只用選學一些參考書算法競賽入門經(jīng)典程序設計導引及劉汝佳實踐

POJ首頁書籍很基礎，適合入門的同學算法藝術與信息學競賽（黑書）較難適合有一定基礎的同學對于初學者仍然

第一章和第三章劉汝佳、黃亮武功秘籍武功秘籍各種的資料很多非常好的一、

OJ的

資源共享