基本程序题集解析

1、基本程序题集NOIP 是一个比较基础的比赛，大家都说 NOIP 是 考察基本算法的熟练掌握， 所以个人认为无论是普及 组还是提高组，都要从最最基本的题做起，要达到： 只要是简单题，编完就对不用编译；一般的题， 写出来的都是对的运行后几本上是正确的。 为了 提高，于是做了一个基本程序题集，以便查找自己的 不足之处。题集目录一、贪心算法Problem1 删数问题Problem2 旅行家的预算Problem3 线段覆盖Problem4 背包问题Problem5 任务调度Problem6 果子合并Problem7 射击竞赛Problem8 任务安排Problem9 最小差距二、分治算法Problem1

2、 一元三次方程的解Problem2 查找第 k 大元素Problem3 麦森数Problem4 逆序对个数Problem5 寻找最近点对Problem6 剔除多余括号Problem7 赛程安排三、搜索算法Problem1 皇后问题Problem2 八数码问题Problem3 拼图Problem4 质数方阵Problem5 埃及分数Problem6 字符串变换Problem7 聪明的打字员Problem8 01 序列Problem9 生日蛋糕四、图论算法Problem1 一笔画问题Problem2 Car 的旅行路线Problem3 求割点与桥Problem4 十字绣Problem5 舞会Pro

3、blem6 休息中的小呆Problem7 最优布线问题Problem8 磁盘碎片整理Problem9 说谎岛Problem10 01 串问题Problem11 海岛地图五、数学问题Problem1 数的划分Problem2 最优分解方案Problem3 出栈序列统计Problem4 百事世界杯之旅Problem5 电子锁Problem6 堆塔问题Problem7 取数游戏Problem8 球迷购票Problem9 Fibonacci 公约数Problem10 传球问题Problem11 约瑟夫问题Problem12 青蛙过河Problem13 棋盘游戏六、数据结构Problem1 火车栈Pro

4、blem2 括号表达式Problem3 银河英雄传说Problem4 矩形覆盖Problem5 最短路径问题Problem6 果子合并七、字符串处理Problem1 相对分子质量Problem2 表达式求值Problem3 侦探推理Problem4 最长公共子串Problem5 一元一次方程的解Problem6 多项式乘法一、 贪心算法Problem1 删数问题 (cutnum)题目描述：给定一正整数n(n的位数小于240)，现要删除数n中的s个数码，使其 得到的新数最小，求这个最小数。输入输入有两行，第一行为整数 n,第二行即为s 输出输出一行,即最小的那个数Problem2 旅行家的预算

5、(travel)题目描述一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市 (假设出 发时油箱是空的)。给定两个城市之间的距离 D1、汽车油箱的量 C (以升为 单位)、每升汽油能行驶的距离 D2、出发点每升汽油价格 P和沿途油站数N (N可以为零)，油站i离出发点的距离i、每升汽油价格Pi(i=1,2,N)。 计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“NoSolution ”。输入输入第一行有5个数:D1,c, D2, P,N(前四个为实数，N为整数,N<=1000) 后面有 N 行,每行两个实数,分别表示对应的加油站离出发点的距离, 与每升汽油的价格 输出输出仅

6、一行,即最少花费Problem3 线段覆盖 (sequence)题目描述给定数轴上的 n 条线段 (n<100) ,每个线段有其端点 ai 、 bi 组成 (-999<=ai<bi<=999),由于有些线段会相互覆盖，所以求出至少去掉多少条线 段，才能使剩下的所有线段之间互相没有内部公共点 (若只是端点重合，则 不是内部公共点 )。输入输入第一行为整数 N,接下来有N行，分别描述每条线段输出输出第一行为最少删除的线段数 s 后面 s 行描述一个可行的删除方案，即删除那些线段Problem4 背包问题 (cheaf)题目描述 有一个贼在偷窃一家商店时发现有 N 件物品 :

7、第 i 件物品值 Vi 元，重Wi磅，(1 w iw n),此处Vi和Wi都是整数。他希望带走的东西越值钱越好， 但他的背包中最多只能装下 W 磅的东西 (W 为整数 )，小偷可带走某个物品 的一部分 (只带走其中的几磅 ),小偷应该带走哪几件东西,每件东西的重量 是多少？ 输入输入第一行为N,W(N<=10000)，后面N行描述每个物品，每行两个数， 即为 Vi 与 Wi 输出输出第一行为大的最大价值。Problem5 任务调度题目描述一个单位时间任务是个作业 ,如要在计算机上运行一个程序 ,它恰覆盖一 个单位的运行时间。给定一个单位时间任务的集合S对S的一个调度即S的一个排列 ,其中

