骗分导论.doc

骗分导论
                       INTRODUCTION TO CHEATING IN NOIP
                          关于应付竞赛不会难题的策略
    大牛是稀有的,每道题都会的大牛更少。相信想我这样的人还是挺多的,那竞赛时遇到不会
    的难题怎么办呢???放弃???让100 分就这样流去???当然不能放弃。
【1】
遇到难题时心态要稳定,先搞定简单的题目,最后思考难题。心态是第一位。
【2】
如果难题实在不能解决也不能放弃,虽然写不出完美的算法,但可以用象贪心,搜索之
类的算法,虽然不能AC 但一般能过几个,有分总比没分好。
举个例子
穿越磁场(cross)
探险机器人在Samuel 星球上寻找一块奇特的矿石,然而此时它陷入了
一片神秘的磁场区域,动弹不得。
探险空间站立刻扫描了这片区域,绘制出该区域的磁场分布平面图。这
片区域中分布了N 个磁场,每个磁场呈正方形,且边与坐标轴平行。
例如下图中,存在3 个磁场,白点表示机器人的位置,黑点表示矿石的
位置:
科学家们分析平面图,进一步发现:这些磁场为大小不一的正方形,可
能相交,甚至覆盖,但是它们的边缘不会重合,顶点也不会重合。
例如下面的两种情形是不会出现的:
科学家们给探险机器人启动了磁力罩,这样它就可以在磁场中自由穿越
了。
初始时,探险机器人和所有矿石都不在任何磁场的边缘。由于技术限制,
X
Y
O
在穿越过程中机器人只能够水平或垂直移动,且不能够沿着磁场的边缘行
动。
由于磁力罩的能量有限,科学家们希望探险机器人穿越尽量少的磁场边
缘采集到这块矿石。例如上图中,探险机器人最少需要穿越两次磁场边缘。
现在小联请你编写程序,帮助科学家们设计探险机器人的路线,统计探
险机器人最少需要穿越多少次磁场边缘。
输入():第一行有一个整数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
3 3
2 1 4
0 0 3 4
输出:
2
当时我做这道题时很茫然,一点思路都没有。但我认为如果机器人和矿一个在磁场外面,
一个在里面就一定要穿越一次。如果都在里面或外面那就不穿越。但有特殊情况,虽然想到
了,但无法处理,所以我就用我错误的想法编了一个。
特殊情况:
如果时这样用我的算法算出来就是0,
但实际上是2。
我的程序主要代码如下
for
 i:=1 to n 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 分为两大部分,第一部分是取所有未标记点中的最小值,第二部分是用当前最
小值改进整个图。那么建立一个上小下大的堆