NOIP2015提高组复赛试题Day2
- 格式:docx
- 大小:26.63 KB
- 文档页数:9
noip2015普及组复赛试题题目一:矩阵运算给定一个n阶方阵A(1 ≤ n ≤ 100),求A的所有指定行指定列删除后得到的新矩阵的行列式。
输入格式:输入第一行包含一个整数n,表示方阵的阶数。
接下来n行,每行包含n个整数,表示方阵A的元素。
接下来一行包含两个整数,表示要删除的行和列的序号。
输出格式:输出一个整数,表示新矩阵的行列式的值。
题目要求:首先,我们需要编写一个能够计算矩阵行列式的函数,然后根据题意进行修改,使其能够处理删除指定行列后的新矩阵,并返回新矩阵的行列式的值。
算法思路:我们可以使用拉普拉斯展开定理来计算矩阵行列式的值。
首先定义一个变量result,初始化为0。
然后遍历矩阵的第一行元素,对于第i 个元素,根据其正负性,计算其余元素组成的(n-1)阶子矩阵的行列式的值,并递归调用自身。
最后将每个元素计算得到的行列式值乘以其对应的元素,累加到result上。
然后根据题目要求,在计算每个元素对应的子矩阵时,判断是否需要删除指定的行列。
如果需要删除,则直接跳过该行列,否则继续计算。
代码如下:```pythondef determinant(matrix):n = len(matrix)if n == 1:return matrix[0][0]result = 0for i in range(n):if n > 2:sub_matrix = [row[:i] + row[i+1:] for row in matrix[1:]]else:sub_matrix = matrix[1:]det = determinant(sub_matrix)result += (-1) ** i * matrix[0][i] * detreturn resultn = int(input())matrix = []for _ in range(n):row = list(map(int, input().split()))matrix.append(row)row, col = map(int, input().split())matrix = [matrix[i][:col] + matrix[i][col+1:] for i in range(row)] # 删除指定列matrix = matrix[:row] + matrix[row+1:] # 删除指定行result = determinant(matrix)print(result)```题目二:水果分配小明和他的朋友们买了n个水果,其中有x个苹果和y个香蕉。
NOIP2015提高组day1第二题解题报告NOIP2015提高组复赛Day1第二题解题报告By 某蒟蒻zrw1.题目大概描述(因为写的时候题目还没放出来)几个小盆友们在传递自己的信息(生日),并且每个小盆友只会把自己知道的信息传给唯一的一个人【但是自己可以收到很多信息,并会在收到信息的下一轮把这些信息传给那个唯一的人】(单相思233333),问多少轮后自己会收到自己一开始传递出去的自己的信息。
输入:第一行一个整数n,表示有n个人接下来n行,每行一个数j,设这是除第一行外的第i行,那么j 表示第i个人只会把信息传给第j个人。
输出:一个整数,表示最少几轮后自己的信息会回到自己手中。
样例输入:52 4 23 1样例输出:3数据规模:100% n<=200000 60% n<=2500 30% 记不住了……2.大概需要什么样的算法根据数据规模,我们可以大概判断需要多少效率的算法,甚至有的时候可以猜出这题用的是什么算法。
对于本题来说,60%大概就是O(n^2)的算法了,一般是裸的暴力回溯或者是暴力广搜,也有用floyd的(我是从NOIP吧上看到的)。
如果要AC的话,算法效率至少要在O(nlogn)以下(log在这里是以2为底不是以10为底)。
然而,本题是有O(n)算法的,下面会讲。
3.我们还是画个图吧(图可能比较难看,但能看就行)画画图,就会知道这是在做一件什么事情了。
以样例数据为例:我们很容易发现,2,3,4,形成了一个环,而1和5,并没有什么卵用……所以在环234中,由于每一轮可以把在上一轮知道的信息传给唯一的下一个人,在234环中,就需要3轮,信息才能传到多画几个图(由于本人很懒,就只画一张特殊情况比较多的小图):(有木有一种贵圈真乱的感觉)我们可以看出来,1,5,6,成了一个环,而2,3,4,8,也成了一个环,7,9,是来打酱油的。
那么对于这两个环来说,因为每一轮可以传递上一轮信息给下一个人,所以显然是1,5,6这个环比较早传完,3轮。
CCF 全国信息学奥林匹克联赛(NOIP2015)复赛提高组day2(请选手务必仔细阅读本页内容)一.题目概况二.提交源程序文件名三.编译命令(不包含任何优化开关)注意事项:1、文件名(程序名和输入输出文件名)必须使用英文小写。
2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。
3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) II x2 240 processor,2.8GHz,内存 4G,上述时限以此配置为准。
4、只提供 Linux 格式附加样例文件。
5、特别提醒:评测在当前最新公布的 NOI Linux 下进行,各语言的编译器版本以其为准。
1.跳石头(stone.cpp/c/pas)【问题描述】一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。
组委会已经选择好了两块岩石作为比赛起点和终点。
在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。
在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。
由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。
【输入格式】输入文件名为 stone.in。
输入文件第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。
接下来 N 行,每行一个整数,第 i 行的整数 Di(0 < Di < L)表示第 i 块岩石与起点的距离。
这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。
【输出格式】输出文件名为 stone.out。
输出文件只包含一个整数,即最短跳跃距离的最大值。
【输入输出样例 1 说明】将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。
CCF 全国信息学奥林匹克联赛(NOIP2015)复赛普及组(请选手务必仔细阅读本页内容)一.题目概况二.提交源程序文件名三.编译命令(不包含任何优化开关)注意事项:1、文件名(程序名和输入输出文件名)必须使用英文小写。
2、C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。
3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) II x2 240 processor,,内存4G,上述时限以此配置为准。
4、只提供Linux 格式附加样例文件。
5、特别提醒:评测在当前最新公布的NOI Linux 下进行,各语言的编译器版本以其为准。
1. 金币c/pas)国王将金币作为工资,发放给忠诚的骑士。
第一天,骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到三枚金币;之后四天(第七、八、九、十天),每天收到四枚金币……;这种工资发放模式会一直这样延续下去:当连续N 天每天收到N 枚金币后,骑士会在之后的连续N+1 天里,每天收到N+1 枚金币。
请计算在前K 天里,骑士一共获得了多少金币。
【输入格式】输入文件名为。
输入文件只有1 行,包含一个正整数K,表示发放金币的天数。
【输出格式】输出文件名为。
输出文件只有1 行,包含一个正整数,即骑士收到的金币数。
【输入输出样例1】【输入输出样例1 说明】骑士第一天收到一枚金币;第二天和第三天,每天收到两枚金币;第四、五、六天,每天收到三枚金币。
因此一共收到1+2+2+3+3+3=14 枚金币。
【输入输出样例2】【数据说明】对于100%的数据,1 ≤ K ≤ 10,000。
2.扫雷游戏(c/pas)扫雷游戏是一款十分经典的单机小游戏。
在n 行m 列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。
玩家翻开一个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。
CCF 全国信息学奥林匹克联赛(NOIP2015)复赛普及组(请选手务必仔细阅读本页内容)一.题目概况二.提交源程序文件名三.编译命令(不包含任何优化开关)【问题描述】注意事项:1、文件名(程序名和输入输出文件名)必须使用英文小写。
2、C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。
3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) II x2 240 processor,2.8GHz,内存4G,上述时限以此配置为准。
4、只提供Linux 格式附加样例文件。
5、特别提醒:评测在当前最新公布的NOI Linux 下进行,各语言的编译器版本以其为准。
1. 金币(coin.cpp/c/pas)国王将金币作为工资,发放给忠诚的骑士。
第一天,骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到三枚金币;之后四天(第七、八、九、十天),每天收到四枚金币……;这种工资发放模式会一直这样延续下去:当连续N 天每天收到N 枚金币后,骑士会在之后的连续N+1 天里,每天收到N+1 枚金币。
请计算在前K 天里,骑士一共获得了多少金币。
【输入格式】输入文件名为coin.in。
输入文件只有1 行,包含一个正整数K,表示发放金币的天数。
【输出格式】输出文件名为coin.out。
输出文件只有1 行,包含一个正整数,即骑士收到的金币数。
【输入输出样例1】【问题描述】【输入输出样例1 说明】骑士第一天收到一枚金币;第二天和第三天,每天收到两枚金币;第四、五、六天,每天收到三枚金币。
因此一共收到1+2+2+3+3+3=14 枚金币。
【输入输出样例2】【数据说明】对于100%的数据,1 ≤ K ≤ 10,000。
2.扫雷游戏(mine.cpp/c/pas)扫雷游戏是一款十分经典的单机小游戏。
在n 行m 列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。
CCF 全国信息学奥林匹克联赛(NOIP2015)复赛普及组(请选手务必仔细阅读本页内容)一.题目概况二.提交源程序文件名三.编译命令(不包含任何优化开关)注意事项:1、文件名(程序名和输入输出文件名)必须使用英文小写。
2、C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。
3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) II x2 240 processor,,内存4G,上述时限以此配置为准。
4、只提供Linux 格式附加样例文件。
5、特别提醒:评测在当前最新公布的NOI Linux 下进行,各语言的编译器版本以其为准。
1. 金币c/pas)国王将金币作为工资,发放给忠诚的骑士。
第一天,骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到三枚金币;之后四天(第七、八、九、十天),每天收到四枚金币……;这种工资发放模式会一直这样延续下去:当连续N 天每天收到N 枚金币后,骑士会在之后的连续N+1 天里,每天收到N+1 枚金币。
请计算在前K 天里,骑士一共获得了多少金币。
【输入格式】输入文件名为。
输入文件只有1 行,包含一个正整数K,表示发放金币的天数。
【输出格式】输出文件名为。
输出文件只有1 行,包含一个正整数,即骑士收到的金币数。
【输入输出样例1】【输入输出样例1 说明】骑士第一天收到一枚金币;第二天和第三天,每天收到两枚金币;第四、五、六天,每天收到三枚金币。
因此一共收到1+2+2+3+3+3=14 枚金币。
【输入输出样例2】【数据说明】对于100%的数据,1 ≤ K ≤ 10,000。
2.扫雷游戏(c/pas)扫雷游戏是一款十分经典的单机小游戏。
在n 行m 列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。
玩家翻开一个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。
姓名省份编号总分magic message landlordsstone substring 李绍铭广东GD-000110000100邓宇广东GD-0002160100030300覃思文广东GD-0003140100300100罗卓枫广东GD-0004330100100301000杨宇通广东GD-00053101001000700邓浩然广东GD-00064051001001010070陈卓彬广东GD-000712010000200潘熙广东GD-0008495100100659090苏泽盛广东GD-0009335100100010010肖遥广东GD-001045010010045100100麦辉煜广东GD-0011160100003030黄昱珲广东GD-001228510010025100林元芃广东GD-0013325100100201080龙辰纲广东GD-0014375100100355030薛靖云广东GD-00153551001001002010黄若岚广东GD-001630510010051000钟子健广东GD-001727010060402030刘家晖广东GD-0018320100100305010何盛哲广东GD-0019280100700900黄洋逸广东GD-00204151001003510050刘政泽广东GD-00212751001000100邓明昱广东GD-0022430100100802050张呈昊广东GD-002330510010001000林颖虞广东GD-0024330100303010030林荻肯广东GD-00251951003035300冒泓希广东GD-002627010010010600于子云广东GD-0027340100100308010曾明亮广东GD-002854510010085100100周魏广东GD-0029000000段政广东GD-0030340100100302090刘恩云广东GD-0031000000张耀文广东GD-0032130100100200麦昌楷广东GD-0033210100803000黄煜林广东GD-00341901004002030李东豪广东GD-003511010000100黄峻翔广东GD-0036200100900100王晓庆广东GD-0037310100100304040梁一帆广东GD-0038370100100406010胡家铭广东GD-0039706000100陈扬广东GD-00402401007020500白昊天广东GD-00411851003030100曾昕怡广东GD-004210000100陈文丰广东GD-00432201007002010黄涛广东GD-00442251001000200臧艾嘉广东GD-004513010030000刘奕烽广东GD-0046000000孙吴歌广东GD-004718010080000陈圣龙广东GD-0048130100100200钟惠兴广东GD-00494651001001001000刘俊杰广东GD-0050360100100304090高嘉煊广东GD-005151510010095100100李子豪广东GD-0052595100100100100100蔡子逸广东GD-0053330100100301000王诚科广东GD-005453510010065100100龙耀为广东GD-0055595100100100100100郑亮涛广东GD-00564051001001010080吴董超广东GD-00572701001000600李珲广东GD-005830510010000100古智锋广东GD-005933010010020900谢典霖广东GD-00603051007001000刘乙丁广东GD-0061275100100303010张重广东GD-006226510010002010傅畅广东GD-00634951001009510070何泓豪广东GD-006430510010030500王之栋广东GD-00655151001005510080温标林广东GD-00662101008020100郑林楷广东GD-0067595100100100100100张凯杰广东GD-006833010010080500刘梓灏广东GD-0069150100002010黄兆鋆广东GD-0070380100100301000邬昶宽广东GD-007132010010001000郑锟浩广东GD-007220000200蔡承泽广东GD-0073400100100510070黄岳嘉广东GD-0074345100100302090沈晓腾广东GD-0075405100100600100邱铭浩广东GD-0076225100700500李卓明广东GD-00772801008003040吴晓杰广东GD-007831010010030600文泓鑫广东GD-0079290100100303030陈润健广东GD-008029510010020200张逸勋广东GD-00812001007010200曾博宇广东GD-008211510000100叶大源广东GD-00832701001000600蔡逸熙广东GD-0084305100100252030蔡育铮广东GD-008523510080252010冼家进广东GD-00862101007020200樊志睿广东GD-008758510010010010090颜杰龙广东GD-0088390100100303050熊俊博广东GD-00892001007002010陈嘉杰广东GD-00903451001000900刘英豪广东GD-009112010020000肖言广东GD-00921205070000袁梓铭广东GD-0093375100100751000樊思明广东GD-00942401008030200郑燊广东GD-00952151008010200董炜隽广东GD-009656010010080100100邹诗环广东GD-009727510010020020刘喆广东GD-009832510010001000李润翡广东GD-0099190100700200蔡明轩广东GD-0100190100800100庞智健广东GD-010113010000300李超朗广东GD-01022051006030010张思敏广东GD-01032351000301000邓一凡广东GD-0104170100500200曾梓峰广东GD-01052201008025100关东阳广东GD-01062801008030300黄文健广东GD-010717010070000杨明杰广东GD-010841010080759050李奕广东GD-0109145100300100王涵广东GD-0110200100100马秋同广东GD-0111000000谭博仁广东GD-0112350100100701070陈少峰广东GD-011312010000200陆晓东广东GD-0114000000刘旭辉广东GD-011525010080202030张林轩广东GD-011630010010020400何家昊广东GD-0117190100800100陈广源广东GD-011811010000100陆李阳广东GD-01191001000000谢油添广东GD-0120000000钱晓波广东GD-0121000000林学勤广东GD-012210000100曾德科广东GD-01232201007030200简燚广东GD-012413010030000陈志恒广东GD-01251801004030100苏志生广东GD-0126150100300200李俊广东GD-0127140100300100周子峻广东GD-0128150100400100钟文彬广东GD-012913010000300李享运广东GD-01302301008030200孙耀威广东GD-0131800700100陈劲豪广东GD-0132195100700200游江川广东GD-0133150100200300张晓鸿广东GD-0134200100100杨沛霖广东GD-01353550100010090罗平镔广东GD-0136240100100102010肖亚语广东GD-01374451001005010060陈丹阳广东GD-013817010070000姚楚名广东GD-0139180100600200刘子桥广东GD-014030510010080100霍志鸿广东GD-014129510070010010周紫轩广东GD-014259010010095100100杨启欣广东GD-01434051001003010030朱俊杰广东GD-01442501009005010吴鸿铭广东GD-014517010030102010冼昊明广东GD-01463751001003010040吕耀维广东GD-014731010070603010李政峰广东GD-014812010000200欧润民广东GD-0149155100400100钟志聪广东GD-015011080100200黄宇胜广东GD-0151201000100林铉昊广东GD-015213510030000李轩广东GD-015311010000100卢健杰广东GD-015437510010055500蔡亿淇广东GD-015527510010020300郑理尤广东GD-015622010010305030吴远航广东GD-01571901003003030尹浩朗广东GD-015828010010005010李海涛广东GD-015926010080302010吴宗培广东GD-016028010010030100何子睿广东GD-016123010070302010林雪晴广东GD-01622301001000030刘海鹏广东GD-0163240100800600袁智杰广东GD-0164800700010邓志聪广东GD-01654201001001005070谢文拯广东GD-016632510070301000邱煜炜广东GD-0167195100800100黄康恩广东GD-01682101008002010黄梦轩广东GD-0169000000王柳君广东GD-01702101007003010郑博文广东GD-0171410100100751000许博维广东GD-01723151001000600马再霖广东GD-0173205100603000梁敬聪广东GD-01742301003040200吴宇恒广东GD-0175210100900200张质源广东GD-01762201007030200封清广东GD-017728010080205030何昊林广东GD-0178180100600200李昊广东GD-01792301007025100鲍政衡广东GD-0180360100803010030杨明炜广东GD-01815201001009510070霍子钊广东GD-018211010000100何大为广东GD-0183000000吴天扬广东GD-01842051007010100谭健翔广东GD-018525010070303020李汉文广东GD-0186000000王奕涵广东GD-0187150100004010詹方榕广东GD-01882301001003000张学斌广东GD-018910000100许海杰广东GD-019020000200张君临广东GD-0191000000邝俊炜广东GD-0192000000王怀颉广东GD-01934701001006010070胡誉天广东GD-01942501008030400苏凯广东GD-01952151007003010李皓玮广东GD-0196000000朱国方广东GD-0197000000钱途广东GD-01982101008002010李泓德广东GD-01992501009030100陈钰彬广东GD-02002501001000500詹鸿宇广东GD-020*******彭宇轩广东GD-0202135100100200张海庭广东GD-02032501001000500黄杰广东GD-020480030301010刘瀚之广东GD-02055401007095100100刘嘉辉广东GD-0206325100100351060曾煜文广东GD-02072301008002030黄健杰广东GD-020831010080307010尹嘉豪广东GD-020*********陈立珅广东GD-02101001000000詹昌凌广东GD-021130010090010010李达一广东GD-0212160100400200张业鸿广东GD-021325510010030200李逸广东GD-02141904010002030刘明旸广东GD-02152301008004010陈颖贤广东GD-021612501000200邓尚源广东GD-0217210100800300杜志聪广东GD-021825510010030200田胤广东GD-021922010010010010黎俊乐广东GD-0220330100100301000张沛博广东GD-02212901008009020邓翔玮广东GD-02223001001000800陈致远广东GD-022332010010030900王青杨广东GD-022431010080309010王晓阳广东GD-02252251008030100赵铭华广东GD-022627510010065100林洋洲广东GD-0227360100100303080刘浩钊广东GD-0228900003060范城豪广东GD-0229210100800200杨栩正广东GD-0230150100002030陈诗敏广东GD-023125010080303010任锐平广东GD-02321651000253010谭天尧广东GD-02332251008002010欧阳龙文广东GD-0234135100200100邱昊中广东GD-02352501001000200任建彬广东GD-02361851000303010王昊旻广东GD-0237145100100200吴伟为广东GD-0238120100100100刘昱志广东GD-0239180100700100刘佳荣广东GD-02403851001003550100陈泰霖广东GD-0241330100100251000陈子陵广东GD-02425451001007510090杨宗霖广东GD-024*******李文迪广东GD-024424010070303010杨耀良广东GD-024530510040309030林仕居广东GD-02464251001004510050陈泰安广东GD-02472001007002010董昭锐广东GD-024822510070301010梁景涛广东GD-0249500100100100100100邱逸铭广东GD-025025010010030200陈雨硕广东GD-025147010010030100100陈冠宏广东GD-02522501001000300林锟广东GD-025311010010000刘智杰广东GD-025425510010030100蔡俊峰广东GD-0255135100025010蔡卓颖广东GD-02561601001030200翁溥珩广东GD-0257330100100010030林根仕广东GD-025811560200200胡祖俊广东GD-025927510001002010杨一凡广东GD-026023510070253010郑重广东GD-0261300100100303040卢致一广东GD-026214010005300郭铭健广东GD-026320010020302010孙宇鹏广东GD-02643401001003010010陈思炀广东GD-02652301008030200尹浩文广东GD-02662351008030200郑朝权广东GD-0267450300010范胜旭广东GD-026828010010002030周柱森广东GD-026919510030302010陈泳良广东GD-02701501003001010邓振华广东GD-027112090100200陈子豪广东GD-027218010030202010湛炜睿广东GD-027312010000200邓靖岚广东GD-02741701002030200杨佳星广东GD-027511010000100李洁彤广东GD-02761051000000刘韫琦广东GD-027712010000200张滨凯广东GD-027813510000200朱迪广东GD-0279220100800400常春广东GD-0280445100100953070谭泳茵广东GD-02812901001000900林涛广东GD-02824901001004010090陈隽文广东GD-028332010010030900黄铮弘广东GD-028*******肖行文广东GD-0285135100100200杨振炜广东GD-028630010010040600卫家熙广东GD-028732010090303070尹靖凯广东GD-0288200100100000李征辉广东GD-0289390100100100900尹颂涛广东GD-029013007030300罗烨晖广东GD-02911751004025010周楷文广东GD-02922451008002040邹卓广东GD-02931401001010200万家旭广东GD-029432010010001000伍华明广东GD-0295330100802010030梁永岚广东GD-029615560700200杨海钰广东GD-0297145100300100陈颖雄广东GD-029822010030301010黄赞高广东GD-02992151007030100文盛广东GD-0300120100100100梁烨荣广东GD-030125510010025100刘毅伦广东GD-03021001000000江昊翰广东GD-030319010010302020潘高高广东GD-0304190100800100邹银涛广东GD-0305190100800100徐可广东GD-0306251005100李嘉羲广东GD-030711090100100刘子恺广东GD-03081350008010陆骏铭广东GD-0309280100100205010唐宇翔广东GD-0310200001010范俭豪广东GD-031155510010095100100龚尚越广东GD-0312290100100305010郑子和广东GD-031330010070301000曹天佑广东GD-0314400100100010070谢国富广东GD-03153451001002510010王彦恒广东GD-03162151006025100许晓彤广东GD-03172051001007010高名哲广东GD-0318370100030100100翁一平广东GD-03192101007030100陈俊熹广东GD-032029010010030600黄文皓广东GD-03214151001007010040郑言广东GD-032231010080301000刘宇轩广东GD-03235251001009510070张瑞霖广东GD-032423010080301010徐振戈广东GD-03252651001000600于凡奇广东GD-0326210100800300邓兆昂广东GD-0327140100300100曾子灏广东GD-03282301001003000黄杨峻广东GD-03291104030102010李琳琳广东GD-0330000000栾昊广东GD-03311200030900杨家权广东GD-033212010000200徐志峰广东GD-033311010000100汪云鹏广东GD-033420000200冯承锐广东GD-0335130100100200卢俊浩广东GD-0336130100100200张俊逸广东GD-0337425100100351000杜子睿广东GD-0338000000邱衍衔广东GD-033923010070252010张文略广东GD-03402351007030300周学斌广东GD-03412101001000100覃涵广东GD-0342200100800200罗梓璋广东GD-034351010010010010090吴限广东GD-03442301008030200朱家信广东GD-034554010010090100100何少渝广东GD-0346365100100100600赵刘洋广东GD-034713010000300黄俊豪广东GD-03482451007025500邓子烽广东GD-03494151001003010030梁文杰广东GD-03503951001003510040谭胜文广东GD-0351465100100859070郭春希广东GD-03522401009030200郑浩文广东GD-035325510010001040黄晓斌广东GD-03543951001008010010邓茵琳广东GD-0355595100100100100100陈代超广东GD-035656010010095100100叶荣臻广东GD-0357415100100656090肖云龙广东GD-0358360100100301000关港宁广东GD-0359320100100305020李睿广东GD-0360180100700100张展邦广东GD-03612301008030200郑嘉铭广东GD-0362320100100603010麦景广东GD-036358010010085100100王浩宇广东GD-0364345100100010040李源隆广东GD-036540010070510090招俊锋广东GD-03663851001003010050黄韵澄广东GD-036730010080305030凌浩广东GD-03685501001006010090欧阳文彬广东GD-03694201007010010010杨嘉宏广东GD-03705451001006510090黄天广东GD-03714801001001001000关雅雯广东GD-03722751001000600欧幸绮广东GD-0373330100100301000董佳昕广东GD-037425510010030200罗慧诗广东GD-0375190100800010李奥广东GD-037656510010010010070黄孟华广东GD-037726010010003030赵忠源广东GD-037825010010030200徐晴洋广东GD-0379210100900200范祥烨广东GD-0380270100100303010白扬广东GD-03812001000304030杨健怡广东GD-038222010030303030邝启鹏广东GD-03833701001003010020李欣霖广东GD-0384210100803000谭家骏广东GD-038522510070153010吴梓华广东GD-03861701001001030郭芃广东GD-03871801003002030欧阳伟强广东GD-03881701004010200吴国璋广东GD-038919010020202010招梓枫广东GD-0390140100020200尹浩贤广东GD-03912201008003010冯文聪广东GD-0392********胡奕晖广东GD-039319090005030刘淼森广东GD-0394130100002010蒋泽林广东GD-03951001000000吕润和广东GD-039632510010005050莫书琪广东GD-0397120100100100周昊广东GD-0398000000陈漫璟广东GD-0399280100100303010李昌栋广东GD-04004501003030100100何灏楠广东GD-040112010000200张震铄广东GD-04022551009020300何继奥广东GD-040334010010005090张庄衢广东GD-040430010070301000陈子豪广东GD-040511010000100邱俊斌广东GD-0406305100100306010汪泽雨广东GD-0407285100100303010郑昕垚广东GD-0408000000罗朝权广东GD-0409120100100100刘雅欣广东GD-04102101001001000黄冰鉴广东GD-04112051000205030何铭烨广东GD-041214090400100彭清桦广东GD-0413265100700900应卓凡广东GD-041422510070251010庄啸森广东GD-0415301000200区曦文广东GD-0416500000李振广东GD-04171451001002010吴茼广东GD-041830010010030700谭嘉伟广东GD-04194251001003510090杨汉全广东GD-0420155100030200陈扬广东GD-04212501001000500谢伟聪广东GD-042218010020302010彭思源广东GD-04231001000000钟梓正广东GD-0424160100300300陈斯昂广东GD-04252601001005200陈昊东广东GD-04261001000000张明达广东GD-042729010010030600刘振宇广东GD-0428335100100010010赵嘉辉广东GD-04294951001000100100陈嘉礼广东GD-0430445100100851000李彬广东GD-0431330100100402040林文斌广东GD-0432350100803010010陈禹诚广东GD-043336510010040900陈泽政广东GD-0434395100100259030邓伟信广东GD-04354801001004510090李东恒广东GD-0436405100100655070梁子辉广东GD-04374251001003010090王宇轩广东GD-0438350100100253090卢紫垣广东GD-04393201008030900翁文涛广东GD-0440595100100100100100吴遥广东GD-0441305100100305020黄舒炜广东GD-04423851001003050100龙跃鹏广东GD-0443385100100451000刘远哲广东GD-044427510010002030郑然广东GD-04452101008002010陈健勋广东GD-04462451008030300黄莹广东GD-044714010040000卢瑞琛广东GD-044812020800200付佳伟广东GD-04492201001000200王瀚森广东GD-0450320100100302070蔡俊亮广东GD-04513601001002510030冯子健广东GD-04522251007025300黎明奔广东GD-0453110106020200尤宇航广东GD-0454190100700200陈载宇广东GD-04552301008002030何伟麟广东GD-0456135100002010钟历炜广东GD-04571001000000谢立辉广东GD-0458310100100751010凌尉铭广东GD-0459200001010谢佳乐广东GD-0460225100800300苏伟轩广东GD-04614701001003010090潘宏曙广东GD-0462295100100303030胡智炜广东GD-0463325100100259010邱灏广东GD-046412010000200梁家铭广东GD-0465365100100306040张紫闻广东GD-04661851004025200罗永茂广东GD-046712010000200梁济凡广东GD-04684201001004010050曾比扬广东GD-0469455100100608090黄文杰广东GD-047011010000100刘泳麟广东GD-0471120100100010成家轩广东GD-0472000000古雨广东GD-0473130100010200杨乐广东GD-047455510010010010090周铭洵广东GD-0475585100100100100100莫培钊广东GD-047628010080303040梁哲铭广东GD-0477295100100252010罗智康广东GD-0478330100100301070利俊安广东GD-04791501003010100梁正昊广东GD-04805201001006010080凌子轩广东GD-048157010010010010090杨家齐广东GD-0482510100100100100100刘祖壤广东GD-048336010010001000黄鑫豪广东GD-048433010080010030刘志涛广东GD-04851109000200张睿风广东GD-048619590703000曾立帆广东GD-048710000100梁光飞广东GD-0488225100800200罗浩宇广东GD-048912010000200郑钧天广东GD-0490400100100602060郑杰恒广东GD-049126010010030300廖崇灿广东GD-0492150100400100郭睿广东GD-04932401008030300谭富灏广东GD-049422510010010100余嘉鸿广东GD-0495360100100510030黄镇广东GD-0496475100100509090刘伟明广东GD-0497330100100301000钟子玠广东GD-049818510070000吴非杰广东GD-049911510000010邓发珩广东GD-050013010000300龙灏天广东GD-0501200100900010高肖帆广东GD-0502155900152030庄博尔广东GD-05034951001001001000林国梁广东GD-0504130100100200黄俊力广东GD-050526010070203040叶钰倩广东GD-0506000000谢国超广东GD-05072301007030100邹丹梅广东GD-050811010000100魏承东广东GD-050946510010065100100李家昊广东GD-051022510080251010蔡启杨广东GD-0511801070000朱恩涛广东GD-05121001000000查竣然广东GD-05131601003020100蔡张风和广东GD-051490030201030郭佳胜广东GD-05153601001001002040黄河广东GD-0516000000金鹏翔广东GD-0517300001010梁家广东GD-0518000000叶学通广东GD-0519120100100100林键彬广东GD-052014010000200梁汐然广东GD-0521460100100801000刘予希广东GD-05225401001005510090谢思远广东GD-0523201010000徐广俊广东GD-052415010000500李奇广东GD-0525000000何泽宇广东GD-052640000400何广荣广东GD-05273701001002510010朱宇旋广东GD-052820000200方舟广东GD-0529900700200谭天广东GD-05301001000000张志宏广东GD-05312201006002040吴浩贤广东GD-0532505100100100100100蓝源泓广东GD-053326510040305030刘晓枫广东GD-053426010010002020琚锡廷广东GD-05355051001007010090陈梓峰广东GD-0536310100801010010黎泽锋广东GD-05379010700100周庭辉广东GD-0538130100100200王昱程广东GD-05392201007020300胡壮飞广东GD-05402551001000500陈晓炀广东GD-054113060300400陈健柏广东GD-054225010080201040石昊海广东GD-054313010030000石昊洋广东GD-05441601000203010黄莫尧广东GD-054517010070000陈靖邦广东GD-0546330100100101000肖起凡广东GD-054723500010090廖俊豪广东GD-0548530100100100100100郑镇航广东GD-054954510010095100100练泓睿广东GD-05502201008030100transport4025502555015602520302030658054020606015205652010 5 20 35 5 35 30 25 80 0 95 0 20 50 20 0 25 5 45 5 30 20 0 55 0 5 10 30 0 0 95 80 0 55 0 0 0 10 5 80 35 25 0 0 0 5 5 0 50 0 0 0 0 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 65 0 35 0 0 15 15 95 45 0 0 5 40 0 5 0 0 5 0 70 25 0 0 20 200 25 5 0 0 0 35 55 15 40 0 0 0 0 25 20 55 0 0 15 0 0 0 0 0 0 0 0 40 0 5 0 0 0 20 0 0 5 0 0 75 20 0 20 0 0 0 0 50 0 0 20 0 0 5 0 20 0 10 0 0 0 15 5 30 15 15 0 0 0 5 80 0 0 15 30 0 5 0 0 40 20 0 15 0 0 0 15 45 0 0 5 20 0 0 5 50 0 0 5 0 15 0 50 0 60 0 0 5 0 0 0 0 0 0 5 0 20 0 5 5 40 5 0 20 0 10 0 0 0 0 45 0 0 60 0 0 30 10 20 15 40 0 0 50 0 0 0 0 0 0 0 0 0 90 0 5 5 0 0 20 0 50 5 0 0 55 20 20 0 5 5 95 65 0 30 20 0 0 20 95 5 35 5 10 100 40 90 80 1550 0 20 0 0 20 0 0 20 0 0 5 20 0 0 25 0 0 10 90 0 15 0 0 0 5 15 0 0 0 5 0 5 10 0 5 5 0 0 5 0 0 0 0 35 0 0 25 9545 20 5 5 20 95 5 5 40 25 0 5 0 0 0 0 5 0 0 0 0 5 0 15 0 15 50 5 0 0 35 0 0 30 25 0 0 0 0 65 85 0 40 20 0 80 80 10 600 60 0 0 0 5 25 45 0 15 5 0 0 0 95 0 0 0 20 0 0 0 0 0 0 0 0 0 10 0 0 20 80 95 0 0 0 0 35 0 0 0 0 5 15 20 45 10 0 0 00 0 0 20 45 30 50 0。
全国信息学奥林匹克联赛(2015)复赛
提高组 2
(请选手务必仔细阅读本页内容)
一.题目概况
二.提交源程序文件名
三.编译命令(不包含任何优化开关)
1、文件名(程序名和输入输出文件名)必须使用英文小写。
2、中函数 ()的返回值类型必须是,程序正常结束时的返回值必须是 0。
3、全国统一评测时采用的机器配置为: () x2 240 ,2.8,内存 4G,上述时限以此配置为准。
4、只提供格式附加样例文件。
5、特别提醒:评测在当前最新公布的下进行,各语言的编译
器版本以其为准。
1.跳石头
()
【问题描述】
一年一度的“跳石头”比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。
组委会已经选择好了两块岩石作为比赛起点和终点。
在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。
在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。
由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。
【输入格式】
输入文件名为。
输入文件第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。
接下来 N 行,每行一个整数,第 i 行的整数(0 < < L)表示第 i 块岩石与起点的距离。
这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。
【输出格式】
输出文件名为。
输出文件只包含一个整数,即最短跳跃距离的最大值。
【输入输出样例 1】
【输入输出样例 1 说明】
将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃
距离为 4(从与起点距离 17 的岩石跳到距离 21 的岩石,或者
从距离 21 的岩石跳到终点)。
【输入输出样例 2】
见选手目录下的 2 和 2。
【数据规模与约定】
对于 20%的数据,0 ≤ M ≤ N ≤ 10。
对于 50%的数据,0 ≤ M ≤ N ≤ 100。
对于 100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤1,000,000,000。
2.子串
()
【问题描述】
有两个仅包含小写英文字母的字符串A和B。
现在要从字符
串A中取出k个互不重叠的非空子串,然后把这k个子串按照其
在字符串A中出现的顺序依次连接起来得到一个新的字符串,
请问有多少种方案可以使得这个新串与字符串 B 相等?注意:
子串取出的位置不同也认为是不同的方案。
【输入格式】
输入文件名为。
第一行是三个正整数 n,m,k,分别表示字符串 A 的长度,字符串 B 的长度,以及问题描述中所提到的 k,每两个整数之
间用一个空格隔开。
第二行包含一个长度为 n 的字符串,表示字符串A。
第三行包含一个长度为 m 的字符串,表示字符串B。
【输出格式】
输出文件名为。
输出共一行,包含一个整数,表示所求方案数。
由于答案
可能很大,所以这里要求输出答案对 1,000,000,007 取模的
结果。
【输入输出样例 1】
【输入输出样例 2】
【输入输出样例 3】
【输入输出样例说明】
所有合法方案如下:(加下划线的部分表示取出的子串)
样例 1: /
样例 2:a / a / a a / a
b / b / b
样例 3:a a b / a a b / a a a b / a a b
a a
b a a b / a a a b / a a b
【输入输出样例 4】
见选手目录下 4 与 4。
【数据规模与约定】
对于第 1 组数据:1≤n≤500,1≤m≤50,1;
对于第 2 组至第 3 组数据:1≤n≤500,1≤m≤50,2;
对于第 4 组至第 5 组数据:1≤n≤500,1≤m≤50,;
对于第 1 组至第 7 组数据:1≤n≤500,1≤m≤50,
1≤k≤m;
对于第 1 组至第 9 组数据:1≤n≤1000,1≤m≤100,
1≤k≤m;
对于所有 10 组数据:1≤n≤1000,1≤m≤200,1≤k≤m。
3. 运输计划
()
【问题描述】
公元 2044 年,人类进入了宇宙纪元。
L 国有 n 个星球,还有 1 条双向航道,每条航道建立在两
个星球之间,这 1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司,该公司有很多个运输计划,每个
运输计划形如:有一艘物流飞船需要从号星球沿最快的宇航路
径飞行到号星球去。
显然,飞船驶过一条航道是需要时间的,
对于航道j,任意飞船驶过它所花费的时间为,并且任意两艘飞
船之间不会产生任何干扰。
为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L
国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶
过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。
在虫洞建设完成后,这 m 个运输计划会同时开始,所有飞
船一起出发。
当这 m 个运输计划都完成时,小 P 的物流公司
的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出
小 P 的物流公司完成阶段性工作所需要的最短时间是多少?
【输入格式】
输入文件名为。
第一行包括两个正整数 n、m,表示 L 国中星球的数量及小
P 公司预接的运输计划的数量,星球从 1 到 n 编号。
接下来 1 行描述航道的建设情况,其中第 i 行包含三个整
数 , 和,表示第 i 条双向航道修建在与两个星球之间,
任意飞船驶过它所花费的时间为。
接下来 m 行描述运输计划的情况,其中第 j 行包含两个正
整数和,表示第 j 个运输计划是从号星球飞往号星球。
【输出格式】
输出文件名为。
共 1 行,包含 1 个整数,表示小 P 的物流公司完成阶段
性工作所需要的最短时间。
【输入输出样例 1】
见选手目录下的 1 与 1。
【输入输出样例 1 说明】
将第 1 条航道改造成虫洞:则三个计划耗时分别为:11、12、11,故需要花费的时间为 12。
将第 2 条航道改造成虫洞:则三个计划耗时分别为:7、15、11,故需要花费的时间为 15。
将第 3 条航道改造成虫洞:则三个计划耗时分别为:4、8、11,故需要花费的时间为 11。
将第 4 条航道改造成虫洞:则三个计划耗时分别为:11、15、5,故需要花费的时间为 15。
将第 5 条航道改造成虫洞:则三个计划耗时分别为:11、10、6,故需要花费的时间为 11。
故将第 3 条或第 5 条航道改造成虫洞均可使得完成阶段性
工作的耗时最短,需要花费的时间为 11。
【样例输入输出 2】
见选手目录下的 2 与 2。
【数据规模与约定】
所有测试数据的范围和特点如下表所示。