8、规定了这些任务的执行顺序。该调度中的第一个任务开始于 时间0,结束于时1；第二个任务开始于时间1,结束于时间2;。单处理器 上具有期限和罚款的单位时间任务调度问题的输入如下 :1包含n个单位时间任务的集合S=1,2,n;2. n个取整的期限d1,dn,(1 w d,w n),任务i要求在di前完成；3. n个非负的权(或罚款)w1,wn。如果任务i没在时间di之前结束，则导致罚款 wi;要求找出S的一个调度，使之最小化总的罚款。输入输入第一行为N(N<=1000)，后面N行每行两个数，即为对应的di与wi输出输出最小总罚款 Problem6 果子合并Problem6 果子合并 题目描述在

9、一个果园里， 多多已经将所有的果子打了下来， 而且按果子的不同种 类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并， 多多可以把两堆果子合并到一起， 消耗的体力等于两堆果 子的重量之和。可以看出，所有的果子经过 n-1 次合并之后，就只剩下一堆 了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家， 所以多多在合并果子时要尽可能 地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目， 你的任务是设计出合并的次序方案， 使多多耗费的体力最少， 并输 出这个最小的体力耗费值。例如有 3 种果子，数目依次为 1， 2， 9。可以先

10、将 1、 2 堆合并，新堆 数目为 3，耗费体力为 3。接着，将新堆与原先的第三堆合并，又得到新的 堆，数目为 12，耗费体力为 12。所以多多总共耗费体力 =3+12=15。可以证 明 15 为最小的体力耗费值。输入输入第一行为N(N<=1000),第二行有N个整数，分别描述每个果子 输出输出一个数即最小代价Problem7 射击竞赛题目描述射击的目标是一个由 R*C(2W RW CW 1000)个小方格组成的矩形网格。 每 一列恰有2个白色的小方格和 R-2个黑色的小方格。行从顶至底编号为1-R, 列从左至右编号为 1-C。射击者可射击 C次。在连续的C次射击中，若每列 恰好有一个白

11、色的方格被射中， 且不存在无白色方格被射中的行， 这样的射 击才是正确的。如果存在正确的射击方法，则要求找到它。输入输入第一行为R, C,后面R行每行C个数，如果为0则为白格，1则 为黑格 输出输出正确方案每行两个数即射击坐标，否则输出 -1Problem8 任务安排 (job)题目描述一家工厂的流水线正在生产一种产品，这需要两种操作：操作A 和操作B。每个操作只有一些机器能够完成。A型机器从输入库接受工件，对其施加操作A,得到的中间产品存放在缓冲库。B型机器从缓冲库接受中间产品，对其施加操作 B,得到的最终产品存放在输出库。所有的机器平行并且 独立地工作， 每个库的容量没有限制。 每台机器的

12、工作效率可能不同， 一台 机器完成一次操作需要一定的时间。 给出每台机器完成一次操作的时间， 计算完成A操作的时间总和的最小值，和完成B操作的时间总和的最小值。输入输入第一行 三个用空格分开的整数：N,工件数量 (1<=N<=1000)M1， A 型机器的数量 (1<=M1<=30)M2， B 型机器的数量 (1<=M2<=30)第二行，接下来 M1个整数(表示 A型机器完成一次操作的时间，1.20),接着是M2个整数(B型机器完成一次操作的时间，1.20)输出只有一行。输出两个整数：完成所有 A 操作的时间总和的最小值，和 完成所有B操作的时间总和的最小值

13、(A操作必须在B操作之前完成)。Problem9 最小差距 (mindis)题目描述给定一些不同的一位数字， 你可以从这些数字中选择若干个， 并将它们 按一定顺序排列， 组成一个整数， 把剩下的数字按一定顺序排列， 组成另一 个整数。组成的整数不能以 0开头(除非这个整数只有 1 位)。例如，给定 6个数字， 0,1,2,4,6,7，你可以用它们组成一对数 10和 2467， 当然，还可以组成其他的很多对数，比如 210 和 764， 204 和 176。这些对 数中两个数差的绝对值最小的是 204和 176，为 28。给定 N 个不同的 09 之间的数字，请你求出用这些数字组成的每对数 中，

14、差的绝对值最小的一对(或多对)数的绝对值是多少？ 输入输入第一行包括一个数 T (TW 1000),为测试数据的组数。每组数据包括两行， 第一行为一个数 N (2W NW 10),表示数字的个数。 下面一行为 N 个不同的一位数字。输出输出T行，每行一个数，表示第i个数据的答案。即最小的差的绝对值分治法Problem1 一元三次方程的解 (equation)题目描述有形如： ax3+bx2+cx+d=0 这样的一个一元三次方程。 给出该方程中各项 的系数 (a， b，c，d 均为实数 )，并约定该方程存在三个不同实根(根的范围在-100 至 100之间 )，且根与根之差的绝对值 >=1。

15、要求由小到大依次在同一 行输出这三个实根 (根与根之间留有空格 )，并精确到小数点后 4 位。 输入输入仅一行，有四个数，依次为a、 b、c、d输出输出也只有一行，即三个根 ( 从小到大输出 )Problem2 查找第 k 大元素 (findk)题目描述有 N 个数，请找出其中第 k 大的数 (N<=10000) 输入输入第一行为N、K,第二行有N个数 输出输出第K大的数Problem3 麦森数 (mason)题目描述形如2AP-1的素数称为麦森数， 这时P 一定也是个素数。但反过来不一 定，即如果P是个素数，2AP-1不一定也是素数。到 1998年底，人们已找 到了 37个麦森数。最大

