本页面已浏览26次
Table of Contents
1. Cow Gymnastics
为了提高健康水平，奶牛们开始进行体操训练了！Farmer John选定了他最喜爱的奶牛Bessie来执教其他N头奶牛，同时评估她们学习不同的体操技术的进度。
K次训练课的每一次（\(1\le K \le 10\)），Bessie 都会根据N头奶牛的表现给她们进行排名（\(1\le N\le 20\)）。之后，她对这些排名的一致性产生了好奇。称一对不同的奶牛是一致的，如果其中一头奶牛在每次训练课中都表现得都比另一头要好。
请帮助Bessie计算一致的奶牛的对数。
输入格式（文件名：gymnastics.in）：
输入的第一行包含两个正整数K和N。以下K行每行包含整数\(1...N\)的某种排列，表示奶牛们的排名（奶牛们用编号 \(1…N\)进行区分）。如果在某一行中A出现在B之前，表示奶牛A表现得比奶牛B要好。
输出格式（文件名：gymnastics.out）：
输出一行，包含一致的奶牛的对数。
输入样例：
3 4
4 1 2 3
4 1 3 2
4 2 1 3输出样例：
4一致的奶牛对为 (1,4)、(2,4)、(3,4) 和 (1,3)。
分析
在这道题目中，我们将严格按照题目要求，用输入和输出文件来进行数据的进和出。
题设中已经给出了“一致”的定义，这是比较容易用循环完成的。
一次训练中，奶牛A和所有其他的牛比较排名，如果A在B前，那么A比B好。而“A在B”前，就是A在记录本次训练的排名表中所在的位置小于B的位置。
如果所有训练（K次）中，A都比B好，那么这个“好”的计数要等于K。如果是这样，那么总的一致数要加1。
答案
思考
这道题目不难，只要想到用一个二维数组来影射K次比赛的排名就可以。
另外请留意输入、输出文件的操作。
2. Where Am I?
Farmer John出门沿着马路散步，但是他现在发现可能迷路了！
沿路有一排共N个农场（\(1\le N \le 100\)）。不幸的是农场并没有编号，这使得Farmer John难以分辨他在这条路上所处的位置。然而，每个农场都沿路设有一个彩色的邮箱，所以 Farmer John希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用A..Z之间的一个字母来指定，所以沿着道路的N个邮箱的序列可以用一个长为N的由字母A..Z组成的字符串来表示。某些邮箱可能会有相同的颜色。Farmer John想要知道最小的K的值，使得他查看任意连续K个邮箱序列，他都可以唯一确定这一序列在道路上的位置。
例如，假设沿路的邮箱序列为 'ABCDABC' 。Farmer John不能令\(K=3\)，因为如果他看到了'ABC'，沿路有两个这一连续颜色序列可能所在的位置。最小可行的K的值为\(K=4\)，因为如果他查看任意连续4个邮箱，这一颜色序列可以唯一确定他在道路上的位置。
输入格式（文件名：whereami.in）：
输入的第一行包含N，第二行包含一个由N个字符组成的字符串，每个字符均在A..Z之内。
输出格式（文件名：whereami.out）：
输出一行，包含一个整数，为可以解决 Farmer John 的问题的最小K值。
输入样例：
7
ABCDABC输出样例：
4分析
这里，首先注意到\(N\)很小，最多到100，所以可以用暴力法解决问题。
其次要注意到的是，题目其实问的是在这一个字符串中，不同长度的子字符串，会不会重复？如果长度为3的时候，各个子字符串有重复，那么就不足以帮助FJ确定位置。于是我们增加长度，直到第一次出现长度为K的时候不再有重复子字符串。这个K就是答案。
找重复有很多方法，可以用暴力法，也可以借用C++中的“集合”（set）标准库。我将采用这个做法。
我会用到集合中的两个方法：
count：统计某个元素的出现次数。基于集合的特性，它只能是0（不存在）或者1（存在）。insert：将一个元素放到集合中去。我们不用担心重复放入的问题，因为set会帮我们处理这个问题。
答案
思考
请注意答案中10行的循环控制写法，我们也可以写成i+len<=n。
还要注意，比较规范的写法是在打开文件、使用完毕后，应该将文件关闭（38、39行）。
3. Livestock Lineup
每天，Farmer John都要给他的8头奶牛挤奶。她们的名字分别是Bessie，Buttercup，Belinda，Beatrice，Bella，Blue，Betsy，和 Sue。
不幸的是，这些奶牛相当难以伺候，她们要求Farmer John以一种符合N条限制的顺序给她们挤奶（\(1\le N\le 7\)）。每条限制的形式为“X必须紧邻着Y挤奶”（X must be miled beside Y），要求奶牛X在挤奶顺序中必须紧接在奶牛Y之后，或者紧接在奶牛Y之前。
请帮助Farmer John求出一种满足所有限制的奶牛挤奶顺序。保证这样的顺序是存在的。如果有多种顺序都满足要求，请输出字典序最小的一种。也就是说，第一头奶牛需要是所有可能排在任意合法奶牛顺序的第一位的奶牛中名字字典序最小的。在所有合法的以这头字典序最小的奶牛为首的奶牛顺序中，第二头奶牛需要是字典序最小的，以此类推。
输入格式（文件名：lineup.in）：
输入的第一行包含N。以下N行每行包含一句句子，以"X must be milked beside Y"的格式描述了一条限制，其中X和Y为Farmer John的某些奶牛的名字（上文列举了八个可能的名字）。
输出格式（文件名：lineup.out）：
请用8行输出一个奶牛的顺序，每行输出一头奶牛的名字，满足所有的限制。如果由多种顺序符合要求，输出字典序最小的奶牛顺序。
输入样例：
3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice输出样例：
Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup分析
一种思路，是我们暴力列举所有可能的排列方式。由于只有8头牛，所以总的排列方式不过\(8!=40320\)种。另外一种方法，是我们用排列（permutatoin）的方式，按照字典序的增序生成各个排列，一旦满足所有限制条件就停止并输出即可。
排列（permutation）
排列是一种重要的算法。一个常见的例子是，在n个各自不同的元素中，挑出m个按挑出的先后次序形成一个“结果”。在生活中，这样的应用比比皆是。比如某人来到苏州旅游，并确定了总共10个想去的景点。但由于时间紧迫，他只能去6个景点。他需要规划：去哪些景点，先去哪里再去哪里。这就是一个从10（n）个元素中挑出6（m）个并有先后顺序的问题。
计算这样的排列总共有多少个并不困难。数学公式是：\(P_n^m=\frac{n!}{n-m!}\)。以上题为例，他有总共151,200种排列方式。
如果上面的公式中，\(n=m\)，我们称其为“全排列”。在本题中，我们可以对这8头牛进行全排列。C++中，向量（vector）支持全排列的操作。
然后，我们对每个可能的排列方式要验证限制条件。限制条件的输入格式很固定，我们关心的只是里面提到的两头牛。每个条件其实就是两头牛的相邻关系。比如：
Buttercup must be milked beside Bella中，涉及Buttercup和Bella两头牛。
保存这样的相邻关系的结构有很多种。我采用vector<string>的方式，而为了更好地进行循环，我将这个相邻关系包到一个映射里，所以最后的结构是map<int, vector<string>>。需要注意的是，相邻关系可以有两个：A在B前和A在B后都可以构成相邻关系。
最后一步，我们根据两头牛的名字，在当前的排列中找到各自的位置，求出两个位置的差。这个差必须为1才是满足相邻条件的。
答案
思考
整个程序有两个辅助函数。
where函数用来根据牛的名字来定位它在当前排列中的位置。satisfies_constraints函数用来遍历所有限制条件，获取涉及的两头牛和位置，并判定是否相邻。
还能不能不用别的数据结构来保存相邻关系？试试看，并用测试数据验证其正确性。
另外，要注意的是，38-45行将每头奶牛名字输入的时候，是有顺序的。我们在输入的时候，严格按照了每头奶头名字的字典序。如果不这么做，有可能给出不同的答案。