第一届蓝桥杯国际赛真题

蓝桥杯大赛国际赛 试题A:仓库布局 时间限制：1秒内存限制：256MB 问题描述 小明管理着一个仓库，他要在仓库里面摆放一些货柜。货柜比较高，不能 上下堆叠，底面是正方形，有一个侧面为正面，用于取放货物。 小明将仓库划分成了n×m的方格，其中南北方向n格，东西方向m格。每 个方格可能放置一个货柜，也可能作为过道。为了使仓库整齐有条理，小明的 货柜的正面都朝南或朝北。具体的，从北向南第一行货柜朝南，第二行全部为 过道，第三行货柜朝北，第四行货柜朝南，第五行全部为过道，第六行货柜朝 北，第七行货柜朝南，第八行全部为过道，依次类推。如果第行为朝南的货 柜，则由于无法取放货柜中的货物，只能将这排货柜撤除，此时第行改为过 道。 小明不仅有东西方向的过道，还有南北方向的过道，他每隔连续的5格都 分出了一个南北方向的过道，即从西向东第6、12、18列都是过道。 依照以上规则，当n=6、m=8时，仓库的摆放图如下： 货柜 货柜 货柜 货柜 货柜 货柜 货 货柜 货柜 货柜 货柜 货柜 货柜 货柜 货柜 货柜 货柜 货柜 货相 货柜 货柜 货相 货柜 货柜 货柜 货柜 货柜 货拒 试题A:仓库布局 1 蓝桥杯大赛国际赛 当n=4、m=8时，仓库的摆放图如下，虚线框中是被撤除的货柜： 货相 货柜 货相 货柜 货柜 货柜 货柜 货柜 货柜 货柜 货相 货柜 货柜 货相 给定n,m,请问按照小明的货柜摆放规则，仓库中可以放置多少个货柜（不 计算被撤除的货柜)。 输入格式 输入一行包含两个整数n,m。 输出格式 输出一个整数，表示可以摆放的货柜数量。 样例输入 68 样例输出 28 评测用例规模与约定 对于30%的评测用例，1≤n≤100,6≤m≤100： 对于70%的评测用例，1≤n≤10000,6≤m≤10000： 对于所有评测用例，1≤n≤10°，6≤m≤10。 试题A:仓库布局 2 蓝桥杯大赛国际赛 试题B:网站扩张 时间限制：1秒内存限制：256MB 问题描述 小明在一个著名的网络公司工作，公司开发了一个新的功能。公司采用邀 请的方式让用户来使用这个功能。 从第1天开始，有一名用户可以使用这个功能。该用户使用一周(7天)后， 可以在第8天邀请一名用户来使用这个功能，之后每隔两天（第11、14、17 ·天)可以邀请一名用户使用。 新被邀请的用户在当天即可开始使用这个功能，使用一周(7天)后可以开 始邀请其他用户，每隔两天可以邀请一名用户。 请问，如果每个用户充分的使用自己的邀请功能，在第天的结束的时候 有多少用户能使用这一新功能。 输入格式 输入一行包含一个整数，表示天数。 输出格式 输出一个整数，表示答案。 样例输入 20 样例输出 9 试题B:网站扩张 3 蓝桥杯大赛国际赛 评测用例规模与约定 对于30%的评测用例，1≤n≤80： 对于60%的评测用例，1≤n≤150： 对于所有评测用例，1≤n≤300： 试题B:网站扩张 4 蓝桥杯大赛国际赛 试题C:基因配对 时间限制：1秒内存限制：256MB 问题描述 生物的基因都是由4种不同的碱基构成，一般用A、T、G、C表示这4种碱 基。碱基之间可以配对构成碱基对，在配对时只能A和T配对，G和C配对。 配对的碱基对按某种顺序连接成螺旋的梯子状，组成了基因。下面给出了 一个基因的示意图。 一般而言，表示一个基因只需要使用一测的碱基序列即可。例如，使 用AGTC来表示一个基因片段时，可知其对应的另一侧的基因片段是TCAG。 现在给了一段较长的基因片段L和一段较短的基因片段S,请问基因片段S 是否能和L中的某一段正好配对。我们说一段基因能和另一段基因配对是指这段 基因中的每个碱基和另一段中对应位置的碱基配对。因碱基具有方向性，因此 在配对的时候不能倒序。 例如，若L=ATCAAATCG,S=TTTAG,则S能和L中的一段正好配对，配 对的段为AAATC,它是从L的第4个位置开始的。 输入格式 输入的第一行包含一个字符串，表示L。 第二行包含一个字符串，表示S。 L和S都只包含A、T、G、C四种字符，S的长度不超过L的长度。 试题C:基因配对 5 蓝桥杯大赛国际赛 输出格式 如果能配对，输出最早的配对的位置。如果不能配对，输出0。 样例输入 ATCAAATCG TTTAG 样例输出 4 评测用例规模与约定 对于70%的评测用例，L和S的长度均不超过1000： 对于所有评测用例，L和S的长度均不超过10。你可能需要使用比较快的 函数才能在时限内完成比较。 试题C:基因配对 6 蓝桥杯大赛国际赛 试题D:捕鱼达人 时间限制：1秒内存限制：256MB 问题描述 小明在玩一个捕鱼的游戏。游戏在一个平面中进行，有条鱼在平面中， 第i条鱼的坐标为(x,y 每个时刻，小明可以选择一条还在平面中的鱼，向这个位置撒一张网，这 条鱼将被捕到网中，同时，与这条鱼距离（欧式距离）不超过R的所有鱼都被 捕到网中。被捕的鱼被小明收走，从平面中消失。请注意，小明只能选择一条 在平面中的鱼（未被收走的）撒网，如果没有鱼，则他不能撒网。 小明想知道，他最少撒几次网能捕到所有的鱼。 提示：两个点(1，y)和(2,2)的欧式距离定义为V-2)尸+1-2)下。 输入格式 输入的第一行包含两个整数，R,表示鱼的条数和网的捕鱼距离。 接下来n行，每行两个整数，表示一条鱼的坐标。 输出格式 输出一行，包含一个整数，表示最少的撒网次数。 样例输入 34 00 23 -5-3 试题D:捕鱼达人 7 蓝桥杯大赛国际赛 样例输出 评测用例规模与约定 对于20%的评测用例，1≤n≤8： 对于40%的评测用例，1≤n≤12： 对于60%的评测用例，1≤n≤25： 对于剩下40%的评测用例，1≤n≤50，鱼的位置使用随机函数生成，在平 面呈均匀分布： 对于所有评测用例，xH,≤1000，R≤2000. 试题D:捕鱼达人 8 蓝桥杯大赛国际赛 试题E:希尔伯特曲线 时间限制：1秒内存限制：256MB 问题描述 希尔伯特曲线是一条递归定义的曲线，n阶希尔伯特曲线定义在一个2”×2” 的方格内。其中一阶曲线如下： 二阶曲线如下： 三阶曲线如下： 阶希尔伯特曲线可以看成是从左下角出发，经过了所有的方格后再从右 下角结束的曲线。 试题E:希尔伯特曲线 9 蓝桥杯大赛国际赛 我们规定左下角方格的坐标为(0,0)，右下角方格的坐标为(2”-1,0)，则可 以依次写出曲线经过的方格的坐标。 例如一阶希尔伯特曲线依次经过的方格为：(0,0)，(0,1)，(1,1)，(1,0)。二阶希 尔伯特曲线依次经过的方格为：(0,0)，(1,0)，(1,1).(0,1)，(0,2)，(0,3)，(1,3)，(1,2)， (2.2).(2.3).(3.3).(3,2).(3.1)(2.1)(2.0),(3,0) 给定n,P,请问n阶希尔伯特曲线经过的第p个点的坐标是多少。 输入格式 输入一行包含两个整数n,p。 输出格式 输出一行包含两个整数，用一个空格分隔，表示所求的坐标。 样例输入 25 样例输出 02 评测用例规模与约定 对于30%的评测用例，1≤n≤10,1≤p≤10： 对于50%的评测用例，1≤n≤30,1≤p≤10： 对于所有评测用例，1≤n≤100,1≤p≤108。 试题E:希尔伯特曲线 10