16、的一个是 P=3021377,它有909526位。麦森数有许 多重要应用，它与完全数密切相关。任务：从文件中输入 P( 1000<P<3100000)，计算2AP-1的位数和最后500 位数字(用十进制高精度数表示)输入输入只包含一个整数 P(1000<P<3100000) 输出输出第一行是十进制高精度数 2AP-1 的位数。第 2-11 行：十进制高精度数 2AP-1 的最后 500 位数字。(每行输出 50位，共输出 10 行，不足 500 位时高位补 0)Problem4 逆序对个数 (sort)题目描述给出一个数列an,如果存在i<j，但是ai>aj

17、那么我们称ai与aj是一对逆序对，现要求求出数列 an中逆序对的个数输入输入第一行为整数 N(N<=10000)，第二行有N个数，即为数列an 输出输出仅一个数,即逆序对的个数Problem5 寻找最近点对题目描述给出平面内的N(N<=10000)个点，点两两都有一个距离，现要求出所有 点对中距离最小的那一对输入输入第一行为N，后面有N行，每行两个数分别描述每个点的横纵坐标 输出输出一个数,即最近点对的距离Problem6 剔除多余括号题目描述键盘输入一个含有括号的四则运算表达式, 可能含有多余的括号, 编程 整理该表达式, 去掉所有多余的括号, 原表达式中所有变量和运算符相对位

18、置保持不变,并保持与原表达式等价。输入输入一行,即为表达式,长度小于 250输出输出也一行,为剔出多余括号之后的表达式Problem7 赛程安排题目描述有 n 个编号为 1 到 n 的运动员参加某项运动的单循环比赛，即每个运 动员要和所有其他运动员进行一次比赛。 试为这 n 个运动员安排一个比赛日 程，使得每个运动员每天只进行一场比赛，且整个比赛在 n-1 天内结束。 输入输入一行，即为运动员人数 n（n<=10000） 输出输出一个n阶方阵A1.N,0.N-1（表示比赛日程），当J> 0时，AI,J表示 第I名运动员在第J天的比赛对手（保证有解）。三、搜索算法Problem1 皇

19、后问题 (queens)题目描述在一 N*N 的棋盘中，摆上 N 个皇后，使其互不攻击，有多少种摆法(皇后攻击同行同列与同斜行的棋子 ) 输入输入一行，即整数 N(N<=10)输出输出一个数，即总方案数Problem2 八数码问题 (8number)题目描述有一个 3*3 的方阵， 其中有 8 个数， 一个方格为空， 可以通过移动方格 将初始的方阵移动成其他的方阵输入输入两个 3*3 的方阵，即为初始状态与目标状态， 0 代表空的方格 输出输出最少的步数使初始方阵转换为目标方阵，如果无解则输出 No Solution 'Problem3 拼图 (puzzling)题目描述这个拼图

20、游戏要求将一些图形拼成一个正方形，图形的个数从 1 到 5。 图形不能旋转， 拼的时候不能重叠， 拼完后的正方形里面不能有隙。 所有给 定的图形都要使用。输入输入第一行是一个整数 n,表示图形的个数，范围从 1到5。接下来有n 个部分，每个部分的第一行是2个整数i和j，表示下面的i行j列用来描述一个图形。图形用 0和 1 表示, 1 表示图形占有这个置, 0表示不占有,中 间没有空格。图形的长与宽都不超过 5。根据图形给出的顺序给每个图形编 号，从 1 开始，至多到 5。保证数据无多解情况。输出如果不能拼成一个正方形，就输出“ No solution possible ”；否则，输出11 /

21、35一种拼的方案： 一个正方形的数阵， 每个位置上的数字是占有这个位置的图 形的编号，中间没有空格。Problem4 质数方阵 (prime)题目描述求一个 5*5 的方阵，满足如下要求：(1) 每行每列的数字和为 s(2) (1,1)上的数字为 t(3) 每个横行竖行斜行所形成的五位数都是质数给定 s,t 求满足要求的方阵数 输入输入一行两个数即 s， t 输出输出第一行为方案数，接下来按序输出所有方案(每个方案件都有一空行)Problem5 埃及分数 (egypt)题目描述在古埃及，人们使用单位分数的和(形如 1/a 的, a 是自然数 )表示一切有理数。如： 2/3=1/2+1/6,但不

22、允许 2/3=1/3+1/3,因为加数中有相同的。对于一个分数 a/b, 表示方法有很多种，但是哪种最好呢？ 首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越 大越好。如：19/45=1/3 + 1/12 + 1/18019/45=1/3 + 1/15 + 1/4519/45=1/3 + 1/18 + 1/30,19/45=1/4 + 1/6 + 1/18019/45=1/5 + 1/6 + 1/18.最好的是最后一种，因为 1/18 比 1/180,1/45,1/30,1/180 都大。 给出a,b(O a b 1000),编程计算最好的表达方式。输入输入仅一行，即为N,表示有

