河南省歷年省賽題目

河南省歷年省賽題目分析2014年上學(xué)年算法講座南陽理工學(xué)院

ACM集訓(xùn)隊(duì)南陽理工學(xué)院2014_鐘詩俊引言省賽是一次給自己定位的絕佳機(jī)會(huì)算法雖千變?nèi)f化但萬變不離其宗省賽題目相對(duì)以考察基礎(chǔ)算法為主各屆省賽亮點(diǎn)不同但經(jīng)典算法卻不變南陽理工學(xué)院2014_鐘詩俊引言備戰(zhàn)省賽：增強(qiáng)平時(shí)基礎(chǔ)算法知識(shí)的掌握和運(yùn)用注重平時(shí)題量的增加和思維的鍛煉注重平時(shí)的經(jīng)典題目掌握省賽最大亮點(diǎn)就是算法經(jīng)典

南陽理工學(xué)院2014_鐘詩俊河南省省賽試題分析模擬代碼題基礎(chǔ)數(shù)論知識(shí)基礎(chǔ)動(dòng)態(tài)規(guī)劃類貪心解決區(qū)間問題經(jīng)典圖論算法運(yùn)用數(shù)據(jù)結(jié)構(gòu)類型算法構(gòu)造題南陽理工學(xué)院2014_鐘詩俊模擬代碼題

簡單模擬題是相對(duì)簡單一些的題目，對(duì)于編程初學(xué)者可以說是練習(xí)代碼實(shí)現(xiàn)能力和代碼打字能力的題目，它基本上涉及不到什么太難的算法，這種題不需要太多的思考，有的簡單模擬也很麻煩。如果在ACM比賽中能遇上簡單模擬，那基本就是最簡單的題了。南陽理工學(xué)院2014_鐘詩俊例題1：房間安排

為了更好地接待在這期間來自世界各地的參觀者如何合理安排各賓館的住房問題提到了日程。組委會(huì)已接到了大量的客戶住宿定單，每張定單的內(nèi)容包括要住宿的房間數(shù)，開始住宿時(shí)間和要住的天數(shù)。為了便于整個(gè)城市各賓館的管理，組委會(huì)希望對(duì)這些定單進(jìn)行安排，目的是用盡可能少的房間來滿足這些定單，以便空出更多的房間用于安排流動(dòng)游客。

組委會(huì)請(qǐng)求DR.Kong來完成這個(gè)任務(wù)，對(duì)這些定單進(jìn)行合理安排，使得滿足這些定單要求的房間數(shù)最少。

假設(shè)：某個(gè)定單上的游客一旦被安排到某房間，在他預(yù)定住宿的期間內(nèi)是不換房間的。為了簡化描述，定單上的開始住宿時(shí)間為距離現(xiàn)在的第幾天。例如，定單為（10，30，5）表示游客要求使用10個(gè)房間，第30天開始連住5天。南陽理工學(xué)院2014_鐘詩俊例題1：房間安排閱讀題目：滿足所有定單要求的最少房間數(shù)提煉出題目：所有的可能天數(shù)中需要最多的房間數(shù)解決題目要求：用d[i]表示在第i天的最多房間數(shù)得出題目所求：遍歷所有時(shí)間得出一個(gè)最大的d[i]值南陽理工學(xué)院2014_鐘詩俊例題1：房間安排

如何快速正確得出d[i]？南陽理工學(xué)院2014_鐘詩俊例題1：房間安排對(duì)區(qū)間進(jìn)行處理

輸入:(a,b,c)d[b]+=ad[b+c]-=a表示在b天的時(shí)候需要增加a個(gè)房間，而在b+c天的時(shí)候有a間房間要退房遍歷d[i]找到最大值即為所求到此完美解決南陽理工學(xué)院2014_鐘詩俊例題1：總結(jié)解讀分析題意得出解決策略方法構(gòu)建算法模型求解結(jié)合原題模擬過程結(jié)合實(shí)際分析得出題目正解該題很好的體現(xiàn)了模擬算法的過程就是逐漸的分析靠近題目要求，得到可行算法最后編程得出正解王道之模擬！南陽理工學(xué)院2014_鐘詩俊例題1：程序?qū)崿F(xiàn)#include<stdio.h>#include<string.h>#defineMAX200intmain(){

