2011-11-03 46页 pdf 216KB 33阅读
is_821124
暂无简介
N,那么就可
以回溯,不必继续搜索了。
剪枝效果有所削弱
但是空间复杂度降到了O(mP),这里P可以任取。
•取P为大质数。(比如<10000的最大质数)
•剪枝效果相当的好。题目给定范围内的数据都在1s内解。
•注意要使用高精度。
总结
1、空间换时间。
2、抓住主要矛盾,用同余法解决空间矛盾。
Amazing Robots: IOI2003
已知条件:
迷宫
i(i=1,2)
(每个不会大于20*20)
守卫
Gi(0<=Gi<=10)
(守卫循环移动进行执勤)
(守卫巡逻的方格数(2..4))
求:
两个机器人都离开迷宫所用的最少指令数目
和离开制指令序列(10000 步以内)。
•每一步可以发出的命令可以是N, E, S, W中的一种,
有4种选择。
•对每一步具体发出哪个命令,直接搜索。
•假设最后结果是T。(也就是最少出宫时间)
•时间复杂度是O(4T)
这种方法时间复杂度太高,绝对不可行!!
•5*4和4*4的迷宫
•第一个机器人的位置是(2,2)
•第二个机器人的位置是(3,2)
•当前时间是0。
•状态((2,2),(3,2),0)
状态表示:
(第一个机器人位置,第二个机器认位置,时间)
E
((2,2),(3,2),0) ((2,3),(3,3),1)
•时间已知,则所有Guard的位置可知。
•Guard、Robot的位置均已知,所以状态可以转移
•设出宫时间是T。
•总共(n*n)*(n*n)*T种状态。
•用BFS实现算法,HASH表判重。
•总的复杂度是O(Tn4)。
T<=10000, n<=20。
时间复杂度太大,不可承受!
0时刻 1时刻 2时刻 3时刻
•0时刻和2时刻是一样的
•1时刻和3时刻是一样的。
•稍加分析:此Guard循环以2为周期循环。
•状态转移,需要的信息是:Robot位置,Guard位置。
•Position of Robot1, 2是的作用就是记录Robot位置。
•Time的作用就是为了计算Guard的位置
•状态:(position of Robot1, position of Robot2, Time)
•Time<=10000,这是状态数过多的罪魁祸首!
•题目说:Guard巡逻经过的格子数只可能是2, 3, 4。
•也就是说机器人巡逻周期只能是2, 4, 6。
•[2, 4, 6]=12,所以第0时刻、12时刻、24时刻……Guard的
状态完全相同。
•12可以看作Guard的周期。Time只要记录当前是第几个周
期。因为周期确定了,Guard的位置也完全确定了!
0<=Time<=11
•状态数(n*n)*(n*n)*12=12n4。
•用BFS算法,标志数组判重。
•时间复杂度O(12n4)。
n<=20
完全可以承受
智破连环阵(N0I2003)
已知:
M个武器(1 ≤ M≤ 100)
N棵炸弹(1 ≤ N≤ 100)
炸弹爆炸半径(1≤ k≤ 1000)
炸弹消灭半径范围以内的,处于攻击状态的武器
第i号武器被消灭后,第i+1号武器立即处于攻击状态
要求:用最少的炸弹消灭所有的武器
示例图
问题转化
• 设炸弹的攻击的半径为r
• 第i号炸弹的坐标为(u[i],v[i])
• 第j号武器的坐标为(x[j],y[j])
则炸弹i能炸到炸弹j的基本条件是
(u[i]-x[j])2+(v[i]-y[j])2<=r2
我们可以枚举哪些炸弹是否爆炸,使得消灭
所有得武器,时间复杂度为M*2n ,M,N可达到
100,显然此方法时间复杂度巨大。
按武器搜索怎么样?
1)我们必须将武器按它的编号划分成若干段
2)每一段的武器,哪些炸弹能对它们进行销毁,
如下图:
算法
• 将武器根据编号分为x段,[Si,Ti]
(S1=1,Ti>=Si,Ti+1=Si+1)。
• 然后判断是否可以从A国的N颗炸弹中选出
x颗,分别可以炸掉其中的一段。
如何分段:搜索算法
如何分段,理论复杂度为2m ,需要优化,
留给学生思考?
如何选取炸弹:二分图的匹配
子串
• 给定一个由自然数串联而成的无限数列
1234567891011121314……(母串)
• 求任意一个长度不超过200的数列(子串)
在其中最早出现的位置。
分析:
• 首先,由于母串可无限扩充,显然我们不
可能把它全部生成出来。
• 如果边生成母串,边判断所生成的数串是
否包含给定的子串,即使是使用字符串处
理中高效的KMP算法,耗费的工作量也是
巨大的。
1121314
• 先枚举第1位1
• 自然数1之后为2,3,……
• 母串中形如123……
• 与子串从第2位开始不符
• 枚举前2位11
• 自然数11之后为12,13……
• 母串中形如111213……
• 与子串从第3位开始不符
• 考虑第2位开始12
• 自然数12之前为11,
末位与子串第1位相
同,之后为
13,14,……
• 母串中形如
1314……
• 与子串匹配!
如何优化呢?
• 较好的方法是另辟蹊径:
• 刚才我们枚举的是母串的每一位,不妨换
一个角度,从子串着手。
• 先来观察一些片断:
12345678910111213141516……
很自然得到算法:
• 枚举子串所包含第一个完整的数a的位数La。
• 假设a在母串的第k位出现(k<=La)
• 判断接下来由a生成的序列是否与子串吻合。
• 如果吻合,则最优解的判断:
– (1) La