第一届河南省大学生程序设计竞赛题型简要分析

概览：

题数	类型
1	几何
2	图论
3	组合；分治
4	多重背包
5	模拟
6	贪心
7	深度优先搜索（剪枝）
8	拓扑排序（有向图）

【试题一】

练习处：

类型：几何

解法：每个物资在每个圆形区域的有效性可以转化为数学公式：

( 是圆心坐标，R是半径，x、y是落点坐标)。

然后就是利用双层循环，在每个圆中探测每个投放物资的坐标点，有效则输出”YES”,

无效则输出”NO”。

【试题二】

练习处：

类型：图论

解法：把相关数据存入图的边结构之后，求最小生成树。有两种简单算法供选择：Prim和Kruskal。其中，Prim算法适合求边稠密的最小生成树，而Kruskal算法适合求边稀疏的最小生成树。本题的“很多基站之间不能直接建立通信”说明边是稀疏的，那么选择Kruskal算法。

先对各个边按照权值进行升序排序，然后把各个顶点各自归为一组。依次取出各条边的两个顶点编号，判断是不是同一组：若两个顶点不在一组则可加入最小生成树，标记这条边加入了最小生成树；若两个顶点在一组（会构成回路）则放弃这条边。由于各条边已经按照权值递增排序，最后被标记为最小生成树的一边的所有边的权值之和则为题中所求最小代价。最后计算最小生成树中各条边的权值总和并输出。

【试题三】

密码破译

练习处：

类型：组合；分治

解法：对所有可能的钥匙组合进行穷举是个方法，但应该注意到：要求两个钥匙的长度之和恰好为此密码的长度，那么其中一把钥匙的长度必定大于等于密码长度的一半。先对钥匙进行升序排序，然后使用二分搜索法定位到第一个大于L/2(L为密码的长度)的元素位置，得到相邻两钥匙的长度之和and，如果and大于L则向左端搜索，否则向右端搜索，遇到and==L，保存两把破译的钥匙的编号。搜索完毕还没有相符的and，则无法找到破译此密码的钥匙。最后，如果相符的and只有一个，则直接输出；如果相符的and有多个，则选择起始编号最小的一组数据输出。

【试题四】

练习处：

类型：应该是多重背包问题

解法：多重背包问题描述是这样的，有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。参见：http://www.nocow.cn/index.php/多重背包。而现在只不过不求最大价值，要求装满背包（飞机）。

【试题五】

练习处：

类型：模拟

解法：对于每一个灾区，如果没有达到平均水平，则分别向左右（注意环形）搜索到最近的超过平均水平的灾区，并索取物资。另外一种思路是http://www.xushine.com/?p=853不太确定其正确性。此处有讨论。

【试题六】Time Limit:1000MS

练习处：http://poj.org/problem?id=1922

类型：贪心

题意：有一个勇士在行军时有一个习惯，跟着别人跑，还会跟着超过他的人跑，但是没人出发他就不出发。那么勇士何时能到达目的地？

解法：比勇士先出发的不用管了（一定不会跟在他们后面），勇士会跟着在他之后出发的并且最先到达目的地的士兵一块到达。

【试题七】Time Limit: 1000MS（这个提示原来是标准输出之后的）

练习处：http://poj.org/problem?id=1011

http://acm.tju.edu.cn/toj/showp1009.html

类型：深度优先搜索（剪枝）

题意：乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。

解法：对这些木棍逆序排序，然后假定最长的木棍为最优解，检查是否可以砍断为这些木棍，如果不行，长度加1继续检查。检查过程是：从这些木棍中选取第一个（最长的）开始尝试组合第一根棍子，如果不够长，加入下一根，直到组合成功，接着组合下一根棍子。

【试题八】

练习处：http://poj.org/problem?id=1094

类型：拓扑排序（有向图）

题意：对前n个字母，输入m组确定他们之间的大小关系，从而判断有没有唯一的序列。

第一种:输出，在前t(t<=m)已能确定一个序列

第二种:不能确定唯一的序列

第三种:不存在拓扑排序

当所有关系式输入后无法排序则输出无法排序。

解法：

1、注意拓扑排序只在有向无环图中有效，关键在于要在每次输入关系后做一次有无环的判断。

：如果已经输入的有向图中的点,不存在入度为0的点,则该有向图存在回路

：如果已经输入的入度为0的点大于一个,则该有向图肯定不存在一个可以确定的拓扑序列但并不妨碍拓扑排序，还要检测是否已经出现了环（存在回路）。

2、还可以使用深度优先搜索来实现拓扑排序，根据每个结点的结束访问时间的降序对结点进行拓扑排序，如果在某个结点的扩展过程中发现反向边，则出现了矛盾；否则对所得到的结点序列，进行一次遍历，对于相邻的结点检测是否存在连接边（存在则表示它们的顺序已经可以确定），如果所有的相邻结点都可确定顺序，则这个序列是完全有序的，对于后面的输入可以忽略；如果处理完所有的输入还不能得到完全有序序列，则输出序列顺序不能确定。

3、Warshall算法（求二元关系的传递闭包），但时间复杂度为O(n³)。

赛题见：http://download.csdn.net/download/wujun8/4218470