河南省历年省赛题目

河南省历年省赛题目分析2014年上学年算法讲座南阳理工学院

ACM集训队南阳理工学院2014_钟诗俊引言省赛是一次给自己定位的绝佳机会算法虽千变万化但万变不离其宗省赛题目相对以考察基础算法为主各届省赛亮点不同但经典算法却不变南阳理工学院2014_钟诗俊引言备战省赛：增强平时基础算法知识的掌握和运用注重平时题量的增加和思维的锻炼注重平时的经典题目掌握省赛最大亮点就是算法经典

南阳理工学院2014_钟诗俊河南省省赛试题分析模拟代码题基础数论知识基础动态规划类贪心解决区间问题经典图论算法运用数据结构类型算法构造题南阳理工学院2014_钟诗俊模拟代码题

简单模拟题是相对简单一些的题目，对于编程初学者可以说是练习代码实现能力和代码打字能力的题目，它基本上涉及不到什么太难的算法，这种题不需要太多的思考，有的简单模拟也很麻烦。如果在ACM比赛中能遇上简单模拟，那基本就是最简单的题了。南阳理工学院2014_钟诗俊例题1：房间安排

为了更好地接待在这期间来自世界各地的参观者如何合理安排各宾馆的住房问题提到了日程。组委会已接到了大量的客户住宿定单，每张定单的内容包括要住宿的房间数，开始住宿时间和要住的天数。为了便于整个城市各宾馆的管理，组委会希望对这些定单进行安排，目的是用尽可能少的房间来满足这些定单，以便空出更多的房间用于安排流动游客。

组委会请求DR.Kong来完成这个任务，对这些定单进行合理安排，使得满足这些定单要求的房间数最少。

假设：某个定单上的游客一旦被安排到某房间，在他预定住宿的期间内是不换房间的。为了简化描述，定单上的开始住宿时间为距离现在的第几天。例如，定单为（10，30，5）表示游客要求使用10个房间，第30天开始连住5天。南阳理工学院2014_钟诗俊例题1：房间安排阅读题目：满足所有定单要求的最少房间数提炼出题目：所有的可能天数中需要最多的房间数解决题目要求：用d[i]表示在第i天的最多房间数得出题目所求：遍历所有时间得出一个最大的d[i]值南阳理工学院2014_钟诗俊例题1：房间安排

如何快速正确得出d[i]？南阳理工学院2014_钟诗俊例题1：房间安排对区间进行处理

输入:(a,b,c)d[b]+=ad[b+c]-=a表示在b天的时候需要增加a个房间，而在b+c天的时候有a间房间要退房遍历d[i]找到最大值即为所求到此完美解决南阳理工学院2014_钟诗俊例题1：总结解读分析题意得出解决策略方法构建算法模型求解结合原题模拟过程结合实际分析得出题目正解该题很好的体现了模拟算法的过程就是逐渐的分析靠近题目要求，得到可行算法最后编程得出正解王道之模拟！南阳理工学院2014_钟诗俊例题1：程序实现#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;}

南阳理工学院2014_钟诗俊基础动态规划类动态规划主要用于组合优化问题，即求一个离散问题在某种意义下的最优解，有时也用于组合计数问题。那么什么样的问题适合用动态规划求解呢？适合用动态规划求解的问题有两个要素：(1)最优子结构性质一个问题可用动态规划求解的基本要求是该问题具有最优子结构性质，通俗的讲即问题的最优解包含其子问题的最优解。南阳理工学院2014_钟诗俊基础动态规划类(2)子问题重叠性性质动态规划所针对的问题还有另一个显著的特征，即他的子问题数中呈现大量的重复，称子问题重叠性在应用动态规划时，对于重复出现的子问题，只需在第一次遇到时加以求解，并把答案保存起来，以便以后遇到时直接引用，不必重新在求解，从而大大提高效率南阳理工学院2014_钟诗俊例题2：聪明的kk

