注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

xiaochen7777的博客

http://player.youku.com/player.php/sid/X

 
 
 

日志

 
 
关于我

了如指掌,方能规划人生。是说人应该了解一下自己手上的掌纹,它能对你的人生进行导航。(Q号:1583223327),共同学习。

网易考拉推荐
 
 

上海市NOI2008选拔赛的原题 (2009-03-15 15:15:59)  

2014-09-02 10:34:06|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
标签: 

杂谈

汉诺塔 Hanoi
【问题描述】
汉诺塔由三根柱子(分别用A、B、C表示)和n个大小互不相同的空心盘子组成。一开始n个盘子都摞在柱子A上,大的在下面,小的在上面,形成了一个塔状的锥形体。
对汉诺塔的一次合法的操作是指:从一根柱子的最上层拿一个盘子放到另一根柱子的最上层,同时要保证被移动的盘子一定放在比它更大的盘子上面(如果移动到空柱子上就不需要满足这个要求)。我们可以用两个字母来描述一次操作:第一个字母代表起始柱子,第二个字母代表目标柱子。例如,AB就是把柱子A最上面的那个盘子移到柱子B。汉诺塔的游戏目标是将所有的盘子从柱子A移动到柱子B或柱子C上面。
有一种非常简洁而经典的策略可以帮助我们完成这个游戏。首先,在任何操作执行之前,我们以任意的次序为六种操作(AB、AC、BA、BC、CA和CB)赋予不同的优先级,然后,我们总是选择符合以下两个条件的操作来移动盘子,直到所有的盘子都从柱子A移动到另一根柱子:
(1)这种操作是所有合法操作中优先级最高的;
(2)这种操作所要移动的盘子不是上一次操作所移动的那个盘子。
可以证明,上述策略一定能完成汉诺塔游戏。现在你的任务就是假设给定了每种操作的优先级,计算按照上述策略操作汉诺塔移动所需要的步骤数。
【输入格式】
输入有两行。第一行为一个整数n(1≤n≤30),代表盘子的个数。第二行是一串大写的ABC字符,代表六种操作的优先级,靠前的操作具有较高的优先级。每种操作都由一个空格隔开。
【输出格式】
只需输出一个数,这个数表示移动的次数。我们保证答案不会超过10的18次方。
【样例】
3
AB BC CA BA CB AC
输出 7
2
AB BA CA BC CB AC
输出 5
【数据规模】
对于20%的数据,n ≤ 10。
对于100%的数据,n ≤ 30。

安全的航线 Flight
【问题描述】
在设计航线的时候,安全是一个很重要的问题。首先,最重要的是应采取一切措施确保飞行不会发生任何事故,但同时也需要做好最坏的打算,一旦事故发生,就要确保乘客有尽量高的生还几率。
当飞机迫降到海上的时候,最近的陆地就是一个关键的因素。航线中最危险的地方就是距离最近的陆地最远的地方,我们称这种点为这条航线“孤地点”。孤地点到最近陆地的距离被称为“孤地距离”。作为航空公司的高级顾问,你接受的第一个任务就是尽量找出一条航线的孤地点,并计算这条航线的孤地距离。
为了简化问题,我们认为地图是一个二维平面,陆地可以用多边形近似,飞行线路为一条折线。航线的起点和终点都在陆地上,但中间的转折点是可能在海上(如下图所示,方格标示出了孤地点)。
【输入格式】
输入的第一行包括两个整数C和N(1≤C≤20,2≤N≤20),分别代表陆地的数目的航线的转折点的数目。
接下来有N行,每行有两个整数x,y。(x,y)表示一个航线转折点的坐标,第一个转折点为航线的起点,最后一个转折点为航线的终点。
接下来的输入将用来描述C块大陆。每块输入由一个正整数M开始(M≤30),M表示多边形的顶点个数,接下来的M行,每行会包含两个整数x,y,(x,y)表示多边形的一个顶点坐标,我们保证这些顶点以顺时针或逆时针给出了该多边形的闭包,不会出现某些边相交的情况。此外我们也保证输入数据中任何两块大陆不会相交。
输入的所有坐标将保证在-10,000到10,000的范围之间。
【输出格式】
输出一个浮点数,表示航线的孤地距离,数据保留2位小数。
【样例】
1 2
-9 -6
5 1
3
0 16
-16 -12
17 -6
输出 0.00
2 3
12 4
16 17
3 9
4
1 0
4 19
19 14
6 12
3
10 10
5 3
18 2
输出 2.94
【数据规模】
对于50%的数据,1≤C≤2,2≤N≤5;
对于100%的数据,1≤C≤20,2≤N≤20。

