搜索
合肥一中汪义超2012年1月17日【题目大意】乘坐出租车，收费标准为2.5公里以内起步价6元，超过2.5公里之后按1.2元/公里计价，超过10公里之后在1.2元/公里的基础上加价50%，另外，停车等候时间则按时间计费后加入总价：1元/5分（注：不满5分钟不计费）【要求】打车需要费用【输入】两个整数N，M，分别表示出租车行驶的里程和中间停车的时间，中间以空格分开，0≤N≤200，0≤M≤60【输出】包含一个整数，表示小W应付的乘车费用，四舍五入到整元。本题没有什么算法而言，关键是能读懂题意，根据题目要求编写程序即可。【考察点】送分题，程序设计基本技能，数据类型的理解和常用函数的使用【注意】当N、M都为0时的特殊情况处理。【题目大意】在一面2米高、N米长的围墙上贴瓷砖，瓷砖规格为2米乘1米，瓷砖可以横贴，也可以竖贴【要求】有多少种贴法【输入】长度N【输出】贴法数【数据规模】对于20%的数据，2N90；对于60%的数据，2N≤1200；对于100%的数据，2N10000。我们先画一面N米长的围墙（当然不能太大），如长度为1、2、3、4、5等。墙高2，瓷砖是（1X2）的，故瓷砖只有两种放法：横放或竖放，如当N=2时，有下面两种贴法：由此方法可以列举找出，N=1时：仅1种N=2时：仅2种N=3时：仅3种N=4时：仅5种N=5时：仅8种N=6时：仅13种由前面几项，可以推出，这题实际上是求菲波拉契数列中以1为首项的第N项。解本题的关键问题已分析出来了，同学们基本上可以用3分钟时间把本题的解出来。但根据题目给出的数据范围，当N91时，数据类型定义为int64，都无法承受菲波拉契数列的庞大数据。故只能采用高精度存贮了。所谓高精度，即把K进制数的1位或K位分开，存于数组中。如：768198574，在数组中存贮样例1：元素下标123456789值475891867那么高精度的加法，直接模拟我们笔算时的方法就行了，注意进位。如：A+B=345+917,结果存于B中：A的元素下标123B的元素下标1234值543值7190c=a[1]+b[1]=5+7=12进位1，本当前位应是2b[1]：=cmod10=2当前位b[1+1]=b[2]=b[2]+cdiv10=1进位通过这种方式，本题能得到70分，原因是：虽然用数组不用担心数据溢出，但对于庞大的数据来说，效率并不高。因为，对于计算来说，一位数的加法，和8位数的加法时间上几乎相同，所以我们完全可以把数组定义为longint,每个元素存8位十进制数，这样速度又将提高8倍。如：712385746819样例2元素下标123456789值8574681971230000000我们称这种存贮方法为压缩的高精度，前一种方法每一位是缝10进位，而这种方法是缝10000,0000进位，计算方法和前面的相同。【题目大意】一个迷宫有N层楼，每层楼都可以停靠电梯，电梯内四个按钮：开、关、上、下，每层内有一个数字表明可以上、下的层数，如不能满足要求，则相应按钮就会失灵。进入迷宫中的人都想尽可能少地按电梯到达目的地给你出发楼层A和目的楼层B，请你求出从A层到B层至少要按几次按钮。【输入文件】输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200,1≤A,B≤N)，第二行为N个用空格隔开的正整数，表示Ki。【输出文件】输出文件仅一行，即最少按键次数,若无法到达，则输出-1。本题很明显是一道宽搜题宽搜的特点：离根节点最近的节点先扩展，所以广度优先搜索法比较适合求步数最少解的问题。确定搜索的几个关键因素：状态：电梯目前到达的层数目标：电梯到达目的楼层边界条件：◦1.搜索完所有节点，没有到达目的楼层◦2.到达目的楼层搜索范围：在每层楼中根据相应电梯中的数字能够到达的楼层（当然要符合题目条件）【题目大意】N支球队参加足球比赛，只能比k场每个队最多参加2场，最少参加0场每个球队有一个等级数，比赛中等级高的客场，等级低的主场，每个球队最多只能做1次主场、1次客场为了增加观赏度，要求尽可能安排k场球队水平差异小的比赛【输入文件】第一行两个正整数N，K。接下来有N行，第i行表示第i支球队的等级。【输出文件】最小的等级差的总和。【数据范围】对于20%的数据，1≤N≤300对于80%的数据，1≤N≤5000对于100%的数据，1≤N≤10000保证所有输入数据中等级的值小于32000，1≤K≤N-1根据题目可以推出每场比赛一定在两个等级相邻的选手之间进行，所以先把N个选手的等级从小到大排序，再把N-1个相邻的差距按照从小到大排序，前K个值的和就是答案。在想到了上述方法后，本题得分关键在于如何实现排序，比较常用的有：法一：冒泡排序，时间复杂度O(N*N),期望得分80；法二：快速排序，时间复杂度为O(N*lgN),期望得分100.