23、N组测试数据，每组测试数据为一行包含 a,b(0ab1000)。输出输出 N 行，对应每组测试数据，对于每组测试数据输出若干个数，自小到大排列，依次是单位分数的分母。Problem6 字符串变换 (string)题目描述已知有两个字串 A$, B$ 及一组字串变换的规则(至多 6 个规则) : A1$ -> B1$ A2$ -> B2$规则的含义为：在人$中的子串 A1$可以变换为 B1$、A2$可以变换 为B2$。例如：A$='abcd' B$='xyz'变换规则为：abc'->xu'ud'->y'y&#

24、39;->yz'则此时，A$可以经过一系列的变换变为B$,其变换的过程为： abc-d>' xu-d>' x-y>' xyz '共进行了三次变换，使得 A$ 变换为 B$。输入输入格式如下：A$ B$A1$ B1$ A2$ B2$ |-> 变换规则所有字符串长度的上限为20。输出输出最短步数，若在10步(包含10步)以内能将A$变换为B$，则输 出最少的变换步数；否则输出 "NO ANSWER!"Problem7 聪明的打字员 (clever )题目描述阿兰是某机密部门的打字员， 她现在接到一个任务： 需

25、要在一天之内输 入几百个长度固定为 6 的密码。 当然，她希望输入的过程敲击键盘的总次数 越少越好。不幸的是，出于保密的需要， 该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键:Swap0,Swap1,Up, Down, Left, Right ，为了说明这 6 个键的作用， 我们先定义录入区的 6个位置的编号， 从左至右 依次为 1 ， 2， 3， 4， 5， 6。下面列出每个键的作用：SwapO:按SwapO,光标位置不变，将光标所在位置的数字与录入区的1 号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的 1 号 位置，则按 Swap0 键之后，录入区的

26、数字不变；Swapl :按Swapl，光标位置不变，将光标所在位置的数字与录入区的6 号位置的数字（左起第六个数字）交换。如果光标已经处在录入区的 6 号 位置，则按 Swap1 键之后，录入区的数字不变；Up：按Up,光标位置不变，将光标所在位置的数字加 1 （除非该数字 是9）。例如，如果光标所在位置的数字为 2，按Up之后，该处的数字变为 3；如果该处数字为 9,则按 Up 之后,数字不变,光标位置也不变；Down :按Down，光标位置不变，将光标所在位置的数字减1 （除非该数字是 0）,如果该处数字为 0,则按 Down 之后,数字不变,光标位置也不 变；Left：按Left，光标左

27、移一个位置，如果光标已经在录入区的1号位置（左起第一个位置）上,则光标不动；Right：按Right，光标右移一个位置，如果光标已经在录入区的6号位置（左起第六个位置）上,则光标不动。当然, 为了使这样的键盘发挥作用, 每次录入密码之前, 录入区总会随 机出现一个长度为 6 的初始密码, 而且光标固定出现在 1 号位置上。 当巧妙 地使用上述六个特殊键之后, 可以得到目标密码, 这时光标允许停在任何一 个位置。现在, 阿兰需要你的帮助, 编写一个程序, 求出录入一个密码需要的最 少的击键次数。输入输入一行, 含有两个长度为 6 的数,前者为初始密码, 后者为目标密码, 两个密码之间用一个空格隔

28、开。输出输出仅一行,含有一个正整数,为最少需要的击键次数。Problem8 01 序列 （01）题目描述求指定长度满足下列要求的序列的个数：（1）全由 01 组成（2）任意一段连续的子串没有连续出现 3次（如： 010101、001001001 就不符合要求 ）输入输入仅一个数,即序列长度 （=35） 输出输出仅一个数,即满足要求的序列总数Problem9 生日蛋糕 (cake)题目描述 要制作一个体积为 N*pi 的 M 层生日蛋糕，每层都是一个圆柱体。 设 从下往上数第i(1 <= i <= M)层蛋糕是半径为 Ri,高度为Hi的圆柱。当i < M 时，要求Ri >

29、 Ri+1且Hi > Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经 费，我们希望蛋糕外表面(最下一层的下底面除外)的面积Q 最小。 令 Q=S*pi请编程对给出的N和M，找出蛋糕的制作方案(适当的Ri和Hi的值)， 使 S 最小。(除 Q 外，以上所有数据皆为正整数) 输入输入两行， 第一行为 N( N <= 10000)，表示待制作的蛋糕的体积为 N*pi ； 第二行为 M(M <= 20) ，表示蛋糕的层数为 M。输出输出仅一行，是一个正整数 S (若无解则S=0)。四、图论算法Problem1 一笔画问题 （fence）题目描述给出一个图，求其欧拉回路（若没有回路，则

