文档介绍：骗分导论 INTRODUCTION TO CH EATING IN NOIP 关于应付竞赛不会难题的策略大牛是稀有的,每道题都会的大牛更少。相信想我这样的人还是挺多的,那竞赛时遇到不会的难题怎么办呢???放弃???让 100 分就这样流去???当然不能放弃。【1】遇到难题时心态要稳定, 先搞定简单的题目, 最后思考难题。心态是第一位。【2】如果难题实在不能解决也不能放弃,虽然写不出完美的算法,但可以用象贪心,搜索之类的算法,虽然不能 AC 但一般能过几个,有分总比没分好。举个例子穿越磁场( cross ) 探险机器人在 Samuel 星球上寻找一块奇特的矿石,然而此时它陷入了一片神秘的磁场区域,动弹不得。探险空间站立刻扫描了这片区域,绘制出该区域的磁场分布平面图。这片区域中分布了 N 个磁场,每个磁场呈正方形,且边与坐标轴平行。例如下图中,存在 3 个磁场,白点表示机器人的位置,黑点表示矿石的位置: 科学家们分析平面图,进一步发现:这些磁场为大小不一的正方形,可能相交,甚至覆盖,但是它们的边缘不会重合,顶点也不会重合。例如下面的两种情形是不会出现的: 科学家们给探险机器人启动了磁力罩,这样它就可以在磁场中自由穿越了。初始时,探险机器人和所有矿石都不在任何磁场的边缘。由于技术限制, XYO 在穿越过程中机器人只能够水平或垂直移动,且不能够沿着磁场的边缘行动。由于磁力罩的能量有限,科学家们希望探险机器人穿越尽量少的磁场边缘采集到这块矿石。例如上图中,探险机器人最少需要穿越两次磁场边缘。现在小联请你编写程序,帮助科学家们设计探险机器人的路线,统计探险机器人最少需要穿越多少次磁场边缘。输入( ):第一行有一个整数 N ,表示有 N 个磁场(1<N< 100 )。随后有 N 行,每行有三个整数 X、Y、C(0<X ,Y ,C< 10000 ),表示一个磁场左下角坐标为( X,Y ), 边长为 C。接下来有一行, 共有四个整数 SX, SY, TX, TY ,表示机器人初始坐标为( SX, SY ),矿石坐标为( TX, TY )(其中, 0<S X, SY, TX, TY< 10000 )。输出( ): 单行输出一个整数, 表示机器人最少需要穿越多少次磁场边缘。样例: 输入: 21 332140034 输出: 2 当时我做这道题时很茫然,一点思路都没有。但我认为如果机器人和矿一个在磁场外面, 一个在里面就一定要穿越一次。如果都在里面或外面那就不穿越。但有特殊情况,虽然想到了,但无法处理,所以我就用我错误的想法编了一个。特殊情况: 如果时这样用我的算法算出来就是 0, 但实际上是 2。我的程序主要代码如下 for i:=1 ton do if ((sx<map[i,1]+c[i]) and (sx>map[i,1]) and (sy<map[i,2]+c[i])and (sy>map[i,2])) xor ((tx<map[i,1]+c[i])and (tx>map[i,1]) and (ty<map[i,2]+c[i] )and (ty>map[i,2])) then inc(total) ; 很短,但数据太弱了,没有一个有如上可能。所以我全过了这样是很划算的,如果当时放弃就一分都没有了~。附标准算法( 2006 全国冬令营汪晔): (有点复杂,当时我绝对想不出来。) 问题分析: 方法 1: 将坐标中的所有整点坐标当作顶点,在每个点与坐标系中相邻的点间加一条无向边,如果穿过磁场,边的权值为 1 ,否则权值为 0。求机器人从起点到终点的最小耗费,也就是求构造的图中两点之间的最短路径,我们可以用 Dijkstra 解决。每次循环中寻找最大值的复杂度为 O(V) , 改进相邻点时由于要判断是否穿过磁场边, 所以复杂度为 O(N) 。整个算法复杂度为就是 O(VN+V2) ,这里 V= 整个坐标中的点的个数=10000*10000 ,显然超时。当然,在实现过程中我们可以有所优化,比如确定查找点的范围。作者: 龚铖 2006-11-16 09:01 回复此发言 2 骗分导论-- 宇宙史上最为牛的奥赛资料( 要求加精置顶) 方法 2: Dijkstra 分为两大部分, 第一部分是取所有未标记点中的最小值,第二部分是用当前最小值改进整个图。那么建立一个上小下大的堆, 堆中保存所有起始点到图中未标记的点的最 00010100010********** 00Oxy000000111011111000000000000000101122 短路径值,这样每次取出一个最小值的复杂度为 O(1) ; 由于此图中,每个点的度最多为 4, 查找边的权值的复杂度为 O(N) ,更新堆的复杂度为 O(Vlog2V) 。因而算法复杂