MB（算法设计与分析）

木板墙 考古学家在人迹罕至的一块平地上发现了由一堆木板拼成的墙。令人惊奇的是这些木板的宽度都相同！地下的部分都已腐烂，而地上的部分也有高有低，甚至有的地方根本没有木板，所以考古学家决定带走面积最大的长方形回去研究。 输入： 首先是整数n(1<=n<=100000)，表示木板的块数。接下来是n个整数h1,...,hn, 其中0<=hi<=1000000000，它们按照从左到右的顺序表示木板的高度。每块木板的宽度都是1。 最后一个0表示程序的结束。 输出： 其中最大长方形的面积。 测试输入关于“测试输入”的帮助 期待的输出关于“期待的输出”的帮助 时间限制关于“时间限制”的帮助 内存限制关于“内存限制”的帮助 额外进程关于“{$a} 个额外进程”的帮助 测试用例 1 以文本方式显示 3 2000 2000 2000↵ 7 1 2 5 6 1 3 3↵ 0↵ 以文本方式显示 6000↵ 10↵ 1秒 64M 0

符号三角形问题.txt

输入:n (1<n<=27). 输出不同方案的个数. 注意：纯打表必和谐掉，不信就试试；有限打表，你懂的。 测试输入关于“测试输入”的帮助 期待的输出关于“期待的输出”的帮助 时间限制关于“时间限制”的帮助 内存限制关于“内存限制”的帮助 额外进程关于“{$a} 个额外进程”的帮助 测试用例 1 以文本方式显示 2↵ 3↵ 以文本方式显示 0↵ 4↵ 1秒 64M 0

整除15问题

给定一个只包含数字 [0..9] 的字符串，求使用字符串中的某些字符，构造一个能够被15整除的最大整数。注意，字符串中的每个字符最多只能使用一次。 输入：程序从标准输入读入数据，每行数据由一串数字组成，长度为1到1000。 输出：针对每一行输入，输出一个结果，每个结果占一行。如果无法构造出能够被15整除的整数，请输出impossible。 测试输入关于“测试输入”的帮助 期待的输出关于“期待的输出”的帮助 时间限制关于“时间限制”的帮助 内存限制关于“内存限制”的帮助 额外进程关于“{$a} 个额外进程”的帮助 测试用例 1 以文本方式显示 1↵ 01431↵ 103↵ 以文本方式显示 impossible↵ 43110↵ 30↵ 1秒 64M 0

快算24（算法设计与分析）

一副牌，除了大小王之外还有52张，从1到13每个数目各有四张。要求设计一个程序，对于任意给出52张牌中的四张，运用＋－×÷四种运算来判断能否每个数只能用一次，但不能不用，算出24来。注意，给出的4个数是无序的。 测试输入关于“测试输入”的帮助 期待的输出关于“期待的输出”的帮助 时间限制关于“时间限制”的帮助 内存限制关于“内存限制”的帮助 额外进程关于“{$a} 个额外进程”的帮助 测试用例 1 以文本方式显示 1 1 1 1↵ 2 3 4 1↵ 7 2 1 1↵ 以文本方式显示 no↵ yes↵ yes↵ 1秒 64M 0

DP（算法设计与分析）

对于由从1到N (1 <= N <= 39)这N个连续的整数组成的集合来说，我们有时可以将集合分成两个部分和相同的子集合。 例如，N=3时，可以将集合{1, 2, 3} 分为{1,2}和{3}。此时称有一种方式（即与顺序无关）。 N=7时，共有四种方式可以将集合{1, 2, 3, ..., 7} 分为两个部分和相同的子集合： {1,6,7} 和 {2,3,4,5} {2,5,7} 和 {1,3,4,6} {3,4,7} 和 {1,2,5,6} {1,2,4,7} 和 {3,5,6} 输入：程序从标准输入读入数据，只有一组测试用例。如上所述的N。 输出：方式数。若不存在这样的拆分，则输出0。 测试输入关于“测试输入”的帮助 期待的输出关于“期待的输出”的帮助 时间限制关于“时间限制”的帮助 内存限制关于“内存限制”的帮助 额外进程关于“{$a} 个额外进程”的帮助 测试用例 1 以文本方式显示 7↵ 以文本方式显示 4↵ 1秒 64M 0