30、求其欧拉路径） ，若不存在则输出 No solution '输入输入的第一行为边数 F（<=1024）,后面F行每行表示一条边（定点标号范围为 1-500）输出输出一条合法的欧拉回路（路径） ，若有多条满足要求，输出其字典序 最小的那一个。Problem2 Car 的旅行路线 （car）题目描述住在城市 A 的 Car 想和朋友一起去城市 B 旅游。她知道每个城市都有四 个飞机场， 分别位于一个矩形的四个顶点上， 同一个城市中两个机场之间有 一条笔直的高速铁路，第 I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。那么Ca

31、r应如何安排到城市 B的路线才能尽可能的节省花费，求其最少 花费 输入第一行有四个正整数 s， t， A， B。S（0<S<=100表示城市的个数，t表示飞机单位里程的价格， A, B分别为 城市A，B的序号，（1<=A，B<=S。接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2, yi2，xi3，yi3，Ti，这当中的（xi1，yi1），（xi2，yi2），（xi3，yi3）分别是第I个城市中任意三个 机场的坐标， T I 为第 I 个城市高速铁路单位里程的价格。输出输出最小花费，保留一位小数Problem3 求割点与桥题目描述给定一个图，求其割点与桥输入

32、第一行有两个整数，n、e,即点数与边数后面e行，每行两个整数 v1、v2,表示点v1与v2相连输出首先输出所有割点,每行输出一个然后输出所有桥,每行一条（不用考虑顺序 ）Problem4 十字绣 （cross）题目描述布是一个 n*m 的网格,线只能在网格的顶点处才能从布的一面穿到另 一面。每一段线都覆盖一个单位网格的两条对角线之一,而在绣的过程中, 一针中连续的两段线必须分处布的两面。给出布两面的图案（实线代表该处有线 ,虚线代表背面有线 ）,问最少需要几针才能绣出来？一针是指针不离开 布的一次绣花过程。输入输入第 1 行两个数 N 和 M（1<=N,M<=200） 。接下来 N

33、 行每行 M 个数描述正面。再接下来N行每行M个数描述反面。每个格子用 .（表示空） ,/ （表示从右上角连到左下角）（表示从左上角连到右下角）和 X （表示连两条对角线）表示。输出输出一个数,最少要用的针数Problem5 舞会 （ball）题目描述一个舞会邀请 n 个人,这 n 个人每一个人都有一个小花名册, 名册里面 写着他所愿意交流的人的名字。比如说在A的人名单里写了 B，那么表示A愿意与B交流；但是B的名单里不见的有 A,也就是说B不见的想与A交流。 但是如果A愿意与B交流，B愿意与C交流，那么A 一定愿意与 C交流。也 就是说交流有传递性。现在觉得需要将这 n 个人分为 m 组,要

34、求每一组的 任何一人都愿意与组内其他人交流。并求出一种方案以确定m 的最小值是多少。注意：自己的名单里面不会有自己的名字。输入输入第一行一个数 n。接下来n行，每i+1行表示编号为i的人的小花17 / 35名册名单，名单以 0 结束。 1<=n<=200。输出输出即 m 的最小值Problem6 休息中的小呆 (rest)题目描述NOIP 备战之际，小呆正在悠闲(欠扁)地玩一个叫“最初梦想”的游 戏。游戏描述的是一个叫 pass 的有志少年在不同的时空穿越对抗传说中的 大魔王 chinesesonic 的故事。小呆发现这个游戏的故事流程设计得很复杂， 它有着很多的分支剧情， 但不同

35、的分支剧情是可以同时进行的， 因此游戏可 以由剧情和剧情的结束点组成， 某些剧情必须要在一些特定的剧情结束后才 能继续发展。 为了体验游戏的完整性， 小呆决定要看到所有的分支剧情 完成所有的任务。 但这样做会不会耽误小呆宝贵的睡觉时间呢？所以就请你 来解决这个问题了。输入输入会给你一个剧情流程和完成条件的列表，其中第一行有一个数 n (0<*100),表示总共有n个剧情结束点，第二行一个数 m(0<m<=120),表 示 由 m 个 不 同 的 剧 情 ， 下 面 的 m 行 中 每 行 有 三 个 数 i0<i<=100),j0<j<=100),k0

36、<k<=1000),表示从剧情结束点i必须完成一个耗费时 间为 k 的剧情才能到达剧情结束点 j 。注意，这 m 行中出现的 1 不是剧情结 束点而是游戏的开始，而 n+1 表示游戏结束。输出输出第一行为一个数，即你要告诉小呆完成整个游戏至少需要多少时 间， 第二行有若干个数， 即要经过的所有可能的剧情结束点 (按升序输出) 。Problem7 最优布线问题题目描述校园里有 n 台计算机， 要将它们用数据线连接起来。 由于计算机所处的 位置不同，连接 2 台计算机的费用往往是不同的。如果将每 2 台计算机都 用数据线连接， 势必造成浪费。 为了节省费用， 可以采用数据的间接传输手