intNcase,d[MAX];

scanf(&Ncase);

while(Ncase--){

memset(d,0,sizeof(d));

intmax=-1,n,a,b,c;scanf(&n);

while(n--){

scanf(&a,&b,&c);

d[b]+=a;

d[b+c]-=a;

}

for(inti=1;i<MAX;i++){

d[i]=d[i-1]+d[i];

if(max<d[i])

max=d[i];}

printf("%d\n",max);

}

return0;}

南陽理工學(xué)院2014_鐘詩俊基礎(chǔ)動(dòng)態(tài)規(guī)劃類動(dòng)態(tài)規(guī)劃主要用于組合優(yōu)化問題，即求一個(gè)離散問題在某種意義下的最優(yōu)解，有時(shí)也用于組合計(jì)數(shù)問題。那么什么樣的問題適合用動(dòng)態(tài)規(guī)劃求解呢？適合用動(dòng)態(tài)規(guī)劃求解的問題有兩個(gè)要素：(1)最優(yōu)子結(jié)構(gòu)性質(zhì)一個(gè)問題可用動(dòng)態(tài)規(guī)劃求解的基本要求是該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，通俗的講即問題的最優(yōu)解包含其子問題的最優(yōu)解。南陽理工學(xué)院2014_鐘詩俊基礎(chǔ)動(dòng)態(tài)規(guī)劃類(2)子問題重疊性性質(zhì)動(dòng)態(tài)規(guī)劃所針對(duì)的問題還有另一個(gè)顯著的特征，即他的子問題數(shù)中呈現(xiàn)大量的重復(fù)，稱子問題重疊性在應(yīng)用動(dòng)態(tài)規(guī)劃時(shí)，對(duì)于重復(fù)出現(xiàn)的子問題，只需在第一次遇到時(shí)加以求解，并把答案保存起來，以便以后遇到時(shí)直接引用，不必重新在求解，從而大大提高效率南陽理工學(xué)院2014_鐘詩俊例題2：聰明的kk

小動(dòng)物“KK”從沙漠區(qū)域（矩形）的左上角沿著向右或向下的方向往右下角跑去。KK太聰明了，它居然能在跑的過程中會(huì)選擇吃掉盡可能多的蟲子線路。要求：你知道它吃掉多少蟲子嗎？南陽理工學(xué)院2014_鐘詩俊例題2：聰明的kk第一行：NM(1≤NM≤200≤Xij≤500(i=1,2?.N,j=1,2?,M)

表示沙漠是一個(gè)N*M的矩形區(qū)域接下來有N行：每行有M個(gè)正整數(shù)，

Xi1Xi2……Xim表示各位置中的蟲子數(shù)（單個(gè)空格隔開）假設(shè)“KK”只能向右走或向下走。南陽理工學(xué)院2014_鐘詩俊例題2：算法分析

問題分析：對(duì)于每一步來說，只能向右或向下。而對(duì)于每個(gè)點(diǎn)來說要么走，要么不走。算法分析：直接暴力搜索

運(yùn)用動(dòng)態(tài)規(guī)劃思想優(yōu)化2^n！超時(shí)！如何優(yōu)化？對(duì)于很多狀態(tài)存在著重復(fù)計(jì)算！高效利用前一狀態(tài)計(jì)算結(jié)果！完美利用前一狀態(tài)結(jié)果避免重復(fù)計(jì)算達(dá)到優(yōu)化效果AC！南陽理工學(xué)院2014_鐘詩俊例題2：問題分析對(duì)題目先進(jìn)行常規(guī)探索，發(fā)現(xiàn)無法得到正解存在的主要問題是超時(shí)，要想出如何優(yōu)化在對(duì)超時(shí)算法進(jìn)一步分析，發(fā)現(xiàn)原因重復(fù)計(jì)算運(yùn)用動(dòng)態(tài)規(guī)劃處理重疊子結(jié)構(gòu)問題南陽理工學(xué)院2014_鐘詩俊例題2：算法剖析當(dāng)前所在位置(i,j)從左得到(i,j-1)從上得到(i-1,j)dp[i][j]+MaxMax(左邊,上面)南陽理工學(xué)院2014_鐘詩俊例題2：算法模型對(duì)于每個(gè)格子都有兩種選擇，走或不走通過優(yōu)化不在重復(fù)計(jì)算已經(jīng)得到的值避免重復(fù)計(jì)算利用動(dòng)態(tài)規(guī)劃思想解決重復(fù)問題經(jīng)典數(shù)塔模型南陽理工學(xué)院2014_鐘詩俊例題2：程序?qū)崿F(xiàn)#include<iostream>usingnamespacestd;intf[22][22];intmain(){ intn,m,c; cin>>m>>n; for(inti=1;i<=m;i++){ for(intj=1;j<=n;j++){ cin>>c; f[i][j]=max(f[i][j-1],f[i-1][j])+c; }} cout<<f[m][n]<<endl;}

