《自创试题-lzx.doc》由会员分享，可在线阅读，更多相关《自创试题-lzx.doc（4页珍藏版）》请在金锄头文库上搜索。
1、寒假作业自创试题K2002_12 李子星【第一题】金链Godline.exeTime Limit: 0.2sMemory Limit: 640Kb【问题描述】LZ已经没有Money了，但N天后LZ会收到许多 Money。LZ有一条金链，恰好由N个金环一个套一个组成。他必须每天支付给旅馆的店主一个金环，但也可以一次支付多个给对方，店主会将他以前支付的金环（金链）找零给他。但是必须在店主有足够的金环（金链）找给他时才可以。当LZ收到钱时，他会用钱赎回他的金链。LZ非常喜欢这条金链，不忍心下手，因此希望取出的次数（一次从一段金链中取出一个金环）越少越好。怎样才能使取出的次数最少呢？他便向同行的你请教
2、来了。例如。当N=5时，你可以取出第二个金环。你的金链被分成了三部分：1(左边剩下的那一段)，1(取出来的金环)，3(右边剩下的那一段)。LZ可以：第一天支付一个第二天支付一个第三天支付3个金环（长度为3的金链，对方找回给你两个金环）第四天，第五天再支付店主找回给他的那两个金环。注意：LZ的店主允许他选择找零的方式。【数据说明】LZ要等待的天数也就是金链的长度N=1016【输入】输入文件名：Godline.in输入文件只有一个数字N【输出】输出文件名：Godline.out输出文件也只有一个数字，即最少取出的金环数【样例】Godline.inGodline.out92【第二题】公路建设Road
3、.exeTime Limit: 1sMemory Limit: 640Kb【问题描述】A国是一个新兴的国家，有N个城市，分别编号为1,2.3N。政府想大搞公路建设，提供了优惠政策：对于每一个投资方案的预计总费用，政府负担50%，并且允许投资的公司对过往的汽车收取连续5年的养路费。世界各地的大公司纷纷投资，并提出了自己的建设方案，他们的投资方案包括这些内容：公路连接的两座城市的编号，预计的总费用（假设他们的预计总师准确的）。你作为A国公路规划局的总工程师，有权利决定每一个方案是否接受。但是政府给你的要求是：要保证各个城市之间都有公路直接或间接相连。因为是新兴国家，政府的经济实力还不强。政府希望负
4、担最少的费用。因为大公司并不是同时提出方案，政府希望每接到一个方案，就可以知道当前需要负担的最小费用和接受的投资方案，以便随时开工。关于你给投资公司的回复可以等到开工以后再给。注意：A国一开始是没有公路的。【数据说明】A国的城市数目N=500，投资的方案总数M=2000。【输入】输入文件名：Road.in第1行有两个数字：N、M第2行到第M+1行给出了各个投资方案，第i行的方案编号为i-1编号小的方案先接到，一个方案占一行，每行有3个数字，分别是连接的两个城市编号a、b，和投资的预计总费用cost。【输出】输出文件名：Road.out输出文件共有M行。每一行的第一个数字是当前政府需要负担的最少
5、费用（保留1位小数），后面是X个数字，表示当前政府接受的方案的编号，不要求从小到大排列。但如果此时接受的所有投资方案不能保证政府的第一条要求，那么这一行只有一个数字0【样例】Road.inRoad.out3 51 2 41 3 42 3 41 3 21 2 204.00 1 2 4.00 1 2 3.00 1 4 2.00 4 5【第三题】迷宫Diablo.exeTime Limit: 5sMemory Limit: 640Kb【问题描述】ZF最近又迷上了暴雪公司的游戏Diablo。他控制的魔法师走到了一个迷宫里面。这个迷宫中道路错综复杂，但是ZF早就记得滚瓜烂熟了，所有的道路他都记得：这个迷
6、宫有多少个路口，哪些路口之间有道路相连，道路多长都记得清清楚楚。一些道路会有敌人，杀掉敌人就会有经验值。因为技术高超，ZF的魔法师可以轻松解决迷宫中的任意多的敌人。现在他想在最短的时间在这个迷宫中得到最多的经验值，对算法比较头痛的他就不知道要怎么走了，因此他向你求助。注意：必须要走过敌人所在的道路才能杀死他。敌人不会到处乱跑，敌人不会复活起点和终点也被当作是路口（起点为标号为1的路口，终点为标号为N的路口），一定是从起点进入终点出来因为他的魔法师会放魔法，可以从任意一个路口传送到其他任意一个路口（释放这个魔法不需要走动），所需要的时间都只需要T。当然，传送的时间肯定比走过去的时间要少（要不然还
7、叫什么魔法嘛）。这个迷宫一定是连通的，也就是说每两个路口之间都至少有一条路可以直接或间接到达。ZF可以给你提供这些信息：迷宫的路口数N（各个路口都有自己的编号）他的魔法师杀掉一个敌人需要的时间TK传送一次需要的时间T迷宫中的道路总数M，以及各条道路的情况，包括连接的路口的编号，走过需要的时间，以及道路上的敌人数目。【数据说明】路口的数目：2=N=104道路的数目：NM=106【输入】输入文件名：Diablo.in第1行有4个正整数：N, M, TK, T第2行到第M+1行每行4个数字：a, b, Tab, Eab,描述了这M条道路的情况【输出】输出文件名：Diablo.out只有一行：得到最多
8、经验并走出迷宫的最少耗时 Tmin 【样例】Diablo.inDiablo.out5 5 1 11 2 5 12 3 3 23 4 4 11 4 2 34 5 7 130【第四题】NumberNumber.exeTime Limit: 1sMemory Limit: 640Kb【问题描述】一个合法的n位K进制数定义如下： 它是一个首位不为0的K进制数。 它不包含连续的两个0。任务：对于输入的K，n。求出满足上述条件的K进制数个数。【数据说明】2=K=50, 2=n=1800【输入】输入文件名：Number.in只有一行：N, K【输出】输出文件名：Number.out输出文件只有一个数字，即满足条件的N位K进制数总个数【样例】Number.inNumber.out2 22【样例说明】这两个数为：10,11
