2015省信息學(xué)奧賽培訓(xùn)在teacher上-競賽指導(dǎo)

成功

+睿智的思想

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

/codejam程序設(shè)計(jì)大賽http/htt/nanti/報(bào)名時(shí)間：3月29日至5月23日http:

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

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

needed

in

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

/usacogate(USACO)基本功訓(xùn)練基本算法講解、訓(xùn)練每個(gè)題做出后有講解、代碼闖關(guān)模式初學(xué)者

Chapter1-4,Chapter5-6

性較強(qiáng)http:

/tcAlgorithm

Competition

-

Single

Round

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

I,

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

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

RatingHandle

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

http

http

自己的OJ杭州電子科技大學(xué)http:

/vjudge華

大虛擬OJhttp

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

Online

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

ErrorRuntime

ErrorTime

Limit

ExceededWrong

AnswerPresentation

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

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

return

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

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

33

1

17

2

4

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

j)=a[i,

j]

+

min{f(i+1,

j)，f(i+1,

j

+

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

父親結(jié)點(diǎn)

兒子結(jié)點(diǎn)

兄弟結(jié)點(diǎn)

祖先結(jié)點(diǎn)

結(jié)點(diǎn)的層次樹的高度ADCBFEGJIHLKM堆父親節(jié)點(diǎn)權(quán)值小于兒子節(jié)點(diǎn)堆除了最底層，為滿二叉樹完全二叉樹有兩個(gè)兒子節(jié)點(diǎn)二叉樹節(jié)點(diǎn)和邊樹同余模堆的應(yīng)用堆排序：將N個(gè)數(shù)一次插入堆中，然后做N次刪除堆頂元素操作，就可以獲得順序的排列。時(shí)間復(fù)雜度：O(n*log(n))樹二叉樹線段樹伸展樹AVL樹樹并查字典樹生成樹122多叉樹250300110200991052302161、數(shù)論2、組合數(shù)學(xué)3、圖論數(shù)學(xué)和常用模型1.素?cái)?shù)與整除問題2.進(jìn)制位3.同余模運(yùn)算數(shù)論秦九韶算法：二進(jìn)制數(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……偽素?cái)?shù)費(fèi)馬小定理隨機(jī)判斷a^(p-1) mod

p=1Miller-Rabbin測試素?cái)?shù)的判定圖的定義1、點(diǎn)V2、邊3、邊權(quán)E=(u,v,w)圖論1E=(u,v

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

有價(jià)值的概念！

面積，左手系是為

積叉積的幾何形式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);}//叉積，計(jì)算(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是否相交，不包括端點(diǎn)用叉積判斷線段是否相交精度問題epsdouble

eps=1e-8；int

dblcmp(double

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

return

0;return

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

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

編程比賽和訓(xùn)練賽，練習(xí)寫代碼的準(zhǔn)確性和速度，積累比賽經(jīng)驗(yàn)。（比賽預(yù)報(bào)：http:/

/

/re

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

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

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

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

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

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

OJ的

資源共享