37、段，即一台计算机可以间接通过若干台计算机(作为中转 )来实现与另一台计算机的连接。如何用最少费用连接 n 台计算机。 (N<=1000) 输入输入数据。第一行有1个正整数n,表示计算机数。此后 n行，每行有 n 个正整数。第 x+1 行，第 y 列的正整数表示直接连接第 x 台计算机和第 y 台计算机的费用。输出输出最小费用Problem8 磁盘碎片整理题目描述出于最高安全性考虑， 司令部采用了特殊的安全操作系统。 该系统采用 一个特殊的文件系统。 在这个文件系统中所有磁盘空间都被分配了相同尺寸 的 N 块，用整数 1 到 N 表识，每个文件占用磁盘上任意区域的一块或多块 存储区， 未被

38、文件占用的存储块被认为是可以使用的。 如果文件存储在磁盘 上自然连续的存储块中，则能被以最快的速度读出。因为磁盘是均匀转动的， 所以存取上面的不同的存储快需要的时间也不 同。读取磁盘开头处的存储比读取磁盘结尾处的存储块快。根据以上现象， 我们事先将文件按其存取频率的大小用整数 1 到 K 标识。按文件在磁盘上最 佳的存储方法，1号文件将占用1 , 2,S1的存储块，2号文件占用 S1 + 1,S1+2S1+S2的存储块，依次类推。为了将文件以最佳形式存储在磁 盘上，需要执行存储酷块移动操作。操作后，原空间将被释放，新空间将被 占用。问对于一个文件序列， 最少需要多少次移动操作才能以最佳方式存储

39、到 磁盘上 输入输入第一行包含两个整数 N, K(N,K<=100000)，接下来K行每行描述一 个文件，第一个数为 Si,表示其存储块数量，后面有Si个整数，每个整数之间用空格隔开, 表示该文件按自然顺序在磁盘上占用的存储块标识, 所有 这些数都介于 1 和 N 之间,包括 1 和 N。所有磁盘空间的表识都不相同输出输出一个数,即最小移动次数Problem9 说谎岛 (island)题目描述哥仑布在到达美州后, 发现了一个奇特的岛屿。 这个岛屿上的人狡猾且 喜欢说谎,由于完全的谎言较易为人所识破,所以为了更加能够迷惑别人, 他们的言语往往是半真半假的。由于对于环境的不熟悉, 哥仑布有许

40、多问题要请教岛上的居民。 当然他 已经知道了岛上居民的这一说谎习俗。幸好,哥仑布的所有问题都只需回答“是”或者“否” ,这样便免去了19 / 35许多繁复。假设哥仑布询问了 N 个居民，对于每个居民只问两个问题，每 个居民只需对于每个问题回答“是”或“否” 。根据居民的习俗，可以断定 两个回答中必有一个是正确的， 而另一个是错误的。 同一个问题可以反复问 多人。哥仑布根据这 N 个人的回答，需要整理推断出他所有问题的答案。但 这一过程实在太复杂与困难了， 因此希望你能够编程求出所有可能答案的种 数。输入输入第一行是两个整数N( 1 < NW 10000)、M ( K M < 200

41、),以空格分隔。分别表示询问了 N 人，共有 M 个问题。整个输入文件共 N+1 行。第i+1行共有四个整数a,b,c,d，以空格分隔。表示第 i个人对于第a个 问题的答案是b,对于第c个问题的答案是 d。其中1 w a,c< M。b和d为0 时表示答案为“否； ”为 1 时表示答案为“是” 。输出若不可能推出任何结果，即无解，输出“NO ANSWEF”；否则输出可能答案组的个数。Problem10 01 串问题 (sequence)题目描述给定7个整数 N,A0,B0,L0,A1,B1,L1,要求设计一个 01串S=s1s2sisN,满足：1. si=0 或 si=1 , 1<=

42、i<=N；2. 对于 S 的任何连续的长度为 L0 0 的个数大于等于 A0 且小于等于 B0;3. 对于 S 的任何连续的长度为 L1 1 的个数大于等于 A1 且小于等于 B1;的子串 sjsj+1 sj+L0-1(1<=j<=N-L0+1),的子串 sjsj+1 sj+L1-1(1<=j<=N-L1 + 1),例如，N=6,A0=1,B0=2,L0=3,A仁1,B1=1丄仁2,则存在一个满足上述所有 条件的 01 串 S=010101。输入输入仅一行, 有 7 个整数, 依次表示 N,A0,B0,L0,A1,B1,L1(3<=N<=1000, 1

43、<= A0<=B0<=L0<=N, 1<=A1<=B1<=L1<=N),相邻两个整数之间用一个空格 分隔。输出输出仅一行，若不存在满足所有条件的 01 串，则输出一个整数 -1 ，否 则输出一个满足所有条件的 01 串。Problem11 海岛地图题目描述给出一个 (h*w) 的海岛地图，其中图中 1表示陆地， 0 表示水域，求所 有岛屿中，面积最大的一个岛屿输入输入第一行为w , h(<=100)，表示图的长与宽后面有 w 行，每行有一个长为 h 的 01 串，用来描述整个地图 输出输出仅一个数，即最大的海岛面积五、数学问题Problem