DP或贪心(算法设计与分析）

小游戏 阿良很喜欢玩计算机游戏，特别是战略游戏，但是有时他不能尽快找到解所以常常感到很沮丧。现在面临如下问题：他必须在一个中世纪的城堡里设防，城堡里的道路形成一棵无向树。要在结点上安排最少的士兵使得他们可以看到所有边。你能帮助他吗？ 你的任务是给出士兵的最少数目。 输入包含多组数据。每组数据表示一棵树，在每组数据中： 第一行是结点的数目。 接下来的几行，每行按如下格式描述一个结点： 结点标识符 : ( 道路的数目 ) 结点标识符1 结点标识符2 ...... 结点标识符道路的数目 或者 结点标识符 : (0) 对于 n (0<n<=1500) 个结点，结点标识符是一个从 0 到 n - 1 的整数。每条边在测试用例中只出现一次。 对于每组数据，各给出一个整数表示士兵的最少数目. 测试输入关于“测试输入”的帮助 期待的输出关于“期待的输出”的帮助 时间限制关于“时间限制”的帮助 内存限制关于“内存限制”的帮助 额外进程关于“{$a} 个额外进程”的帮助 测试用例 1 以文本方式显示 4↵ 0:(1) 1↵ 1:(2) 2 3↵ 2:(0)↵ 3:(0)↵ 5↵ 3:(3) 1 4 2↵ 1:(1) 0↵ 2:(0)↵ 0:(0)↵ 4:(0)↵ 以文本方式显示 1↵ 2↵

油井问题（算法设计与分析作业）

主油管道为东西向，确定主油管道的南北位置，使南北向油井喷油管道和最小。要求线性时间完成。 1<= 油井数量 <=2 000 000 输入要求： 输入有油井数量行，第 K 行为第 K 油井的坐标 X ,Y 。其中， 0<=X<2^31,0<=Y<2^31 。 输出要求： 输出有一行， N 为主管道最优位置的最小值 注意：用快排做的不给分！！ 友情提示：可以采用while(scanf("%d,%d",&x,&y) != EOF)的数据读入方式。 测试输入关于“测试输入”的帮助 期待的输出关于“期待的输出”的帮助 时间限制关于“时间限制”的帮助 内存限制关于“内存限制”的帮助 额外进程关于“{$a} 个额外进程”的帮助 测试用例 1 以文本方式显示 41,969978↵ 26500,413356↵ 11478,550396↵ 24464,567225↵ 23281,613747↵ 491,766290↵ 4827,77476↵ 14604,597006↵ 292,706822↵ 18716,289610↵ 5447,914746↵ 以文本方式显示 597006↵ 1秒 64M 0

矩阵链乘问题（算法设计与分析）

矩阵链乘问题 输入： 共两行 第一行 N （ 1<=N<=100 ），代表矩阵个数。 第二行有 N+1 个数，分别为 A1 、 A2 ...... An+1 （ 1<=Ak<=2000）， Ak 和 Ak+1 代表第 k 个矩阵是个 Ak X Ak+1 形的。 输出： 共两行 第一行 M ，为最优代价。注：测试用例中 M 值保证小于 2^31 第二行为最优顺序。如 (A1((A2A3)A4)) ，最外层也加括号。 注意:测试用例已经保证了输出结果唯一,所以没有AAA的情况.

实现简单的文件系统

实验内容： 通过对具体的文件存储空间的管理、文件的物理结构、目录结构和文件操作的实现，加深对文件系统内部功能和实现过程的理解。 要求： 1.在内存中开辟一个虚拟磁盘空间作为文件存储器，在其上实现一个简单的单用户文件系统。在退出这个简单的文件系统时，将该虚拟文件系统保存到磁盘上，以便下次再将它恢复到内存的虚拟磁盘空间中。 2.提供以下操作： •new：建立一个新的简单文件系统； •sfs：打开一个简单文件系统； •exit：退出打开的简单文件系统； •mkdir：创建子目录； •rmdir：删除子目录； •ls：显示目录； •cd：更改当前目录； •create：创建文件； •open：打开文件； •close：关闭文件； •read：读文件； •write：写文件； •delete：删除文件。

磁盘调度模拟

编写一个磁盘调度程序，模拟操作系统对磁盘的调度。 实验目的： 本实验要求学生独立设计并实现磁盘调度模拟程序，以加深对磁盘调度特点和各种磁盘调度算法的理解。 实验要求： 　　可以随机输入磁道请求序列，当前磁头位置和磁头移动方向，支持先来先服务、最短寻道时间优先、扫描、循环扫描调度算法，能够输出磁头移动经过的磁道序列。具体信息见测试用例格式说明。 测试用例格式如下： 输入： 磁盘调度算法 　　　　当前磁头位置 　　　　磁头移动方向 　　　　磁道请求序列（磁道1,磁道2,磁道3,...) 　　　　其中： 　　　　(1) 调度算法选项为： 1----先来先服务 2----最短寻道时间优先 3----扫描法(SCAN) 4----循环扫描法(C-SCAN) 　　　　(2) 磁头移动方向选项为： 　　　　　　　　1----向磁头号增大方向移动 　　　　　　　　0----向磁头号减小方向移动 输出： 磁头移动经过的磁道序列（磁道1，磁道2，磁道3） 磁头移动经过的总磁道数