堵塞的交通 Traffic
【问题描述】
有一天,由于某种穿越现象作用,你来到了传说中的小人国。小人国的布局非常奇特,整个国家的交通系统可以被看成是一个2行C列的矩形网格,网格上的每个点代表一个城市,相邻的城市之间有一条道路,所以总共有2C个城市和3C-2条道路。
小人国的交通状况非常槽糕。有的时候由于交通堵塞,两座城市之间的道路会变得不连通,直到拥堵解决,道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事,部长听说你来自一个科技高度发达的世界,喜出望外地要求你编写一个查询应答系统,以挽救已经病入膏肓的小人国交通系统。
小人国的交通部将提供一些交通信息给你,你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式:
Close r1 c1 r2 c2:相邻的两座城市(r1,c1)和(r2,c2)之间的道路被堵塞了;
Open r1 c1 r2 c2:相邻的两座城市(r1,c1)和(r2,c2)之间的道路被疏通了;
Ask r1 c1 r2 c2:询问城市(r1,c1)和(r2,c2)是否连通。如果存在一条路径使得这两条城市连通,则返回Y,否则返回N;
【输入格式】
第一行只有一个整数C,表示网格的列数。接下来若干行,每行为一条交通信息,以单独的一行“Exit”作为结束。我们假设在一开始所有的道路都是堵塞的。
【输出格式】
对于每个查询,输出一个“Y”或“N”。
【样例】
2
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit
输出Y
N
3
Open 1 1 1 2
Ask 1 1 1 2
Close 1 1 1 2
Ask 1 1 1 2
Exit
输出
Y
N
【数据规模】
对于30%的数据,C≤1,000,信息条数≤1,000;
对于100%的数据,C≤100,000,信息条数≤100,000。

 

 

汉诺塔:我们班有人用递推做出来了,而我是找规律的。搜了一批发现,答案有2^n、2*3^(n-1)-1以及3^(n-1),总共3种情况。(在n=3时,对应的优先序列分别可以是{AB AC BC BA CA CB}、{AB AC BA CB CA BC}和{AB AC BC BA CB CA}。)第一和第三种比较容易看出来,第二种我是借助Excel乱试才发现的。知道了这样以后,把输入序列拿过来,另n=3,看答案是7、9或者17,再分别套上面的公式去做。这题找规律找得我很得意,为后面的悲惨埋下了伏笔……

安全的航线:计算几何。我不会,听汤牛讲解的时候是说二分答案,把顶点扩充成圆、边扩充成矩形,然后判断所有航线段是不是都在这个图形内。计算几何很麻烦,有人整个早上在做这题……

堵塞的交通:生死一行代码。我能再考场上想出正确算法却时间不够,有个小东西写反了,错了,结果人家朴素还比我多20分!我写麻烦了,其中有个东西,我连续复制了16次!总代码有200多行!其实能写得更漂亮,只是考场上搞不定。做法是用线段树维护。每个线段维护它的左上能不能到右上、右下,同理左下能不能。如果用U来表示上、D来表示下,就是需要维护UU、UD、DU、DD共4种状态。遇到询问的时候,我们可以直接看如果只有这一段,原点到目标点能不能联通。刚写完了这个,还有1个多小时,我洋洋得意,以为200有希望了(第二题放弃)。突然发现,比如说左上是原点,左上不能直接到左下,却可以在左边绕一大圈到左下,然后左下可以到目标点这种情况。想了半个小时没想出来。后来想到,如果是这样,左上一定在左边的某一个竖着联通的地方与左下联通了,那么只要找出最近的竖着的就好了!用树状数组求和来维护竖着的有几个,然后二分去找最近的竖着的,判断左上左下能不能同时到那个竖着的,可以的话判断左下到目标点能不能联通,都满足那么就输出Y。当然还有右边这样的情况、以及左边右边都这样绕的情况。这些我都考虑好了,自己造出了一个样例,就是左右都要绕的情况,发现不对!此时已经没有时间了!我匆匆调,两三分钟内都没发现问题,老师在催交卷,只好交了。30分(我很不厚道地说句,数据不厚道,说小数据只有3个的朴素能过5个!)后来结束后检查发现,找到那个竖着的东西,再去判那种相交情况的时候,没有考虑左右!因为我的程序里左右是分明的,原先读入的时候有判断,以为子程序会自己处理这样的情况,可事实是没有!改了后80,再检查,发现,后来改的时候打反了一个字母,再改,100!我相信如果考场上我能再多5分钟,就能发现这个弱智的错误,足够细心不引入新的那个错误,这样就能满分了,更是在别人都没有想出正确算法的情况下!生死一行代码,一个小小的疏忽能带来0分的后果,在NOIP2007前我就用这句话来提醒自己,而现在,这个警钟又被敲响!大家不要BS我那写烂掉的程序,中间有2大段30多行能用1行代替的,总大小9K少一点。不过到底还是离AC很近了。我很高兴编译的时候这200多行的程序只有一个常量忘了定义,语言强熟悉程度加强了:)

 

  评论这张
 
阅读(29)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017