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）
磁头移动经过的总磁道数
实现请求页式存储管理模拟程序
编写一个请求页式存储管理模拟程序，通过对页面置换过程的模拟，加深对请求页式存储管理方式基本原理及实现过程的理解。
要求：
1. 从键盘输入页面访问序列及分配给进程的内存块数；
2. 分别采用OPT、FIFO和LRU算法进行页面置换（说明：对于OPT算法，在有多个页面可选的情况下，先淘汰较早进入的页面）。
3. 计算缺页次数及缺页率。
测试用例格式如下：
输入：
算法（1--OPT，2--FIFO，3--LRU）
内存块数
页面序列（页面1,页面2,页面3,...)
输出：
页面变化时内存块装入页面列表1-是否命中/页面变化时内存块装入页面列表2-是否命中/...
缺页次数
其中：
页面变化时内存块装入页面列表：内存块1装入页面,内存块2装入页面,内存块3装入页面...，未装入任何页面时由"-”表示
是否命中：1-命中，0-缺页
实现动态分区分配模拟程序
实验内容：
编写一个动态分区分配算法模拟程序，加深对动态分区存储管理方式及其实现过程的理解。
要求：
1.空闲分区通过空闲区链进行管理，在内存分配时，优先考虑低地址部分的空闲区。
2.分别采用首次适应算法、最佳适应算法和最坏适应算法模拟内存空间的动态分配与回收，每次分配和回收后显示出空闲区链的详细情况（说明：在申请不成功时，需要打印当前内存的占用情况信息）。
3.进程对内存空间的申请和释放可由用户自定义输入。
4.参考请求序列如下：
(1) 初始状态下可用内存空间为640KB；
(2) 进程1申请130KB；
(3) 进程2申请60KB；
(4) 进程3申请100KB；
(5) 进程2释放60KB；
(6) 进程4申请200KB；
(7) 进程3释放100KB；
(8) 进程1释放130KB；
(9) 进程5申请140KB；
(10) 进程6申请60KB；
(11) 进程7申请50KB；
(12) 进程6释放60KB。
测试用例格式如下：
输入：
动态分区分配算法选择
可用内存空间容量
序号/进程号/申请或释放操作/申请或释放的容量
其中：
(1) 动态分区分配算法：1----首次适应，2----最佳适应，3----最坏适应
(2) 申请或释放操作： 1----申请操作，2----释放操作
输出：
序号/内存空间状态1/内存空间状态2......
内存空间状态表示分为两种情况：
(1) 内存空间被占用：
内存空间起始地址-内存空间结束地址.1.占用的进程号
(2) 内存空间空闲
内存空间起始地址-内存空间结束地址.0
实验一 实现单处理机下的进程调度程序
编写一个单处理机下的进程调度程序，模拟操作系统对进程的调度。
要求：
1.能够创建指定数量的进程，每个进程由一个进程控制块表示。
2.实现先来先服务调度算法：进程到达时间可由进程创建时间表示。
3.实现短作业优先调度算法：可指定进程要求的运行时间。（说明：对不可剥夺的短作业优先算法，当作业运行时间相等时，优先调度进程号小的进程执行；对可剥夺式的短作业优先算法，即选最短剩余时间的进程进行运行，在剩余时间相同的情况下，选择到达时间早的进程进行运行）
4. 实现时间片轮转调度算法：可指定生成时间片大小。（说明：新进程到来时插入到就绪队列的队尾，当进程P运行完一个时间片时，若同时有进程Q到达，则先在就绪队列队尾插入新到达的进程Q，之后再插入进程P)
5.实现动态优先级调度算法：可指定进程的初始优先级（优先级与优先数成反比，优先级最高为0），优先级改变遵循下列原则：进程在就绪队列中每停留一个时间片，优先级加1，进程每运行一个时间片，优先级减3。（说明：本算法在优先级相同的情况下，选择到达时间早的进程进行运行）
测试用例格式如下：
输入：调度算法
进程号/到达时间/运行时间/优先级/时间片
输出：调度顺序/进程号/开始运行时间/结束运行时间/优先级
其中调度算法选项为：1----先来先服务，2----短作业优先，3----最短剩余时间优先，4----时间片轮转，5----动态优先级
RSS订阅
290
1