南陽理工學(xué)院2014_鐘詩俊簡單圖論

圖論（Graphtheory）是數(shù)學(xué)的一個(gè)分支，它以圖為研究對(duì)象，研究頂點(diǎn)和邊組成的圖形的數(shù)學(xué)理論和方法。圖是區(qū)域在頭腦和紙面上的反映，圖論就是研究區(qū)域關(guān)系的學(xué)科。區(qū)域是一個(gè)平面，平面當(dāng)然是二維的，但是，圖在特殊的構(gòu)造中，可以形成多維（例如大于3維空間）空間，這樣的圖已經(jīng)超越了一般意義上的區(qū)域（例如一個(gè)有許多洞的曲面，它是多維的，曲面染色已經(jīng)超出了平面概念）。

圖論中的圖是由若干給定的頂點(diǎn)及連接兩頂點(diǎn)的邊所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用頂點(diǎn)代表事物，用連接兩頂點(diǎn)的邊表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。

圖論起源于著名的柯尼斯堡七橋問題。

圖論的研究對(duì)象相當(dāng)于一維的拓?fù)鋵W(xué)。摘抄之維基關(guān)于圖論的解釋和介紹南陽理工學(xué)院2014_鐘詩俊例題3：最舒適的路線異形卵潛伏在某區(qū)域的一個(gè)神經(jīng)網(wǎng)絡(luò)中。其網(wǎng)絡(luò)共有N個(gè)神經(jīng)元（編號(hào)為1,2,3,…,N），這些神經(jīng)元由M條通道連接著。兩個(gè)神經(jīng)元之間可能有多條通道。異形卵可以在這些通道上來回游動(dòng)，但在神經(jīng)網(wǎng)絡(luò)中任一條通道的游動(dòng)速度必須是一定的。當(dāng)然異形卵不希望從一條通道游動(dòng)到另一條通道速度變化太大，否則它會(huì)很不舒服。現(xiàn)在異形卵聚居在神經(jīng)元S點(diǎn)，想游動(dòng)到神經(jīng)元T點(diǎn)。它希望選擇一條游動(dòng)過程中通道最大速度與最小速度比盡可能小的路線，也就是所謂最舒適的路線。南陽理工學(xué)院2014_鐘詩俊例題3：最舒適的路線第一行：K表示有多少組測試數(shù)據(jù)。接下來對(duì)每組測試數(shù)據(jù)：第1行:NM第2~M+1行：XiYiVi(i=1,…..,M)表示神經(jīng)元Xi到神經(jīng)元Yi之間通道的速度必須是Vi最后一行：ST(S<T)【約束條件】2≤K≤51<N≤5000<M≤50001≤Xi,Yi,S,T≤N0<Vi<30000，Vi是整數(shù)。數(shù)據(jù)之間有一個(gè)空格。對(duì)于每組測試數(shù)據(jù)，輸出一行：如果神經(jīng)元S到神經(jīng)元T沒有路線，輸出“IMPOSSIBLE”。否則輸出一個(gè)數(shù)，表示最小的速度比。如果需要，輸出一個(gè)既約分?jǐn)?shù)。南陽理工學(xué)院2014_鐘詩俊例題3：最舒適的路線提煉題目要求：找到一條路，路上的最大速度和最小速度盡量接近如何，得到滿足這個(gè)要求的路徑？南陽理工學(xué)院2014_鐘詩俊例題3：最舒適的路線運(yùn)用最短路？顯然，這個(gè)只能保證從起點(diǎn)的到終點(diǎn)的總距離最小。比如：source,sink(1,2)131325128NO！在重新思考一下題目的本質(zhì)要求！要得到的是這樣一條特殊的路徑：最大速度和最小速度差值盡量的??！想想最小生成樹的建樹過程！是否覺得這個(gè)過程就是題目所要求的模型？！我們來重新溫習(xí)一下最小生成樹的建樹過程!南陽理工學(xué)院2014_鐘詩俊例題3：算法分析最小生成樹：1、隨意的選取一個(gè)點(diǎn)作為樹根2、尋找跟當(dāng)前點(diǎn)有連接且未更新過的點(diǎn)集中最小權(quán)值點(diǎn)3、從該點(diǎn)更新與其相連的點(diǎn)的權(quán)值4、不斷循環(huán)2，3知道一棵完整的樹建立完成

