河南省歷年省賽題目

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

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

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

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

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

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

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

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

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

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

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

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

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

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

運(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！南陽(yáng)理工學(xué)院2014_鐘詩(shī)俊例題2：?jiǎn)栴}分析對(duì)題目先進(jìn)行常規(guī)探索，發(fā)現(xiàn)無(wú)法得到正解存在的主要問(wèn)題是超時(shí)，要想出如何優(yōu)化在對(duì)超時(shí)算法進(jìn)一步分析，發(fā)現(xiàn)原因重復(fù)計(jì)算運(yùn)用動(dòng)態(tài)規(guī)劃處理重疊子結(jié)構(gòu)問(wèn)題南陽(yáng)理工學(xué)院2014_鐘詩(shī)俊例題2：算法剖析當(dāng)前所在位置(i,j)從左得到(i,j-1)從上得到(i-1,j)dp[i][j]+MaxMax(左邊,上面)南陽(yáng)理工學(xué)院2014_鐘詩(shī)俊例題2：算法模型對(duì)于每個(gè)格子都有兩種選擇，走或不走通過(guò)優(yōu)化不在重復(fù)計(jì)算已經(jīng)得到的值避免重復(fù)計(jì)算利用動(dòng)態(tài)規(guī)劃思想解決重復(fù)問(wèn)題經(jīng)典數(shù)塔模型南陽(yáng)理工學(xué)院2014_鐘詩(shī)俊例題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;}

南陽(yáng)理工學(xué)院2014_鐘詩(shī)俊簡(jiǎn)單圖論

圖論（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)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用頂點(diǎn)代表事物，用連接兩頂點(diǎn)的邊表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。

圖論起源于著名的柯尼斯堡七橋問(wèn)題。

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

最小生成樹(shù)實(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南陽(yáng)理工學(xué)院2014_鐘詩(shī)俊例題3：模型分析為什么在運(yùn)用建立最小生成樹(shù)的過(guò)程中就可以求出該題的解呢？其實(shí)該題的算法模型就是圖論中經(jīng)典的最小瓶頸樹(shù)模型！算法的正確性證明，其實(shí)剛才在分析最小生成樹(shù)的建樹(shù)過(guò)程已經(jīng)給出。YES!證明！南陽(yáng)理工學(xué)院2014_鐘詩(shī)俊例題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);}南陽(yáng)理工學(xué)院2014_鐘詩(shī)俊例題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);