极品飞车

 时间:2018-08-09 00:44:04 贡献者:lisuyan210

导读:极品飞车 flycar 【题目】 Statement FC 星有许多城市,某些城市之间无法直接到达,但某些城市之间可以通过一种奇怪的 高速公路 SARS (Super Air Roam Structure 超级空中漫游结构) 进行人员或物资

极品飞车ol壁纸高清
极品飞车ol壁纸高清

极品飞车 flycar 【题目】 Statement FC 星有许多城市,某些城市之间无法直接到达,但某些城市之间可以通过一种奇怪的 高速公路 SARS (Super Air Roam Structure 超级空中漫游结构) 进行人员或物资的交流运输。

每条 SARS 都对行驶在他上面的 Flycars 限了固定的速度。

同时 FC 星人对 flycar 的 “舒适度” 也有特殊的要求。

他们认为乘坐一次 flycar 过程中,flycar 达到的最高速与最低速之间的差 越小,本次乘坐越舒适(可以理解,因为 SARS 的限速要求,flycar 都必须瞬间提/降速,痛 苦啊)——FC 星人对时间却没那么多要求。

Problem 因此 Hecy 的任务就明确了: 为 FC 星上几乎垄断了 flycar 市场的全星通用汽车公司 (CC) 设计新一代自动寻路 flycar,使得该 flycar 能自动寻找两城市间最舒适的到达路径。

【解答】 本题是考察并查集数据结构的经典题目。

不会并查集的人用 heap + dijkstra 当然也能比 较好的解决, 但是理论上复杂度比并查集大; 熟练运用并查集的人可以对基本的并查集算法 进行改进得到更快一些的算法;当然使用了 ack 对 findroot 优化后几乎能使算法逼近关于|E| 线性(@_@) 。

当然普通的比赛我们用一般并查集就够了;上面说的“更快的并查集算法” 实施证明并没有想象中的快(但还是快了很多) ,因此下面主要写一下基本的并查集算法, 以及适合学弟学妹的 heap + dijkstra 算法。

1) heap + dijkstra A. 把所有边按照 speed 从小到大排序 (当然从大到小也大致一样, 只有细节上的不同而 已) 。

枚举 lowspeed; B. 对每个 lowspeed,在整个图中用 dijkstra 寻找起点到终点的最短路(要求所有边的 speed >= lowspeed) ,这个“最短路”的意思是整条路的最高 speed 最小; C. 对 dijkstra 中 “每次寻找到源集距离最近的点” 这一步, 使用 binheap (二叉堆)优化; 这样总的复杂度是 O(e*n*log(n))。

(备注. 关于 binheap) binheap 常常用来优化某些算法的子部分;这样的“某些算法”的共同点是:有一列数, 这些数经常变动,且算法经常需要求这列数中间最大(最小)的一个的值。

这时候可以把这 列数存在一个连续的内存空间中(也就是数组拉 ft) ,并在初始化时将其修复为一个最大堆 (或最小堆,以下都称为 binheap) 。

这样每次变动数列内某个数的值时,只需要根据相应的 变化方向(变大或变小)把这个变化的数在 binheap 中进行相应的向上修复或向下修复就能 在O (logn) 时间内恢复 binheap 的性质; 取数时也一样, 只要把最后一个数放到空出的 root 处,自 root 向下修复一次就能恢复 binheap 性质。

相对普通算法(改数据 O(1) ,取数据 O (n) ) ,binheap 优势明显。

2) 基本的并查集算法 A. 同上面的; B. 对每个 lowspeed,将 highspeed 定为 < lowspeed,这样当然不存在合法的边,更不存 在从起点到终点的路径,这样可以把 n 个顶点看成 n 个连通分支; C. 逐 “边” 增加 highspeed, e.g. 按照 speed 大小从小到大逐条增加合法边 (当然 speed >= lowspeed) ,在增加合法边的同时连通分支也在逐渐减少,当起点与终点在同一个连通分支 里时,与上面的 B 相同的目的就达到了; D. 上面这个不断合并连通分支的过程用并查集实现;

这样总的复杂度为 O(e*e); 3) 并查集算法的优化 A. 同上面的; B. 令 lowspeed 与 highspeed 都指向最慢边; C. 不断增加 highspeed,直到找到路; D. 令 lowspeed = highspeed,不断减少 lowspeed,直到找到路,此时得到一个可行解; E. 将 lowspeed 微增; F. 回到 B,直到找不到路; 这个算法的复杂度从理论上讲是 O(e),但是常数可能较大,另外正确性容易证明。

Lord of ring ring 【题目】 Problem Hecy 把 n 个 ring(0 < n < 31)扔在地上,rings 之间不相切、任意三个 ring 不共点,求 地上一共被 rings 圈住了几个封闭区域。

【解答】 本题的解答可以很繁,也可以非常简单,关键就是是否懂得灵活运用一个古老的几何定 理。

〖Euler 定理〗 设空间内的简单多面体 A =(V,E,F)拥有 v 个顶点,e 条边,f 个面,则整数 v,e, f 之间存在下面的关系:v + f - e = 2; 〖Euler 定理的推论〗 设平面内的简单多边形 G =(V,E)拥有 v 个顶点,e 条边,f 个封闭区域,则 v,e, f 之间存在这个关系:v + f – e = 1; 本题事实上扩展了这个定理(推论) ,将他用到了多个图上。

