NOIP基本程序题集.doc

基本程序题集For NOIP2007Billy.Linux NOIP是一个比较基础的比赛，大家都说NOIP是考察基本算法的熟练掌握，所以个人认为无论是普及组还是提高组，都要从最最基本的题做起，要达到：只要是简单题，编完就对不用编译；一般的题，写出来的都是对的运行后基本上是正确的。为了提高，于是做了一个基本程序题集，以便查找自己的不足之处。题集目录一、 贪心算法Problem1删数问题Problem2旅行家的预算Problem3线段覆盖Problem4背包问题Problem5任务调度Problem6果子合并Problem7射击竞赛Problem8任务安排Problem9最小差距二、 分治算法Problem1一元三次方程的解Problem2查找第k大元素Problem3麦森数Problem4逆序对个数Problem5寻找最近点对Problem6剔除多余括号Problem7赛程安排三、 搜索算法Problem1皇后问题Problem2八数码问题Problem3拼图Problem4质数方阵Problem5埃及分数Problem6字符串变换Problem7聪明的打字员Problem8 01序列Problem9生日蛋糕四、 图论算法Problem1一笔画问题Problem2 Car的旅行路线Problem3求割点与桥Problem4十字绣Problem5舞会Problem6休息中的小呆Problem7最优布线问题Problem8磁盘碎片整理Problem9说谎岛Problem10 01串问题Problem11海岛地图五、 数学问题Problem1数的划分Problem2最优分解方案Problem3出栈序列统计Problem4百事世界杯之旅Problem5电子锁Problem6堆塔问题Problem7取数游戏Problem8球迷购票Problem9 Fibonacci公约数Problem10传球问题Problem11约瑟夫问题Problem12青蛙过河Problem13棋盘游戏六、 数据结构Problem1火车栈Problem2括号表达式Problem3银河英雄传说Problem4矩形覆盖Problem5最短路径问题Problem6果子合并七、 字符串处理Problem1相对分子质量Problem2表达式求值Problem3侦探推理Problem4最长公共子串Problem5一元一次方程的解Problem6多项式乘法一、 贪心算法Problem1删数问题题目描述： 给定一正整数n(n的位数小于240)，现要删除数n中的s个数码，使其得到的新数最小，求这个最小数。输入 输入有两行，第一行为整数n，第二行即为s输出输出一行，即最小的那个数Problem2旅行家的预算 题目描述 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离i、每升汽油价格Pi（i=1，2，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。输入 输入第一行有5个数：D1，c，D2，P，N(前四个为实数，N为整数,N<=1000) 后面有N行，每行两个实数，分别表示对应的加油站离出发点的距离，与每升汽油的价格输出 输出仅一行，即最少花费Problem3线段覆盖题目描述 给定数轴上的n条线段(n<100)，每个线段有其端点ai、bi组成(-999<=ai<bi<=999)，由于有些线段会相互覆盖，所以求出至少去掉多少条线段，才能使剩下的所有线段之间互相没有内部公共点(若只是端点重合，则不是内部公共点)。输入 输入第一行为整数N，接下来有N行，分别描述每条线段输出 输出第一行为最少删除的线段数s 后面s行描述一个可行的删除方案，即删除那些线段Problem4背包问题题目描述 有一个贼在偷窃一家商店时发现有N件物品:第i件物品值Vi元，重Wi磅，(1in)，此处Vi和Wi都是整数。他希望带走的东西越值钱越好，但他的背包中最多只能装下W磅的东西(W为整数)，小偷可带走某个物品的一部分(只带走其中的几磅)，小偷应该带走哪几件东西，每件东西的重量是多少？输入 输入第一行为N(N<=10000)，后面N行描述每个物品，每行两个数，即为Vi与Wi输出输出第一行为大的最大价值，后面依次描述物品i应偷多少(如果没偷，则不输出，输出对应的i为升序)。Problem5任务调度题目描述 一个单位时间任务是个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间。给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序。该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1, 结束于时间2;。单处理器上具有期限和罚款的单位时间任务调度问题的输入如下: 1.包含n个单位时间任务的集合S=1,2,n; 2.n个取整的期限d1,dn,(1d,n),任务i要求在di前完成; 3.n个非负的权(或罚款)w1,wn。如果任务i没在时间di之前结束,则导致罚款wi; 要求找出S的一个调度,使之最小化总的罚款。输入 输入第一行为N(N<=1000)，后面N行每行两个数，即为对应的di与wi输出 输出最小总罚款Problem6果子合并Problem6果子合并题目描述 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。 输入 输入第一行为N(N<=1000)，第二行有N个整数，分别描述每个果子输出输出一个数即最小代价Problem7射击竞赛题目描述 射击的目标是一个由R*C(2RC1000)个小方格组成的矩形网格。每一列恰有2个白色的小方格和R-2个黑色的小方格。行从顶至底编号为1-R，列从左至右编号为1-C。射击者可射击C次。在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。如果存在正确的射击方法，则要求找到它。输入 输入第一行为R，C，后面R行每行C个数，如果为0则为白格，1则为黑格输出输出正确方案每行两个数即射击坐标，否则输出-1Problem8任务安排题目描述 一家工厂的流水线正在生产一种产品，这需要两种操作：操作A和操作B。每个操作只有一些机器能够完成。A型机器从输入库接受工件，对其施加操作A，得到的中间产品存放在缓冲库。B型机器从缓冲库接受中间产品，对其施加操作B，得到的最终产品存放在输出库。所有的机器平行并且独立地工作，每个库的容量没有限制。每台机器的工作效率可能不同，一台机器完成一次操作需要一定的时间。 给出每台机器完成一次操作的时间，计算完成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操作的时间总和的最小值（A操作必须在B操作之前完成）。Problem9最小差距题目描述 给定一些不同的一位数字，你可以从这些数字中选择若干个，并将它们按一定顺序排列，组成一个整数，把剩下的数字按一定顺序排列，组成另一个整数。组成的整数不能以0开头（除非这个整数只有1位）。 例如，给定6个数字，0,1,2,4,6,7，你可以用它们组成一对数10和2467，当然，还可以组成其他的很多对数，比如210和764，204和176。这些对数中两个数差的绝对值最小的是204和176，为28。 给定N个不同的09之间的数字，请你求出用这些数字组成的每对数中，差的绝对值最小的一对（或多对）数的绝对值是多少？输入 输入第一行包括一个数T（T1000），为测试数据的组数。每组数据包括两行，第一行为一个数N（2N10），表示数字的个数。下面一行为N个不同的一位数字。输出输出T行，每行一个数，表示第i个数据的答案。即最小的差的绝对值二、 分治法Problem1一元三次方程的解题目描述 有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。输入 输入仅一行，有四个数，依次为a、b、c、d输出输出也只有一行，即三个根(从小到大输出)Problem2查找第k大元素题目描述 有N个数，请找出其中第k大的数(N<=10000)输入 输入第一行为N、K，第二行有N个数输出输出第K大的数Problem3麦森数题目描述 形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。 任务：从文件中输入P（1000<P<3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）输入 输入只包含一个整数P（1000<P<3100000）输出 输出第一行是十进制高精度数2P-1的位数。第2-11行：十进制高精度数2P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）Problem4逆序对个数题目描述 给出一个数列an，如果存在i<j，但是ai>aj那么我们称ai与aj是一对逆序对，现要求求出数列an中逆序对的个数输入 输入第一行为整数N(N<=10000)，第二行有N个数，即为数列an输出输出仅一个数，即逆序对的个数Problem5寻找最近点对题目描述 给出平面内的N(N<=10000)个点，点两两都有一个距离，现要求出所有点对中距离最小的那一对输入 输入第一行为N，后面有N行，每行两个数分别描述每个点的横纵坐标输出输出一个数，即最近点对的距离Problem6剔除多余括号题目描述 键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价。输入 输入一行，即为表达式，长度小于250输出输出也一行，为剔出多余括号之后的表达式Problem7赛程安排题目描述 有n个编号为1到n 的运动员参加某项运动的单循环比赛，即每个运动员要和所有其他运动员进行一次比赛。试为这n个运动员安排一个比赛日程，使得每个运动员每天只进行一场比赛，且整个比赛在n-1天内结束。输入 输入一行，即为运动员人数n(n<=10000)输出输出一个n阶方阵A1.N,0.N-1(表示比赛日程)，当J0时，AI,J表示第I名运动员在第J天的比赛对手。三、 搜索算法Problem1皇后问题题目描述 在一N*N的棋盘中，摆上N个皇后，使其互不攻击，有多少种摆法(皇后攻击同行同列与同斜行的棋子)输入 输入一行，即整数N(N<=10)输出 输出一个数，即总方案数Problem2八数码问题题目描述 有一个3*3的方阵，其中有8个数，一个方格为空，可以通过移动方格将初始的方阵移动成其他的方阵输入 输入两个3*3的方阵，即为初始状态与目标状态，0代表空的方格输出输出最少的步数使初始方阵转换为目标方阵，如果无解则输出No SolutionProblem3拼图题目描述 这个拼图游戏要求将一些图形拼成一个正方形，图形的个数从1到5。图形不能旋转，拼的时候不能重叠，拼完后的正方形里面不能有隙。所有给定的图形都要使用。输入 输入第一行是一个整数n，表示图形的个数，范围从1到5。接下来有n个部分，每个部分的第一行是2个整数i和j，表示下面的i行j列用来描述一个图形。图形用0和1表示，1表示图形占有这个置，0表示不占有，中间没有空格。图形的长与宽都不超过5。根据图形给出的顺序给每个图形编号，从1开始，至多到5。保证数据无多解情况。输出 如果不能拼成一个正方形，就输出“No solution possible”；否则，输出一种拼的方案：一个正方形的数阵，每个位置上的数字是占有这个位置的图形的编号，中间没有空格。Problem4质数方阵题目描述 求一个5*5的方阵，满足如下要求： (1)每行每列的数字和为s (2)(1,1)上的数字为t (3)每个横行竖行斜行所形成的五位数都是质数 给定s,t求满足要求的方阵数输入 输入一行两个数即s，t输出 输出第一行为方案数，接下来按序输出所有方案(每个方案件都有一空行)Problem5埃及分数题目描述 在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。 如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。 对于一个分数a/b,表示方法有很多种，但是哪种最好呢？ 首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如： 19/45=1/3 + 1/12 + 1/180 19/45=1/3 + 1/15 + 1/45 19/45=1/3 + 1/18 + 1/30, 19/45=1/4 + 1/6 + 1/180 19/45=1/5 + 1/6 + 1/18. 最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。 给出a,b(0ab1000),编程计算最好的表达方式。输入 输入仅一行，即为N，表示有N组测试数据，每组测试数据为一行包含a,b(0ab1000)。输出输出N行，对应每组测试数据，对于每组测试数据输出若干个数，自小到大排列，依次是单位分数的分母。Problem6字符串变换题目描述已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:A1$ -> B1$A2$ -> B2$规则的含义为：在 A中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ 。例如：A$abcdB$xyz变换规则为：abc->xuud->yy->yz则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为： abcd->xud->xy->xyz共进行了三次变换，使得 A$ 变换为B$。输入 输入格式如下： A$ B$A1$ B1$ A2$ B2$ |-> 变换规则. . / 所有字符串长度的上限为 20。输出输出最短步数，若在10步（包含 10步）以内能将A$变换为B$，则输出最少的变换步数；否则输出"NO ANSWER!"Problem7聪明的打字员题目描述 阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程敲击键盘的总次数越少越好。 不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键:Swap0,Swap1,Up, Down, Left, Right，为了说明这6个键的作用，我们先定义录入区的6个位置的编号，从左至右依次为1，2，3，4，5，6。下面列出每个键的作用： Swap0：按Swap0，光标位置不变，将光标所在位置的数字与录入区的1号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的1号位置，则按Swap0键之后，录入区的数字不变； Swap1：按Swap1，光标位置不变，将光标所在位置的数字与录入区的6号位置的数字（左起第六个数字）交换。如果光标已经处在录入区的6号位置，则按Swap1键之后，录入区的数字不变； Up：按Up，光标位置不变，将光标所在位置的数字加1（除非该数字是9）。例如，如果光标所在位置的数字为2，按Up之后，该处的数字变为3；如果该处数字为9，则按Up之后，数字不变，光标位置也不变； Down：按Down，光标位置不变，将光标所在位置的数字减1（除非该数字是0），如果该处数字为0，则按Down之后，数字不变，光标位置也不变； Left：按Left，光标左移一个位置，如果光标已经在录入区的1号位置（左起第一个位置）上，则光标不动； Right：按Right，光标右移一个位置，如果光标已经在录入区的6号位置（左起第六个位置）上，则光标不动。 当然，为了使这样的键盘发挥作用，每次录入密码之前，录入区总会随机出现一个长度为6的初始密码，而且光标固定出现在1号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。 现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。输入 输入一行，含有两个长度为6的数，前者为初始密码，后者为目标密码，两个密码之间用一个空格隔开。输出输出仅一行，含有一个正整数，为最少需要的击键次数。Problem8 01序列题目描述 求指定长度满足下列要求的序列的个数： (1)全由01组成 (2)任意一段连续的子串没有连续出现3次(如：010101、001001001就不符合要求)输入 输入仅一个数，即序列长度输出输出仅一个数，即满足要求的序列总数Problem9生日蛋糕题目描述 要制作一个体积为N*pi的M层生日蛋糕，每层都是一个圆柱体。 设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > 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一笔画问题题目描述 给出一个图，求其欧拉回路（若没有回路，则求其欧拉路径），若不存在则输出No solution输入 输入的第一行为边数F(<=1024)，后面F行每行表示一条边（定点标号范围为1-500）输出输出一条合法的欧拉回路（路径），若有多条满足要求，输出其字典序最小的那一个。Problem2 Car的旅行路线题目描述 住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。 那么Car应如何安排到城市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求割点与桥题目描述 给定一个图，求其割点与桥输入 第一行有两个整数，n、e，即点数与边数 后面e行，每行两个整数v1、v2，表示点v1与v2相连输出 首先输出所有割点，每行输出一个 然后输出所有桥，每行一条(不用考虑顺序)Problem4十字绣题目描述 布是一个n*m的网格，线只能在网格的顶点处才能从布的一面穿到另一面。每一段线都覆盖一个单位网格的两条对角线之一，而在绣的过程中，一针中连续的两段线必须分处布的两面。给出布两面的图案(实线代表该处有线,虚线代表背面有线)，问最少需要几针才能绣出来？一针是指针不离开布的一次绣花过程。输入 输入第1行两个数N和M(1<=N,M<=200)。 接下来N行每行M个数描述正面。 再接下来N行每行M个数描述反面。 每个格子用.（表示空）,/（表示从右上角连到左下角）,（表示从左上角连到右下角）和X（表示连两条对角线）表示。输出输出一个数，最少要用的针数Problem5舞会题目描述 一个舞会邀请n个人，这n个人每一个人都有一个小花名册，名册里面写着他所愿意交流的人的名字。比如说在A的人名单里写了B，那么表示A愿意与B交流；但是B的名单里不见的有A，也就是说B不见的想与A交流。但是如果A愿意与B交流，B愿意与C交流，那么A一定愿意与C交流。也就是说交流有传递性。现在觉得需要将这n个人分为m组，要求每一组的任何一人都愿意与组内其他人交流。并求出一种方案以确定m的最小值是多少。注意：自己的名单里面不会有自己的名字。输入 输入第一行一个数n。接下来n行，每i+1行表示编号为i的人的小花名册名单，名单以0结束。1<=n<=200。输出输出即m的最小值Problem6休息中的小呆题目描述 NOIP备战之际，小呆正在悠闲（欠扁）地玩一个叫“最初梦想”的游戏。游戏描述的是一个叫pass的有志少年在不同的时空穿越对抗传说中的大魔王chinesesonic的故事。小呆发现这个游戏的故事流程设计得很复杂，它有着很多的分支剧情，但不同的分支剧情是可以同时进行的，因此游戏可以由剧情和剧情的结束点组成，某些剧情必须要在一些特定的剧情结束后才能继续发展。为了体验游戏的完整性，小呆决定要看到所有的分支剧情完成所有的任务。但这样做会不会耽误小呆宝贵的睡觉时间呢？所以就请你来解决这个问题了。输入 输入会给你一个剧情流程和完成条件的列表，其中第一行有一个数n（0<n<100），表示总共有n个剧情结束点，第二行一个数m(0<m<=120)，表示由m个不同的剧情，下面的m行中每行有三个数i0<i<=100),j0<j<=100),k0<k<=1000)，表示从剧情结束点i必须完成一个耗费时间为k的剧情才能到达剧情结束点j。注意，这m行中出现的1不是剧情结束点而是游戏的开始，而n+1表示游戏结束。输出输出第一行为一个数，即你要告诉小呆完成整个游戏至少需要多少时间，第二韩有若干个数，即要经过的所有可能的剧情结束点（按升序输出）。Problem7最优布线问题题目描述 校园里有n台计算机，要将它们用数据线连接起来。由于计算机所处的位置不同，连接2台计算机的费用往往是不同的。如果将每2 台计算机都用数据线连接，势必造成浪费。为了节省费用，可以采用数据的间接传输手段，即一台计算机可以间接通过若干台计算机(作为中转)来实现与另一台计算机的连接。如何用最少费用连接n台计算机。输入 输入数据。第一行有1个正整数n，表示计算机数。此后n行，每行有n个正整数。第x+1行，第y列的正整数表示直接连接第x台计算机和第y台计算机的费用。输出 输出最小费用 Problem8磁盘碎片整理题目描述 出于最高安全性考虑，司令部采用了特殊的安全操作系统。该系统采用一个特殊的文件系统。在这个文件系统中所有磁盘空间都被分配了相同尺寸的N块，用整数1到N表识，每个文件占用磁盘上任意区域的一块或多块存储区，未被文件占用的存储块被认为是可以使用的。如果文件存储在磁盘上自然连续的存储块中，则能被以最快的速度读出。 因为磁盘是均匀转动的，所以存取上面的不同的存储快需要的时间也不同。读取磁盘开头处的存储比读取磁盘结尾处的存储块快。根据以上现象，我们事先将文件按其存取频率的大小用整数1到K标识。按文件在磁盘上最佳的存储方法，1号文件将占用1，2，S1的存储块，2号文件占用S1+1,S1+2S1+S2的存储块，依次类推。为了将文件以最佳形式存储在磁盘上，需要执行存储酷块移动操作。操作后，原空间将被释放，新空间将被占用。 问对于一个文件序列，最少需要多少次移动操作才能以最佳方式存储到磁盘上输入 输入第一行包含两个整数N，K，接下来K行每行描述一个文件，第一个数为Si，表示其存储块数量，后面有Si个整数，每个整数之间用空格隔开，表示该文件按自然顺序在磁盘上占用的存储块标识，所有这些数都介于1和N之间，包括1和N。 所有磁盘空间的表识都不相同输出输出一个数，即最小移动次数Problem9说谎岛题目描述 哥仑布在到达美州后，发现了一个奇特的岛屿。这个岛屿上的人狡猾且喜欢说谎，由于完全的谎言较易为人所识破，所以为了更加能够迷惑别人，他们的言语往往是半真半假的。 由于对于环境的不熟悉，哥仑布有许多问题要请教岛上的居民。当然他已经知道了岛上居民的这一说谎习俗。 幸好，哥仑布的所有问题都只需回答“是”或者“否”，这样便免去了许多繁复。假设哥仑布询问了N个居民，对于每个居民只问两个问题，每个居民只需对于每个问题回答“是”或“否”。根据居民的习俗，可以断定两个回答中必有一个是正确的，而另一个是错误的。同一个问题可以反复问多人。 哥仑布根据这N个人的回答，需要整理推断出他所有问题的答案。但这一过程实在太复杂与困难了，因此希望你能够编程求出所有可能答案的种数。输入 输入第一行是两个整数N（1N10000）、M（1M200），以空格分隔。分别表示询问了N人，共有M个问题。整个输入文件共N+1行。 第i+1行共有四个整数a,b,c,d，以空格分隔。表示第i个人对于第a个问题的答案是b, 对于第c个问题的答案是d。其中1a,cM。b和d为0时表示答案为“否；”为1时表示答案为“是”。输出若不可能推出任何结果，即无解，输出“NO ANSWER”；否则输出可能答案组的个数。Problem10 01串问题题目描述 给定7个整数N,A0,B0,L0,A1,B1,L1，要求设计一个01串S=s1s2sisN，满足： 1.si=0或si=1，1<=i<=N； 2.对于S的任何连续的长度为L0的子串sjsj+1sj+L0-1(1<=j<=N-L0+1)，0的个数大于等于A0且小于等于B0; 3.对于S的任何连续的长度为L1的子串sjsj+1sj+L1-1(1<=j<=N-L1+1)，1的个数大于等于A1且小于等于B1; 例如，N=6,A0=1,B0=2,L0=3,A1=1,B1=1,L1=2，则存在一个满足上述所有条件的01串S=010101。输入 输入仅一行，有7个整数，依次表示N,A0,B0,L0,A1,B1,L1（3<=N<=1000，1<= A0<=B0<=L0<=N，1<=A1<=B1<=L1<=N），相邻两个整数之间用一个空格分隔。输出输出仅一行，若不存在满足所有条件的01串，则输出一个整数-1，否则输出一个满足所有条件的01串。Problem11海岛地图题目描述 给出一个(h*w)的海岛地图，其中图中1表示陆地，0表示水域，求所有岛屿中，面积最大的一个岛屿输入输入第一行为w，h(<=100)，表示图的长与宽后面有w行，每行有一个长为h的01串，用来描述整个地图输出输出仅一个数，即最大的海岛面积五、 数学问题Problem1数的划分题目描述 将整数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出栈序列统计题目描述 栈是常用的一种数据结构,有n令元素在栈顶端一侧等待进栈,栈顶端另一侧是出栈序列.你已经知道栈的操作有两种:push和pop,前者是将一个元素进栈,后者是将栈顶元素弹出.现在要使用这两种操作,由一个操作序列可以得到一系列的输出序列.请你编程求出对于给定的n,计算并输出由操作数序列1,2,n,经过一系列操作可能得到的输出序列总数.输入 输入一个整数n(1<=n<=50)输出 输出一个整数，即可能输出序列的总数目。 Problem4百事世界杯之旅题目描述 每个瓶盖上有一个球星的名字，有N个不同的球星，平均情况下，要买多少瓶饮料才能集齐所有名字输入 输入一个数N(<=33)输出 输出平均情况下的瓶数，若为整数则直接输出，若为分数，则以真分数形式输出，格式如下： b a- cProblem5电子锁题目描述 某机要部门安装了电子锁。m个工作人员每人发一张磁卡，卡上有开锁的密码特征，为了保证安全，规定至少n个人同时使用各自的磁卡才能将锁打开。现在需要你计算一下，电子锁上至少要有多少种特征，每个人的磁卡上至少要有几种特征。同时输出分配方案。输入 输入仅一行，有两个数即m(m<=7)，n(<=m且<=4)输出 输出第一行为两个数，既电子锁上的特征数，与磁卡上的特征数后面n行按字典序数出一个01序列，表识每个人磁卡上的拥有的特征，1表识有，0表示没有。Problem6堆塔问题题目描述 有n个边长为一的正立方体，在一个宽为1的轨道上堆塔，但它本身不能分离。 堆塔时底层必须有支撑，求对于n各正方体，又多少种方案输入 输入仅一行n(n<=100)输出 输出也只一行，即总方案数Problem7取数游戏题目描述 给出正整数n(<=1000000)和k(<n)，然后按下列方法取数:(n=16,k=4) 1: 取1 剩 15 2: 取2 剩 13 3: 取4 剩 9 4: 取8 剩 1 第五次取不够，加上k个，现在共5个 5: 取1 剩 4 6: 取2 剩 2 第七次取不够，加上k个，现在共6个 7: 取1 剩 5 8: 取2 剩 3 第九次取不够，加上k个，现在共7个 9: 取1 剩 6 10: 取1 剩 4 11: 取1 剩 0 取完共取11次输入 输入仅一行，即n，k输出若取得完，则输出取的次数，否则输出ErrorProblem8球迷购票题目描述 球迷手上有100元与50元的钞票，每张票50元，现在有m+n个球迷买票(m个手上持50元的，n个手上持100元的)，一开始售票员手上有钱，有多少排队方案可以不出现没有钱找的局面输入 输入仅一行即m，n(m,n<=5000)输出 输出有一行，即总得方案数Problem9 Fibonacci公约数题目描述 给出两个fibonacci数，求一个最大的fibonacci数，满足这个数是他们的最大公约数输入 输入有两行，分别是两个Fibonacci数(<=102000)输出即输出他们的Fibonacci公约数Problem10传球问题题目描述 Grant老师常和小朋友们一起玩一种传球游戏。游戏是这样进行的： 一群小朋友分成两组，每组n人，围成一个圈。每一个小朋友都有一个编号(1.n之间)，这个编号在其所在组中是唯一的。 游戏开始之前，Grant老师会发给每个小朋友一个球，球上也有编号(1.n之间)，并且一个组中的球不会有两个相同编号。然后，所有小朋友必须闭上眼睛，游戏开始。随着Grant老师口中的哨子发出的节奏，每个小朋友都用一只手把球传到右边，而用另一只手接左边的来球。 突然，Grant老师的哨子停了，关键的时刻到了。小朋友马上睁开眼睛，开始与同组的小朋友之间进行传球，争取以最短的时间把球传到位。传到位是指一个组中的每一个小朋友手上的球的编号与他自己的编号相同。最后获胜的就是那个最先把球传到位的组。如果一旦哪方出现传球失误(球没被接到而落地)，或犯规（一个人手上拿两个或两个以上的球）这一组就被判输。 这个游戏非常有趣，小朋友们玩了许多次。他们总结出一条经验：总是两个人之间对传。也就是说，不会出现a把球传给b，而b没有把球传给a的这种情况。这样可以避免小朋友之间的失误与犯规。不过还有个关键问题就是怎么传。究竟应该把手上的球传给谁？ 现在需要你编一个程序来帮助小朋友们确定传球方法。你的程序首先需要计算出从一种初始状态开始： 子问题 1：至少需要几次对传才能将球传到位。 子问题2：至少需要多少时间才能将球传到位。每一个时间单位一个小朋友可以不做任何动作，也可以与另外一个小朋友之 间进行对传。 注意有些对传可以同时进行。比如小朋友1与小朋友2之间的对传和小朋友3与小朋友4之间的对传就可以在一个时间单位之内完成，但是被计作两次对传。输入： 输入第一行是一个整数 n (2<=n<=20000)。接下来有n 行，每行一个整数(1.n)，其中第(i+1)行的整数表示i号小朋友手上的球的编号。输出：输出只有二行，每行一个整数，分别表示子问题1和子问题2的解。Problem11约瑟夫问题题目描述 n个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人最开始的编号。输入 输入一个正整数n，表示人的个数。输入数据保证数字n不超过100位。输出 输出一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。Problem12青蛙过河题目描述 大小各不相同的一队青蛙站在河左岸的石墩（记为A）上，要过到对岸的石墩(记为D)上去。河心有几片菏叶(分别记为Y1Ym)和几个石墩(分别记为S1Sn)。 青蛙的站队和移动方法规则如下： 1每只青蛙只能站在荷叶、石墩，或者仅比它大一号的青蛙背上（统称为合法的落脚点）； 2一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点； 3青蛙允许从左岸A直接跳到河心的石墩、荷叶和右岸的石墩D上，允许从河心的石墩和荷叶跳到右岸的石墩D上； 4青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动； 5青蛙在离开左岸石墩后，不能再返回左岸；到达右岸后，不能再跳回； 6假定石墩承重能力很大，允许无论多少只青蛙都可呆在上面。但是，由于石墩的面积不大，至多只能有一只青蛙直接站在上 面，而其他的青蛙只能依规则1落在比它大一号的青蛙的背上。 7荷叶不仅面积不大，而且负重能力也有限，至多只能有一只青蛙站在上面。 8每一步只能移动一只青蛙，并且移动后需要满足站队规则； 9在一开始的时候，青蛙均站在A上，最大的一只青蛙直接站在石墩上，而其它的青蛙依规则6站在比其大一号的青蛙的背上。 青蛙希望最终能够全部移动到D上，并完成站队。 设河心有m片荷叶和n个石墩，请求出这队青蛙至多有多少只，在满足站队和移动规则的前提下，能从A过到D。输入 输入仅有两行，每一行仅包含一个整数和一个换行/回车符。第一行的数字为河心的石墩数n（0<=n<=25），第二行为荷叶数m（0<=m<=25）。 输出 输出中仅包含一个数字和一个换行/回车符。该数字为在河心有n个石墩和m片荷叶时，最多能够过河的青蛙的只数。Problem13棋盘游戏题目描述 大小为3的棋盘游戏里有3个白色棋子，3个黑色棋子，和一个有7个格子一线排开的木盒子。3个白棋子被放在一头，3个黑棋子被放在另一头，中间的格子空着。 初始状态: WWW_BBB 目标状态: BBB_WWW在这个游戏里有两种移动方法是允许的：1. 你可以把一个棋子移到与它相邻的空格；2. 你可以把一个棋子跳过一个(仅一个)与它不同色的棋子到达空格。 大小为N的棋盘游戏包括N个白棋子，N个黑棋子，还有有2N+1个格子的木盒子。 这里是3-棋盘游戏的解，包括初始状态，中间状态和目标状态： WWW BBBWW WBBBWWBW BBWWBWB BWWB BWBW BWBWB WBWBWBBW WBWBBWBW WBBWBWBW BWBWB WBWB BWWB BWBWWBB WBWWBBBW WWBBB WWW请编一个程序解大小为N的棋盘游戏(1 <= N <= 12)。要求用最少的移动步数实现。输入 输入仅一个整数N。输出 用空格在棋盘的位置(位置从左到右依次为1, 2, ., 2N+1)表示棋盘的状态。输出棋盘的状态变换序列，每行20个数(除了最后一行)。 输出的解还应当有最小的字典顺序(即如果有多组移动步数最小的解，输出第一个数最小的解；如果还有多组，输出第二个数最小的解；.)。六、 数据结构Problem1火车栈题目描述 有一个车站，每天都会有N辆车进站，进站按从1到N的顺序进站。现在车站的站长想让这些火车按照特定的顺序出站，问可以做到吗？ 当N为5时，出站顺序若为1 2 3 4 5，可以做到，但是顺序若为5 4 1 2 3，则不行。 我们可以把火车进站就是压栈，出站则是弹栈。输入 一个N，在1000之内，下接一些出站序列，当读到一个0时，则这个测试数据结束。输出对每个序列输出一行“Yes”或“No”。Problem2括号表达式题目描述 一个由左右括号(,),组成的表达式，判断表达式是否合法，其中规则如下： (1)空串合法 (2)如果A合法，那么A,(A),A都合法 (3)如果A，B都合法，那么AB合法输入 输入有若干行，每行一个表达式输出输出对于每一个表达式给出判断，行数与输入一样，每行对应每一个表达式，如果为合法则输出Yes，否则输出NoProblem3银河英雄传说题目描述 公元五八一年，地球居民迁移至金牛座第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, , 30000。之后，他把自己的战舰也依次编号为1, 2, , 30000，让第i号战舰处于第i列(i = 1, 2, , 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。 然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。 在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。 最终的决战已经展开，银河的历史又翻过了一页输入 输入的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。 以下有T行，每行有一条指令。指令有两种格式： 1.M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰 队调动指令，并且保证第i号战舰与第j号战舰不在同一列。 2.C i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。输出 输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理： 如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息； 如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置 的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。Problem4矩形覆盖题目描述 给出平面上n个矩形，求它们所形成的图形的周长和面积输入 输入第一行为n(n<=5000) 后面n行米行描述一个矩形，分别为4个整数(每两个描述一个点，两个点即为矩形的对点)，坐标值均在-10000，10000之内输出输出有两行，第一行为图形的周长，第二行为面积Problem5最短路径问题题目描述 求一个有向图的起点到终点的最短路径输入 第一行有四个数n,e,s,t分别表示点数，边数，起点，终点(n<=5000) 后面e行，每行3个数分别表示边的起点，终点，与权(有可能出现两条起点终点相同的边)输出输出s到t的最短路径长度Problem6果子合并题目描述 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