44、1 数的划分 (divide)题目描述将整数 n 分成 k 份，且每份不能为空， 任意两份不能相同 (不考虑顺序 )。 例如：n=7, k=3，下面三种分法被认为是相同的。1， 1， 5; 1， 5， 1; 5， 1， 1; 问有多少种不同的分法。输入 输入仅一行，即 N， K(N<=200,K<=20) 输出输出仅一个数，即总共的方法数Problem2 最优分解方案题目描述给定整数N,将其分解为若干个互不相同的整数，是他们的乘积最大 输入输入仅一个数， N(N<=1000) 输出输出最大乘积Problem3 出栈序列统计 (stack)题目描述 栈是常用的一种数据结构 ,有

45、 n 令元素在栈顶端一侧等待进栈 ,栈顶端另 一侧是出栈序列你已经知道栈的操作有两种:push和pop,前者是将一个元 素进栈 ,后者是将栈顶元素弹出 .现在要使用这两种操作 ,由一个操作序列可 以得到一系列的输出序列请你编程求出对于给定的 n,计算并输出由操作数 序列1,2,n,经过一系列操作可能得到的输出序列总数输入输入一个整数 n(1<=n<=50)输出 输出一个整数，即可能输出序列的总数目。Problem4 百事世界杯之旅 (pepsi)题目描述每个瓶盖上有一个球星的名字，有 N 个不同的球星，平均情况下，要 买多少瓶饮料才能集齐所有名字输入输入一个数 N(<=33)

46、输出输出平均情况下的瓶数， 若为整数则直接输出， 若为分数， 则以真分数 形式输出，格式如下：bacProblem5 电子锁题目描述某机要部门安装了电子锁。 m 个工作人员每人发一张磁卡， 卡上有开锁 的密码特征， 为了保证安全， 规定至少 n 个人同时使用各自的磁卡才能将锁 打开。 现在需要你计算一下， 电子锁上至少要有多少种特征， 每个人的磁卡 上至少要有几种特征。同时输出分配方案。输入输入仅一行，有两个数即 m(m<=7) ， n(<=m 且<=4)输出输出第一行为两个数，既电子锁上的特征数，与磁卡上的特征数后面 n 行按字典序数出一个 01 序列，表识每个人磁卡上的拥

47、有的特征， 1 表识有， 0 表示没有。Problem6 堆塔问题题目描述有 n 个边长为一的正立方体， 在一个宽为 1 的轨道上堆塔， 但它本身不 能分离。堆塔时底层必须有支撑，求对于 n 各正方体，又多少种方案 输入输入仅一行 n(n<=100)输出输出也只一行，即总方案数Problem7 取数游戏题目描述给出正整数n(<=1000000)和k(<n),然后按下列方法取数：(n=16,k=4)1： 取 1 剩152： 取 2 剩133： 取 4 剩94： 取 8 剩1第五次取不够,加上k 个,现在共5个5： 取 1 剩46： 取 2 剩2第七次取不够,加上k 个,现在共6