〖Euler 定理的推论在本题的扩展〗 设平面内形如本题的图 G =(V,E)拥有 v 个顶点,e 条边,f 个封闭区域,t 个连通分 支,则 v,e,f,t 之间存在这个关系:v + f = e + t ; (没有严格证明,但应该是对的) 接下来的事情就好办了: 1, 统计 e :因为不存在三圆共点,任意两圆(A,B)一交就各多 2 条边(不妨认为单一 的圆 v = e = 0) ; 2, 统计 v :与第一几乎一样; 3, 统计 t :把圆当成点,两圆相交就连条弧,dfs(O(n))统计连通分支; 4, f = e + t – v ; 就这样,很简单吧 《星球开发》出题报告出题目的 这是一题比较简单的提交答案的题目,程序思路、设计都不复杂,出题主要 目的是想考察选手的搜索能力:如何确定恰当的搜索规则,高效完成搜索。

出题思路

在把题目理解后, 就会想到可能可以用搜索来解决。

但是因为是最优化问题, 选手也可能会尝试用动态规划等手段去解决。

解题思路是,先搜索出所有的拼接方案,把这些方案存在文件里,再用另外 一个程序测试按照这些拼接方案能够取得的最好成绩,从中选取一个最佳的。

不 论数据的规模如何,拼接方案都是一样的,这样生成好所有的拼接方案后,可以 给各个数据使用。

李翼思路:1. 按速度把所有边排序. 枚举速度最小的边, 然后按速度从小到大添加边, 直到起点和终点连 通. 连通性判断可以用并查集. 2. 记录每一个段弧...每添加一个圆, 考察与已知弧的交点. 每次都得到一些新的弧.最后我们知 道交点数目 E 和弧数 V, 区域 F 满足 V-E+F=1 3. 广度搜索.不过我考试的时候也是深度的, 所以得分不高.第一次测试的解题报告福州八中【FlyCar】因为最后要求得路径数并不多,所以我对于每一对起始点和终点,采用如下算法:记录到达从起始到每个顶点时有可能出现的所有状态 (vj[k].max,vj[k].min)即记录一种方案途中的最大值和最小值,一旦一个顶点 s 的状况更新了,那么试图利用它更新跟它相连接的所有顶点,判断一个顶点 t 是否会被 s 更新的方法: 我们定义:一个状态(min1,max1)优于某种状态(min2,max2) 当且仅当(min1>min2)且(max1max2)Vs[k ].min, f [s, t ]}, max{ Vs[k ].max, f [s, t ]) 考虑任意的 k,都有状态 (min{1.如果该状态劣于 Vt 的某个状态则放弃此状态。

2.如果该状态优于 Vt 的某些状态则在 Vt 的状态表中用此状态替换它们。

3.如果此状态不优于并且不劣于任何一个 Vt 的状态则将此状态插入到 Vt 的状 态列表。

最后从终点的状态中挑选一种状态使得状态中的 max 与 min 的差最小,即最优 解。

--Copyright byFacker

【Lord Of Ring】首先,因为题目说任意三圆不交一点。

if (R-r)

故我们只要用两圆的圆心距与半径和、差关系来判断两圆关系。

相离、内含依此类推(内切,外切题目不要求)并用一个矩阵来记录这些圆的 关系。

如果一些圆,它们,可以通过相交的邻接的圆关联起来,那么这些圆属 于一个圆的集团。

因为两个圆如果不属于一个集团,那么它们划分出的区域就没有本质的联 系。

我们计算圆分割出的区域就一个一个集团考虑。

经过枚举,发现:如果一个集团中的圆共相交产生 M 个交点,就划分出 M +1 个区域。

(一个单独的圆,0 个交点,一个区域) 然后,宽搜出这些集团。

计算交点,得出区域。

测试数据,发现大部分不对,但小数据经手算也与参考数据结果不同。

经多 次测试,发现如果把两圆内含也看做相交,则所得结果与参考数据结果同。

不 过此种做法我们觉得显然是错误的。

—Copyright byGaoBin题三: 首先用贪心求个最优解,便于剪枝。

搜索过程中首先找可到达区域内可吃到的 DS 中最大的, 如果比其它的大得 多,则直接取该块,缩小可选择的 U 板个数。

注意剪枝:如果可选区域内的所 有 DS 和都不比最优解大,则 Search_End; 既然是提交答案式的题目,就结合数据搜索,先观察数据特点,针对该数 据写剪枝。

另外,前几个数据直接看就可以知道最优解了,所以就不用针对这些数据 进行搜索了。

—Copyright by 第一次训练解题报告 福州三中李榕滨 题一:flycar 分析: 题目要求从起始点到目标点的最大权与最小权之差最小的路径。

我们可先枚举出最小 权的边,然好求出在以该边为最小权情况下的最大权的边。

实现方法有很多种,用并查集的 方法应该是比较好的。

具体方法是不断地加边,看看起始点与目标点是否连通。

题二:ring. 分析: 题目要我们求出封闭区域的数目, 大致做法是先求出所有的区域的数目, 再减 1 就是封 闭区域的个数。

设第 1 至第 n 个圆将平面划分成的区域个数是 f(n),那么考察第 n+1 个圆。

Yuanqi

设前 n 各圆与第 n+1 个圆的交点数目是 2k.若 k=0,那么就多了一个区域,若 k>0,那么就多 了 2k 个区域。

题三: 我没有什么比较好的做法,只是用搜索。

 
 

微信关注公众号,送福利!