时间限制：3.0s 内存限制：256.0MB
问题描述
从万能词典来的聪明的海狸已经使我们惊讶了一次。他开发了一种新的计算器，他将此命名为\。它非常特别，并且被计划使用在各种各样的科学问题中。 为了测试它，聪明的海狸邀请了n位科学家，编号从1到n。第i位科学家给这个计算器带来了ki个计算题。第i个科学家带来的问题编号1到n，并且它们必须按照编号一个一个计算，因为对于每个问题的计算都必须依赖前一个问题的计算结果。
每个教授的每个问题都用一个数ai,?j? 来描述，i（1≤i≤n）是科学家的编号，j（1≤j≤ ki）是问题的编号，ai,?j? 表示解决这个问题所需资源单位的数量。
这个计算器非常不凡。它一个接一个的解决问题。在一个问题解决后，并且在下一个问题被计算前，计算器分配或解放资源。
计算器中最昂贵的操作是解放资源，解放远远慢于分配。所以对计算器而言，每一个接下来的问题所需的资源不少于前一个，是非常重要的。
给你关于这些科学家所给问题的相关信息。你需要给这些问题安排一个顺序，使得―坏对‖尽可能少。
所谓―坏对‖，就是相邻两个问题中，后一个问题需求的资源比前一个问题少。别忘了，对于同一个科学家给出的问题，计算它们的相对顺序必须是固定的。 输入格式
第一行包含一个整数n，表示科学家的人数。接下来n行每行有5个整数，ki, ai,?1, xi, yi, mi (0?≤?ai,?1?
第一行输出一个整数，表示最优顺序下最少的―坏对‖个数。 如果问题的总个数不超过200000,接下来输出
行，表示解决问题的最优顺序。每
一行两个用空格隔开的整数，表示这个问题所需的资源单位数和提供这个问题的科学家的编号。 样例输入 2
2 1 1 1 10 2 3 1 1 10 样例输出 0 1 1 2 1 3 2 4 2
6
数据规模和约定
20%的数据n?=?2, 1?≤?ki?≤?2000； 另外30%的数据n?=?2, 1?≤?ki?≤?200000； 剩下50%的数据 1?≤?n?≤?5000, 1?≤?ki?≤?5000。
6. 算法训练 Cowboys
时间限制：2.0s 内存限制：256.0MB
问题描述
一个间不容发的时刻：n个牛仔站立于一个环中，并且每个牛仔都用左轮手枪指着他旁边的人！每个牛仔指着他顺时针或者逆时针方向上的相邻的人。正如很多西部片那样，在这一刻，绳命是入刺的不可惜……对峙的场景每秒都在变化。每秒钟牛仔们都会分析局势，当一对相邻的牛仔发现他们正在互指的时候，就会转过身。一秒内每对这样的牛仔都会转身。所有的转身都同时在一瞬间发生。我们用字母来表示牛仔所指的方向。―A‖表示顺时针方向，―B‖表示逆时针方向。如此，一个仅含―A‖―B‖的字符串便用来表示这个由牛仔构成的环。这是由第一个指着顺时针方向的牛仔做出的记录。例如，牛仔环―ABBBABBBA‖在一秒后会变成―BABBBABBA‖；而牛仔环―BABBA‖会变成―ABABB‖。这幅图说明了―BABBA‖怎么变成―ABABB‖ 一秒过去了，现在用字符串s来表示牛仔们的排列。你的任务是求出一秒前有多少种可能的排列。如果某个排列中一个牛仔指向顺时针，而在另一个排列中他指向逆时针，那么这两个排列就是不同的。 输入格式
输入数据包括一个字符串s，它只含有―A‖和―B‖。 输出格式
输出你求出来的一秒前的可能排列数。 数据规模和约定
s的长度为3到100（包含3和100） 样例输入 BABBBABBA 样例输出 2 样例输入 ABABB 样例输出 2
7
样例输入 ABABAB 样例输出 4 样例说明
测试样例一中，可能的初始排列为：\和 \。 测试样例二中，可能的初始排列为：\和\。
7. 算法训练数字三角形
时间限制：1.0s 内存限制：256.0MB
问题描述
（图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路 径，使该路径所经过的数字的总和最大。 ●每一步可沿左斜线向下或右斜线向下走； ●1＜三角形行数≤100；
●三角形中的数字为整数0，1，…99；
（图３.１－１） 输入格式
.
文件中首先读到的是三角形的行数。
接下来描述整个三角形 输出格式
最大总和（整数） 样例输入 5 7 3 8
8
8 1 0 2 7 4 4 4 5 2 6 5 样例输出 30
8. 算法训练 未名湖边的烦恼
时间限制：1.0s 内存限制：256.0MB
问题描述
每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法） 输入格式
两个整数，表示m和n 输出格式
一个整数，表示队伍的排法的方案数。 样例输入 3 2 样例输出 5
数据规模和约定 m,n∈［0,18］ 问题分析
9. 算法训练最大的算式
时间限制：1.0s 内存限制：256.0MB
问题描述
题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：
N=5，K=2，5个数字分别为1、2、3、4、5，可以加成：
9
1*2*(3+4+5)=24 1*(2+3)*(4+5)=45 (1*2+3)*(4+5)=45 …… 输入格式
输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2<=N<=15, 0<=K<=N-1）。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。 输出格式
输出文件仅一行包含一个整数，表示要求的最大的结果 样例输入 5 2
1 2 3 4 5 样例输出 120 样例说明
(1+2+3)*4*5=120
10. 算法训练图形显示
时间限制：1.0s 内存限制：512.0MB
问题描述
编写一个程序，首先输入一个整数，例如5，然后在屏幕上显示如下的图形（5表示行数）： * * * * * * * * * * * * * * *
11. 算法训练排序
时间限制：1.0s 内存限制：512.0MB
问题描述
编写一个程序，输入3个整数，然后程序将对这三个整数按照从大到小进行排列。 输入格式：输入只有一行，即三个整数，中间用空格隔开。 输出格式：输出只有一行，即排序后的结果。 输入输出样例
10