最小生成樹實(shí)現(xiàn)算法頗多，這里只介紹基本的算法思想不在介紹具體實(shí)現(xiàn)13245612578156假設(shè)以1為根下一個(gè)更新點(diǎn)3更新與1相連點(diǎn)當(dāng)前未更新最小權(quán)值點(diǎn)為4當(dāng)前未更新最小權(quán)值點(diǎn)為3以下的點(diǎn)同上方法更新與2相連點(diǎn)當(dāng)前未更新最小權(quán)值點(diǎn)為2更新與3相連點(diǎn)157521南陽理工學(xué)院2014_鐘詩俊例題3：模型分析為什么在運(yùn)用建立最小生成樹的過程中就可以求出該題的解呢？其實(shí)該題的算法模型就是圖論中經(jīng)典的最小瓶頸樹模型！算法的正確性證明，其實(shí)剛才在分析最小生成樹的建樹過程已經(jīng)給出。YES!證明！南陽理工學(xué)院2014_鐘詩俊例題3：程序?qū)崿F(xiàn)#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>usingnamespacestd;constdoubleEPS=1e-6;constdoubleINF=30005;constintMAXN=6000+5;structEdge{intfrom,to,dist;booloperator<(constEdge&rhx)const{returndist<rhx.dist;}}edges[MAXN];intf[MAXN];voidInit(intn){for(inti=0;i<=600;++i)f[i]=i;}intFind(intx){if(f[x]==x)returnf[x];returnf[x]=Find(f[x]);}voidUnion(intu,intv){inta=Find(u),b=Find(v);if(a!=b)f[a]=b;}intGCD(inta,intb){returnb==0?a:GCD(b,a%b);}南陽理工學(xué)院2014_鐘詩俊例題3：程序?qū)崿F(xiàn)if(minv-INF>=EPS)puts("IMPOSSIBLE");else{intg=GCD(a,b);if(a/g==1&&b/g!=1)printf("%d\n",b/g);elseif(a/g==1&&a/g==1)printf("1\n");elseprintf("%d/%d\n",b/g,a/g);}}return0;}intmain(){//freopen("Input.txt","r",stdin);intT,n,m,s,t;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(inti=0;i<m;++i)scanf("%d%d%d",&edges[i].from,&edges[i].to,&edges[i].dist);scanf("%d%d",&s,&t);sort(edges,edges+m);inta,b;doublex,y,minv=INF;for(inti=0;i<m;++i){Init(n);for(intj=i;j<m;++j){Union(edges[j].from,edges[j].to);