《基本程序题集》由会员分享，可在线阅读，更多相关《基本程序题集（35页珍藏版）》请在金锄头文库上搜索。
1、基本程序题集 NOIP是一个比较基础的比赛，大家都说NOIP是考察基本算法的熟练掌握，所以个人认为无论是普及组还是提高组，都要从最最基本的题做起，要达到：只要是简单题，编完就对不用编译；一般的题，写出来的都是对的运行后几本上是正确的。为了提高，于是做了一个基本程序题集，以便查找自己的不足之处。题集目录一、 贪心算法Problem1删数问题Problem2旅行家的预算Problem3线段覆盖Problem4背包问题Problem5任务调度Problem6果子合并Problem7射击竞赛Problem8任务安排Problem9最小差距二、 分治算法Problem1一元三次方程的解Problem2查
2、找第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磁盘碎片整
3、理Problem9说谎岛Problem10 01串问题Problem11海岛地图五、 数学问题Problem1数的划分Problem2最优分解方案Problem3出栈序列统计Problem4百事世界杯之旅Problem5电子锁Problem6堆塔问题Problem7取数游戏Problem8球迷购票Problem9 Fibonacci公约数Problem10传球问题Problem11约瑟夫问题Problem12青蛙过河Problem13棋盘游戏六、 数据结构Problem1火车栈Problem2括号表达式Problem3银河英雄传说Problem4矩形覆盖Problem5最短路径问题Proble
4、m6果子合并七、 字符串处理Problem1相对分子质量Problem2表达式求值Problem3侦探推理Problem4最长公共子串Problem5一元一次方程的解Problem6多项式乘法一、 贪心算法Problem1删数问题(cutnum)题目描述： 给定一正整数n(n的位数小于240)，现要删除数n中的s个数码，使其得到的新数最小，求这个最小数。输入 输入有两行，第一行为整数n，第二行即为s输出输出一行，即最小的那个数Problem2旅行家的预算(travel)题目描述 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱
5、的量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线段覆盖(sequence)题目描述 给定数轴上的n条线段(n100)，每个线段有其端点ai、bi组成(-999=aibi=999)，由于有些线
6、段会相互覆盖，所以求出至少去掉多少条线段，才能使剩下的所有线段之间互相没有内部公共点(若只是端点重合，则不是内部公共点)。输入 输入第一行为整数N，接下来有N行，分别描述每条线段输出 输出第一行为最少删除的线段数s 后面s行描述一个可行的删除方案，即删除那些线段Problem4背包问题(cheaf)题目描述 有一个贼在偷窃一家商店时发现有N件物品:第i件物品值Vi元，重Wi磅，(1in)，此处Vi和Wi都是整数。他希望带走的东西越值钱越好，但他的背包中最多只能装下W磅的东西(W为整数)，小偷可带走某个物品的一部分(只带走其中的几磅)，小偷应该带走哪几件东西，每件东西的重量是多少？输入 输入第一
7、行为N,W(N=10000)，后面N行描述每个物品，每行两个数，即为Vi与Wi输出输出第一行为大的最大价值。 Problem5任务调度题目描述 一个单位时间任务是个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间。给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序。该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1, 结束于时间2;。单处理器上具有期限和罚款的单位时间任务调度问题的输入如下: 1.包含n个单位时间任务的集合S=1,2,n; 2.n个取整的期限d1,dn,(1d,n),任务i要求在di前完成; 3.n个非负的权(
8、或罚款)w1,wn。如果任务i没在时间di之前结束,则导致罚款wi; 要求找出S的一个调度,使之最小化总的罚款。输入 输入第一行为N(N=1000)，后面N行每行两个数，即为对应的di与wi输出 输出最小总罚款Problem6果子合并Problem6果子合并题目描述 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬
9、回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。 输入 输入第一行为N(N=1000)，第二行有N个整数，分别描述每个果子输出输出一个数即最小代价Problem7射击竞赛题目描述 射击的目标是一个由R*C(2RC1000)个
10、小方格组成的矩形网格。每一列恰有2个白色的小方格和R-2个黑色的小方格。行从顶至底编号为1-R，列从左至右编号为1-C。射击者可射击C次。在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。如果存在正确的射击方法，则要求找到它。输入 输入第一行为R，C，后面R行每行C个数，如果为0则为白格，1则为黑格输出输出正确方案每行两个数即射击坐标，否则输出-1Problem8任务安排(job)题目描述 一家工厂的流水线正在生产一种产品，这需要两种操作：操作A和操作B。每个操作只有一些机器能够完成。A型机器从输入库接受工件，对其施加操作A，得到的中间产
11、品存放在缓冲库。B型机器从缓冲库接受中间产品，对其施加操作B，得到的最终产品存放在输出库。所有的机器平行并且独立地工作，每个库的容量没有限制。每台机器的工作效率可能不同，一台机器完成一次操作需要一定的时间。 给出每台机器完成一次操作的时间，计算完成A操作的时间总和的最小值，和完成B操作的时间总和的最小值。输入 输入第一行 三个用空格分开的整数： N，工件数量 (1=N=1000) M1，A型机器的数量 (1=M1=30) M2，B型机器的数量 (1=M2=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。输入 输入仅一行，有四个数，依次为a、b、c、d输出
12、输出也只有一行，即三个根(从小到大输出)Problem2查找第k大元素(findk)题目描述 有N个数，请找出其中第k大的数(N=10000)输入 输入第一行为N、K，第二行有N个数输出输出第K大的数Problem3麦森数(mason)题目描述 形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。 任务：从文件中输入P（1000P3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）输入 输入只包含一个整数P（1000P3100000）输出 输出第一行是十进制高精度数2P-1的位数。第2-11行：十进制高精度数2P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）Problem4逆序对个数(sort)题目描述 给出一个