小动物“KK”从沙漠区域（矩形）的左上角沿着向右或向下的方向往右下角跑去。KK太聪明了，它居然能在跑的过程中会选择吃掉尽可能多的虫子线路。要求：你知道它吃掉多少虫子吗？南阳理工学院2014_钟诗俊例题2：聪明的kk第一行：NM(1≤NM≤200≤Xij≤500(i=1,2„.N,j=1,2„,M)

表示沙漠是一个N*M的矩形区域接下来有N行：每行有M个正整数，

Xi1Xi2……Xim表示各位置中的虫子数（单个空格隔开）假设“KK”只能向右走或向下走。南阳理工学院2014_钟诗俊例题2：算法分析

问题分析：对于每一步来说，只能向右或向下。而对于每个点来说要么走，要么不走。算法分析：直接暴力搜索

运用动态规划思想优化2^n！超时！如何优化？对于很多状态存在着重复计算！高效利用前一状态计算结果！完美利用前一状态结果避免重复计算达到优化效果AC！南阳理工学院2014_钟诗俊例题2：问题分析对题目先进行常规探索，发现无法得到正解存在的主要问题是超时，要想出如何优化在对超时算法进一步分析，发现原因重复计算运用动态规划处理重叠子结构问题南阳理工学院2014_钟诗俊例题2：算法剖析当前所在位置(i,j)从左得到(i,j-1)从上得到(i-1,j)dp[i][j]+MaxMax(左边,上面)南阳理工学院2014_钟诗俊例题2：算法模型对于每个格子都有两种选择，走或不走通过优化不在重复计算已经得到的值避免重复计算利用动态规划思想解决重复问题经典数塔模型南阳理工学院2014_钟诗俊例题2：程序实现#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;}

南阳理工学院2014_钟诗俊简单图论

图论（Graphtheory）是数学的一个分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法。图是区域在头脑和纸面上的反映，图论就是研究区域关系的学科。区域是一个平面，平面当然是二维的，但是，图在特殊的构造中，可以形成多维（例如大于3维空间）空间，这样的图已经超越了一般意义上的区域（例如一个有许多洞的曲面，它是多维的，曲面染色已经超出了平面概念）。

图论中的图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用连接两顶点的边表示相应两个事物间具有这种关系。

图论起源于著名的柯尼斯堡七桥问题。

图论的研究对象相当于一维的拓扑学。摘抄之维基关于图论的解释和介绍南阳理工学院2014_钟诗俊例题3：最舒适的路线异形卵潜伏在某区域的一个神经网络中。其网络共有N个神经元（编号为1,2,3,…,N），这些神经元由M条通道连接着。两个神经元之间可能有多条通道。异形卵可以在这些通道上来回游动，但在神经网络中任一条通道的游动速度必须是一定的。当然异形卵不希望从一条通道游动到另一条通道速度变化太大，否则它会很不舒服。现在异形卵聚居在神经元S点，想游动到神经元T点。它希望选择一条游动过程中通道最大速度与最小速度比尽可能小的路线，也就是所谓最舒适的路线。南阳理工学院2014_钟诗俊例题3：最舒适的路线第一行：K表示有多少组测试数据。接下来对每组测试数据：第1行:NM第2~M+1行：XiYiVi(i=1,…..,M)表示神经元Xi到神经元Yi之间通道的速度必须是Vi最后一行：ST(S<T)【约束条件】2≤K≤51<N≤5000<M≤50001≤Xi,Yi,S,T≤N0<Vi<30000，Vi是整数。数据之间有一个空格。对于每组测试数据，输出一行：如果神经元S到神经元T没有路线，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。南阳理工学院2014_钟诗俊例题3：最舒适的路线提炼题目要求：找到一条路，路上的最大速度和最小速度尽量接近如何，得到满足这个要求的路径？南阳理工学院2014_钟诗俊例题3：最舒适的路线运用最短路？显然，这个只能保证从起点的到终点的总距离最小。比如：source,sink(1,2)131325128NO！在重新思考一下题目的本质要求！要得到的是这样一条特殊的路径：最大速度和最小速度差值尽量的小！想想最小生成树的建树过程！是否觉得这个过程就是题目所要求的模型？！我们来重新温习一下最小生成树的建树过程!南阳理工学院2014_钟诗俊例题3：算法分析最小生成树：1、随意的选取一个点作为树根2、寻找跟当前点有连接且未更新过的点集中最小权值点3、从该点更新与其相连的点的权值4、不断循环2，3知道一棵完整的树建立完成

最小生成树实现算法颇多，这里只介绍基本的算法思想不在介绍具体实现13245612578156假设以1为根下一个更新点3更新与1相连点当前未更新最小权值点为4当前未更新最小权值点为3以下的点同上方法更新与2相连点当前未更新最小权值点为2更新与3相连点157521南阳理工学院2014_钟诗俊例题3：模型分析为什么在运用建立最小生成树的过程中就可以求出该题的解呢？其实该题的算法模型就是图论中经典的最小瓶颈树模型！算法的正确性证明，其实刚才在分析最小生成树的建树过程已经给出。YES!证明！南阳理工学院2014_钟诗俊例题3：程序实现#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);}南阳理工学院2014_钟诗俊例题3：程序实现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);