输出：
可安排的最大相容活动子集。
2-8排队接水问题
问题描述：
有N个人在一个水龙头前排队接水，假如每个人接水的时间为Ti,请编程找出这N个人排队的一种顺序，使得N个人的平均等待时间最小。
输入：
人数N以及每个人的接水时间T1，T2,……,Tn,
输出：
排队顺序，即1到N的一种排列以及这种方案下的平均等待时间。
2-8田忌赛马
问题描述：
田忌和齐王赛马各有n匹马，现进行n场比赛，
比赛规则如下：
1、马匹不得重复参赛。
2、赢一场得2分，输一场得0分，平局各得1分
请为田忌安排马匹出场次序，使其得分最高。
输入：
马匹数目n,田忌每匹马的斗争值T1，T2,……,Tn,以及齐王每匹马的斗争值Q1，Q2,……,Qn,（值大的胜值小的马）
输出：
田忌马的出场次序以及最后的得分。
2-9程序存储问题
问题描述：
设有n个程序{1,2,3,…,n}要存放在长度为L的磁带上。
程序i存放在磁带上的长度是li,1≤i≤n。
要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。
输入：
先是两个正整数，分别表示程序文件个数n和磁带长度L，接下来是n个正整数，表示程序存放在磁带上的长度。
输出：
最多可以存储的程序个数m，以及已存程序的编号。
2-10数列极差问题
问题描述：
在黑板上写了N个正整数作成的一个数列，进行如下操作：
每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min，编程求解这样的极差。
输入：
正整数的个数N，以及N个正整数
输出：
极差d
动态规划
3-1导弹拦截问题
问题描述：
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：
虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入：
导弹依次飞来的高度（不大于30000的正整数），
输出：
最多能拦截多少导弹数，以及被拦截的导弹飞来时候的高度。
3-2合唱队型问题
问题描述：
N位同学站成一排，音乐老师要请其中的（N-K）位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：
设K位同学从左到右依次编号为1，2...，K，他们的身高分别为T1，T2，...，TK，则他们的身高满足T1<...Ti+1>...>TK（1<=i<=K）。
输入：
队员人数N和每个学生身高T[i]，
输出：
最长的合唱队形的长度和相应的合唱队员编号。
3-3最大子段和问题
问题描述：
给定一个整数序列,求其连续子序列的和的最大值，如果序列中全为负数则规定最大子段和为0,长度L=0。
输入：
整数的个数n以及n个整数
输出：
最大连续子序列之和以及序列长度。
3-40/1背包问题
问题描述：
给定n种物品和一个背包。
物品i的重量是Wi，其价值为Vi，背包的容量为C。
应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
（物体不可以分割）
输入：
物体的件数n，背包的容量C，每件物品的重量和价值。
输出：
背包内物品的总价值以及装载方案。
3-5最长公共子序列问题
问题描述：
最长公共子序列也称作最长公共子串（不要求连续），英文缩写为LCS（LongestCommonSubsequence）。
其定义是，一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。
设计一算法，求解两个序列的最长公共子序列。
输入：
已经序列A、B以及长度对应的长度m、n；
输出：
最长公共子序列以及其长度
3-6矩阵连乘加括号问题
问题描述：
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。
给矩阵加上括号以确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
输入：
矩阵个数和n，以及n个矩阵的行、列信息
输出：
加括号的信息以及最少的乘法次数。
3-7金矿开采问题
问题描述：
现在n座金矿，每座金矿开采需要的人数以及产金量已知（假设人数多或少于金矿开采所需人数均无法开采出一块金子），现有一定数量的人员，设计算法，计算出最多可以开采出的金矿数目。
输入：
金矿数目n、人数m、以及每座金矿所需人数Pi以及产金量gi
输出：
最多开采出的金矿数目以及人员安排方案
3-8多段图最短路径问题
问题描述：
给定一张有向带权图，设计一动态规划的算法，计算出所有点到最后目标点的最短距离以及路径。
输入：
有向带权图的邻接表以及项点个数n
输出：
每点到最后目标点的最短距离以及路径。
3-9资源最优分配问题
问题描述：
现在有某种资源共n个单位，准备将它们分配到m个项目上，设在第i个项目上分配j个单位的资源就可以获得的收益为a[i,j],求可以获得的最大总收益。
输入：
资源数n，工程数m以及第i个项目上分配j个单位的资源可以获得的收益a[i,j]
输出：
最优分配方案以及可以获得的最大收益。
3-10轨道建造问题
问题描述：
建造滑雪场的升降轨道。
起点和终点的高度已知，x坐标分割成若干份，间隔为1，每一点都给出支架的高度。
要选择尽可能少的支架顶端建立固定点，两个固定点之间用一条直钢轨连接，当然要求中间支架的高度都不能超过钢轨在那里的高度。
而且两个相邻固定点之间的距离不能超过给定的K。
输入：
起点和终点海拔高度H1，H2，支架总个数n以及每个支架的海拔高度hi，相邻固定点间的最大限度距离K
输出：
最少用于固定的支架数目x以及用到的支架编号
3-11乘积最大问题
问题描述：
向长度为N的数字串中插入r个乘号，将其分成r+1个组成部分，找出一种分法，使得这r+1个部分乘积最大。
输入：
数字串的个数以及N个数字字符，以有乘号的个数r
输出：
乘号的位置以及最后的乘积
回溯法
4-1N后问题
问题描述：
在n×n格的棋盘上放置彼此不受攻击的n个皇后。
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，设计一算法，求解一种皇后的摆放方案。
输入：
皇后数目n
输出：
各个皇后的摆放位置
4-2马步遍历问题
问题描述：
有一n×n格的棋盘，按照国际象棋的规划，马只能走“日”字型结构，设计一算法，按马的走法将棋盘每一格刚好遍历一次。
输入：
棋盘大小n
输出：
遍历方案
4-3迷宫问题
问题描述：
设有一个n×m格的迷宫，四面封闭，仅在左上角的格子有入口，左下角的格子有出口。
迷宫内部的格子，其东、西、南、北四面可能有出入口，也可能没有出入口。
设计一个程序通过迷宫
输入：
迷宫
输出：
行走方案
4-4图m着色问题
问题描述：
用m种颜色为无向图G=（VE）的每个顶点着色要求每个顶点着一种颜色、并使相邻两个顶点之间具有不同颜色。
输入：
地图邻接矩阵以及可用颜色种类m
输入：
着色方案以及用到的颜色数（一种即可）
4-50/1背包问题
问题描述：
给定n种物品和一个背包。
物品i的重量是Wi，其价值为Vi，背包的容量为C。
应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
（物体不可以分割）
输入：
物体的件数n，背包的容量C，每件物品的重量和价值。
输出：
背包内物品的总价值以及装载方案。
4-6符号三角形问题
问题描述：
有一种符号三角形由“+”“-”两种符号组成，其第一行的符号是已知，其余各行的符号的生成规则如下：
2个同号下面都是“+”，2个异号下面都是“-”。
求第一行符号个数n已知的情况下，生成的三角形中“+”“-”号个数相等的三角形数目。
输入：
第一行符号的个数n
输出：
“+”“-”个数相等的三角形的数目以及三角形
4-7旅行售货员问题
问题描述：
有一售货员，要到世界各地去销售商品，各城市之间的旅行代价已知，为其制定一旅行计划，将各个城市刚好遍历一次再回到起点，并且旅行代价总和最小。
输入：
各个城市之间的旅行代价以及城市的个数n
输出：
最小代价和以及旅行方案。
4-8作业分配问题
问题描述：
现有个操作员操作n项作业，每第i个操作员操作第j项作业的时间Aij（0≤i,j≤n）已知，要求每个操作员操作一项作业，使得操作时间总和最小。
输入：
操作员个数n，第i个操作员操作第j项作业的时间Aij（0≤i,j≤n）
输出：
分配方案以及操作时间总和。
4-9陷井逃离问题
问题描述：
TOM掉进了一个陷阱阵，每个陷阱两种选择，选择一：
逃离，但若想成功逃离，需要相应的时间将其排除，并需在其规定时间前逃出，否则无法逃出。
选择二：
直接通过，但直接通过生命将消耗1点。
为其制定一逃生方案，使其消耗生命最少。
输入：
陷阱个数n，生命点m，以及每个陷阱的排除所需时间以及最晚逃离时间。
输出：
逃生方案以及剩余生命值，若无法逃离，则输出-1.
4-10最大子段和问题
问题描述：
给定一个整数序列,求其连续子序列的和的最大值，如果序列中全为负数则规定最大子段和为0,长度L=0。
输入：
整数的个数n以及n个整数
输出：
最大连续子序列之和以及序列长度。
4-11整数的划分问题
问题描述：
将正整数n表示成一系列正整数之和：
n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。
正整数n的这种表示称为正整数n的划分。
求正整数n的不同划分个数以及划分情况。
输入：
正整数n
输出：
n的划分个数以及划分情况
4-12乘积最大问题
问题描述：
向长度为N的数字串中插入r个乘号，将其分成r+1个组成部分，找出一种分法，使得这r+1个部分乘积最大。
输入：
数字串的个数以及N个数字字符，以有乘号的个数r
输出：
乘号的位置以及最后的乘积
分支限界
5-10/1背包问题
问题描述：
给定n种物品和一个背包。
物品i的重量是Wi，其价值为Vi，背包的容量为C。
应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
（物体不可以分割）
输入：
物体的件数n，背包的容量C，每件物品的重量和价值。
输出：
背包内物品的总价值以及装载方案。
5-2旅行售货员问题
问题描述：
有一售货员，要到世界各地去销售商品，各城市之间的旅行代价已知，为其制定一旅行计划，将各个城市刚好遍历一次再回到起点，并且旅行代价总和最小。
输入：
各个城市之间的旅行代价以及城市的个数n
输出：
最小代价和以及旅行方案。
5-3作业分配问题
问题描述：
现有个操作员操作n项作业，每第i个操作员操作第j项作业的时间Aij（0≤i,j≤n）已知，要求每个操作员操作一项作业，使得操作时间总和最小。
输入：
操作员个数n，第i个操作员操作第j项作业的时间Aij（0≤i,j≤n）
输出：
分配方案以及操作时间总和。
图的遍历问题
6-1图的深度优先遍历算法（要求用邻接表存储）
问题描述：
给定一张图，要求用深度优先方式对图的结点进行遍历
输入：
图的顶点个数以及邻接表数据
输出：
遍历次序
6-2图的广度优先遍历算法（要求用邻接矩阵存储）
问题描述：
给定一张图，要求用广度优先方式对图的结点进行遍历
输入：
图的顶点个数以及邻接表数据
输出：
遍历次序
ACM专题（可置换题）
7-1猫和老鼠
问题描述：
有一只很霸道的猫，捉来好多好多老鼠，然后，这只猫就开始开大餐了。
但为了显得它与众不同，它用了一个很特别的就餐顺序：
它先定好步长k，然后它吃掉第1个位置上的，然后再每隔k只再吃一只老鼠一轮结束后，它再次从第1个位置开始继续吃，直到最后只剩下一只老鼠为止。
而这最后一只老鼠这只猫会放走，因为它不想破坏生态平衡，它希望这只老鼠，来年再制造n只。
。
。
。
。
。
（当然它怎么找它的另一半就不管了。
。
。
）但这群老鼠中，有一只特别聪明，它希望不死，它经过计算，于是一开始它就站在一个特别的位置上，而最后，它果然没死，被放走了，你知道它站在哪个位置上吗？
输入：
多组测试数据，每组一行，每行两个正整数n和k（1<=n,k<=1000000）n和k的意义如描述
输出：
输出这只老鼠站的位置
样例输入：
101
62
样例输出：
8
5
7-2猜数字游戏
问题描述：
猜数字游戏是gameboy最喜欢的游戏之一。
游戏的规则是这样的：
计算机随机产生一个四位数，然后玩家猜这个四位数是什么。
每猜一个数，计算机都会告诉玩家猜对几个数字，其中有几个数字在正确的位置上。
比如计算机随机产生的数字为1122。
如果玩家猜1234,因为1,2这两个数字同时存在于这两个数中，而且1在这两个数中的位置是相同的，所以计算机会告诉玩家猜对了2个数字，其中一个在正确的位置。
如果玩家猜1111,那么计算机会告诉他猜对2个数字，有2个在正确的位置。
现在给你一段gameboy与计算机的对话过程，你的任务是根据这段对话确定这个四位数是什么。
输入：
输入数据有多组。
每组的第一行为一个正整数N（1<=N<=100），表示在这段对话中共有N次问答。
在接下来的N行中，每行三个整数A,B,C。
gameboy猜这个四位数为A，然后计算机回答猜对了B个数字，其中C个在正确的位置上。
当N=0时，输入数据结束。
输出：
每组输入数据对应一行输出。
如果根据这段对话能确定这个四位数，则输出这个四位数，若不能，则输出"Notsure"。
样例输入：
648152157161078421049010085853385553224815002999330
样例输出：
3585Notsure
7-3采矿游戏
问题描述：
某天gameboy玩魔兽RPG。
有一个任务是在一个富含金矿的圆形小岛上建一个基地，以最快的速度采集完这个小岛上的所有金矿。
这个小岛上有n（0而且这个小岛的地势非常平坦，所以基地可以建在小岛的任何位置，每个金矿的采矿速度只跟矿藏到基地的路程长度有关。
为了不让这个任务太无聊，游戏设计者对这个小岛施了个“魔法”，规定矿工在小岛上只能正南正北正西正东走。
也就是说矿工不能斜着在岛上走。
这个小岛在一个二维直角坐标系中描述。
你的任务就是帮gameboy找一个建造基地的位置，使矿工能以最快的速度采完所有矿。
输入：
输入数据有多组。
每组数据的第一行是一个正整数n（0在接下来的n行中，每行有两个实数x,y，表示其中一个金矿的坐标。
n=0表示输入数据结束。
输出：
每一组输入数据对应一行输出，输出两个实数x，y（保留小数点后两位），也就是你找到的建造基地的位置坐标。
如果坐标不唯一，可以任选一个输出。
样例输入：
41.01.03.01.03.03.01.03.00
样例输出：
2.002.00
7-4母猪问题
问题描述：
话说现在猪肉价格这么贵，著名的ACBoy0068也开始了养猪生活。
说来也奇怪，他养的猪一出生第二天开始就能每天中午生一只小猪，而且生下来的竟然都是母猪。
不过光生小猪也不行，0068采用了一个很奇特的办法来管理他的养猪场：
对于每头刚出生的小猪，在他生下第二头小猪后立马被杀掉，卖到超市里。
假设在创业的第一天，0068只买了一头刚出生的小猪，请问，在第N天晚上，0068的养猪场里还存有多少头猪？
输入：
测试数据的第一行包含有一个正整数T，代表测试数据的个数。
接下来有T组测试，每组测试数据占一行，分别有一个正整数N代表0068创业的第N天。
（0输出：
对于每组数据，请在一行里输出第N天晚上养猪场里猪的数目。
样例输入：
223
样例输出：
23
7-5杀人游戏
问题描述：
不知道你是否玩过杀人游戏，这里的杀人游戏可没有法官，警察之类的人，只有土匪，现在已知有N个土匪站在一排，每个土匪都有一个编号，从1到N，每次杀人时给定一个K值，从还活着的土匪中，编号从小到大的找到K个人，然后杀掉，继续往下，直到找遍，然后继续从剩下的土匪中，编号从小到大找到第K个活着的土匪，然后杀掉。
比如，现在有10个土匪，K为3，第一次杀掉3，6，9号的土匪，第二次杀掉4，8号土匪，第三次杀掉5号土匪，第四次杀掉7号土匪，第五次杀掉10号土匪，我们看到10号土匪是最后一个被杀掉的（从1到K-1的土匪运气好，不会被杀！
）。
现在给定你一个N和一个K，问你最后一个被杀掉的土匪的编号是多少。
输入：
第一行有一个T（T<=10000），接下来有T组数据，每组中包含一个N（N<2^31）和一个K（3<=K<=100&&K输出：
对于每组数据，输出最后被杀的土匪的编号。
样例输入：
1103
样例输出：
10
升级会员 