48、个7： 取 1 剩58： 取 2 剩3第九次取不够,加上k 个,现在共7个9： 取 1 剩610： 取 1 剩411： 取 1 剩0取完共取 11次输入输入仅一行,即 n,k输出若取得完,则输出取的次数,否则输出(ErrorProblem8 球迷购票题目描述球迷手上有 100 元与 50 元的钞票,每张票 50 元,现在有 m+n 个球迷 买票 (m 个手上持 50 元的, n 个手上持 100 元的 ),一开始售票员手上有钱, 有多少排队方案可以不出现没有钱找的局面 输入输入仅一行即 m, n(m,n<=5000) 输出输出有一行,即总得方案数Problem9 Fibonacci 公约

49、数题目描述给出两个 fibonacci 数，求一个最大的 fibonacci 数，满足这个数是他们 的最大公约数输入输入有两行，分别是两个 Fib on acci数（<=10人2000）输出即输出他们的 Fibonacci 公约数Problem10 传球问题 （ballgame）题目描述Grant 老师常和小朋友们一起玩一种传球游戏。游戏是这样进行的： 一群小朋友分成两组， 每组 n 人，围成一个圈。 每一个小朋友都有一个 编号 （1.n 之间），这个编号在其所在组中是唯一的。游戏开始之前， Grant老师会发给每个小朋友一个球，球上也有编号（1.n 之间），并且一个组中的球不会有两个相

50、同编号。然后，所有小朋友必须闭上眼睛，游戏开始。随着 Grant 老师口中的哨子发出的节奏，每个小朋友都用一只手把球传到右边， 而用另一只手接左边的来球。突然， Grant 老师的哨子停了， 关键的时刻到了。 小朋友马上睁开眼睛， 开始与同组的小朋友之间进行传球， 争取以最短的时间把球传到位。 传到位 是指一个组中的每一个小朋友手上的球的编号与他自己的编号相同。 最后获 胜的就是那个最先把球传到位的组。如果一旦哪方出现传球失误（球没被接到而落地 ），或犯规（一个人手上拿两个或两个以上的球）这一组就被判输。这个游戏非常有趣， 小朋友们玩了许多次。 他们总结出一条经验： 总是 两个人之间对传。也就

51、是说，不会出现a把球传给b,而b没有把球传给a的这种情况。 这样可以避免小朋友之间的失误与犯规。 不过还有个关键问题 就是怎么传。究竟应该把手上的球传给谁？现在需要你编一个程序来帮助小朋友们确定传球方法。 你的程序首先需 要计算出从一种初始状态开始：子问题 1 ：至少需要几次对传才能将球传到位。子问题 2：至少需要多少时间才能将球传到位。每一个时间单位一 个 小 朋 友 可 以 不 做 任 何 动 作 ， 也 可 以 与 另 外 一 个 小 朋 友 之 间进行对传。注意有些对传可以同时进行。 比如小朋友 1 与小朋友 2 之间的对传和小 朋友 3 与小朋友 4 之间的对传就可以在一个时间单位之

52、内完成， 但是被计作 两次对传。输入：输入第一行是一个整数 n （2<=n<=20000）。接下来有n行，每行一个整25 / 35数（仁n），其中第（i+1）行的整数表示i号小朋友手上的球的编号。输出：输出只有二行，每行一个整数，分别表示子问题 1 和子问题 2 的解。Problem11 约瑟夫问题题目描述n 个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针 “一二一”报数， 报到 2的人退出圈子。 这样不断循环下去， 圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。 试问最后剩下的人最开始的编号。输入输入一个正整数n,表示人的个数。输入

53、数据保证数字 n不超过100位。 输出输出一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。Problem12 青蛙过河 （frog）题目描述大小各不相同的一队青蛙站在河左岸的石墩（记为 A）上，要过到对岸 的石墩（记为D）上去。河心有几片荷叶（分别记为Y1Ym）和几个石墩（分别记 为S1Sn）。青蛙的站队和移动方法规则如下：1每只青蛙只能站在荷叶、石墩,或者仅比它大一号的青蛙背上（统 称为合法的落脚点） ；2一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另 一个落脚点；3 青蛙允许从左岸 A直接跳到河心的石墩、荷叶和右岸的石墩D 上,允许从河心的石墩和荷叶跳到右岸的石墩D上

54、；4青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动；5青蛙在离开左岸石墩后,不能再返回左岸；到达右岸后,不能再跳回；6假定石墩承重能力很大, 允许无论多少只青蛙都可呆在上面。 但是, 由于石墩的面积不大,至多只能有一只青蛙直接站在上面,而其他的青蛙只能依规则 1 落在比它大一号的青蛙的背上。7荷叶不仅面积不大,而且负重能力也有限,至多只能有一只青蛙站 在上面。8每一步只能移动一只青蛙，并且移动后需要满足站队规则； 9在一开始的时候，青蛙均站在A 上，最大的一只青蛙直接站在石墩上，而其它的青蛙依规则 6 站在比其大一号的青蛙的背上。 青蛙希望最终能够全部移动到 D 上，并完成站队。

55、设河心有 m 片荷叶和 n 个石墩，请求出这队青蛙至多有多少只，在满 足站队和移动规则的前提下，能从A 过到 D。输入输入仅有两行，每一行仅包含一个整数和一个换行/ 回车符。第一行的数字为河心的石墩数 n ( 0<=n<=25),第二行为荷叶数 m (0<=m<=25)。 输出输出中仅包含一个数字和一个换行 / 回车符。该数字为在河心有 n 个石 墩和 m 片荷叶时，最多能够过河的青蛙的只数。Problem13 棋盘游戏 (shuttle)题目描述大小为 3 的棋盘游戏里有 3 个白色棋子， 3 个黑色棋子，和一个有 7 个 格子一线排开的木盒子。 3 个白棋子被放在一

56、头， 3个黑棋子被放在另一头， 中间的格子空着。初始状态 : WWW_BBB 目标状态 : BBB_WWW 在这个游戏里有两种移动方法是允许的：1. 你可以把一个棋子移到与它相邻的空格；2. 你可以把一个棋子跳过一个 (仅一个 )与它不同色的棋子到达空格。大小为N的棋盘游戏包括 N个白棋子，N个黑棋子，还有有2N+1个格子的 木盒子。这里是 3-棋盘游戏的解，包括初始状态，中间状态和目标状态： WWW BBBWW WBBB WWBW BB WWBWB B WWB BWB W BWBWBWBWBWB BW WBWB BWBW WBBWBWBW BWBWB WBWB BWWB BWBWWBB WBWWBBBW WWBBB WWW请编一个程序解大小为N的棋盘游戏（1 <= N <= 12）。要求用最少的移动步数实现。输入输入仅一个整数 N。输出用空格在棋盘的位置（位置从左到右依次为1,2,2N+1）表示棋盘的状态。输出棋盘的状态变换序列，每行 20个数 （除了最后一行 ）。输出的解还应当有最小的字典顺序 （即如果有多组移