本页面已浏览15次

1. Triangles

Farmer John想要给他的奶牛们建造一个三角形牧场。

有N（\(3\le N\le 100\)）个栅栏柱子分别位于农场的二维平面上不同的点 \((X_1,Y_1) ... (X_N,Y_N)\)。他可以选择其中三个点组成三角形牧场，只要三角形有一条边与x轴平行，且有另一条边与y轴平行。

Farmer John可以围成的牧场的最大面积是多少？保证存在至少一个合法的三角形牧场。

输入格式（文件名：triangles.in）：

输入的第一行包含整数N。以下N行每行包含两个整数\(X_i\)和\(Y_i\)，均在范围\(−10^4 ... 10^4\) 之内，描述一个栅栏柱子的位置。

输出格式（文件名：triangles.out）：

由于面积不一定为整数，输出栅栏柱子可以围成的合法三角形的最大面积的两倍。

输入样例：

4
0 0
0 1
1 0
1 2

输出样例：

2

位于点 (0,0)、(1,0) 和(1,2)的木桩组成了一个面积为1的三角形。所以，答案为2*1=2。只有一个其他的三角形，面积为0.5。

分析

这是一个典型的暴力求解问题。每一个点可能可以和另外两个点构成一个直角三角形（题目要求），总共需要循环两次，每次最多看另外100个点，所以最多\(100\times 100 \times 100\)次循环就可以了。

每次遍历有两个操作：

1. 判定是否为直角三角形。鉴于我们是遍历所有点，所以只考虑一种直角三角形的情况即可：本点的X和第一个循环中得到的点X相同，本点的Y和第二个循环中得到的点Y相同。在循环执行到适当时候，会再遍历到这些点，只是这些点的顺序会有交换罢了。这样我们不可能漏过任何可能的直角三角形。
2. 计算面积并不断更新最大值。由于结果是要求输出最大三角形面积的两倍，我们在计算的时候也就不用完全套用\(\frac{底*高}{2}\)的公式。而对于直角三角形来说，底和高很容易找到。

答案

思考

（略）

2. Mad Scientist

Farmer John的远房亲戚Ben是一个疯狂的科学家。通常这会在家庭聚会时造成不小的摩擦，但这偶尔也会带来些好处，尤其是当Farmer John发现他正面对一些有关他的奶牛们的独特而不寻常的问题时。

Farmer John当前正面对一个有关她的奶牛们的独特而不寻常的问题。他最近订购了N头奶牛（\(1\le N\le 1000\)），包含两种不同品种：荷斯坦牛和更赛牛。他在订单中用一个长为N的字符串来指定奶牛，其中的字符为H（表示荷斯坦牛）或G（表示更赛牛）。不幸的是，当这些奶牛到达他的农场，他给她们排队时，她们的品种组成的字符串与原先的不同。

我们将这两个字符串称为A和B，其中A是Farmer John原先想要的品种字符组成的字符串，B是他的奶牛们到达时组成的字符串。Farmer John并没有简单地检查重新排列B中的奶牛是否能得到A，而是请他的远房亲戚Ben利用他的科学才华来解决这一问题。

经过数月的研究，Ben发明了一台不同寻常的机器：奶牛品种转换机3000，能够选择任意奶牛组成的子串并反转她们的品种：在这个子串中的所有H变为G，所有G变为H。Farmer John想要求出将他当前的序列B变为他本来订购时想要的A需要使用这台机器的最小次数。然而，疯狂科学家Ben的技能并不会处理开发奇异机器以外的事，所以你需要帮助Farmer John解决这个计算难题。

输入格式（文件名：breedflip.in）：

输入的第一行包含N，以下两行包含字符串A和B。每个字符串均包含N个字符，字符均为H和G之一。

输出格式（文件名：breedflip.out）：

输出将B变为A需要使用机器的最小次数。

输入样例：

7
GHHHGHH
HHGGGHH

输出样例：

2

首先，FJ可以仅改变第一个字符组成的子串，将B变为GHGGGHH。然后，他可以改变由第三和第四个字符组成的子串，得到A。当然，还存在其他有效的执行两次操作的方案。

分析

这道题不存在暴力求解的好方法：子串的分割方式太多了。

但是，我们可以这么想：

• 比较两个字符串，不同的地方正是我们要“操作”的地方。
• 我们希望每次操作，能尽可能多地变换“字符”。也就是说，如果能一次性更换3头牛的种类，我们就不考虑更换2头的情况。因为，只要不是最大的变换，就一定会留下至少一头牛没有被更换，也就需要再多一次操作。

问题就转换成：在B中找到和A不同的字符串有几个，有几个我们就要操作几次。而进一步简化的判定是：这样的字符串，只要第一头牛不同就肯定是不同的。它的长度最小是1，最大可能是整个字符串的长度。

我们设置一些标记，可以方便我们跟踪这样的差异：

• 如果存在差异：
  • 如果已经存在差异，那么当前的差异不计数，继续检查下一个字符。
  • 否则就要计数，并标记“存在差异”了。
• 如果不存在差异，就继续检查下一个字符。

答案

思考

请注意20-27行的写法。if (!mismatched)的另一个分支，是不做任何处理的。

3. Swapity Swap

Farmer John的N头奶牛（\(1\le N\le 100\)）站成一排。对于每一个\(1\le i\le N\)，从左往右数第i头奶牛的编号为i。

Farmer John想到了一个新的奶牛晨练方案。他让她们重复以下包含两个步骤的过程K（\(1\le K\le 10^9\)）次：

1. 当前从左往右数在位置\(A_1 ... A_2\)的奶牛序列反转她们的顺序（\(1\le A_1\lt A_2\le N\)）。
2. 然后，在当前从左往右数在位置\(B_1 ... B_2\)的奶牛序列反转她们的顺序（\(1\le B_1\lt B_2\le N\)）。

当奶牛们重复这一过程K次后，请对每一个\(1\le i\le N\)输出从左往右数第i头奶牛的编号。

测试点性质：

• 测试点2-3满足\(K\le 100\)。
• 测试点4-13没有额外限制。

输入格式（文件名：swap.in）：

输入的第一行包含N和K。第二行包含A_1和A_2，第三行包含B_1和B_2。

输出格式（文件名：swap.out）：

在第i行输出晨练结束时从左往右数第i头奶牛的编号。

输入样例：

7 2
2 5
3 7

输出样例：

1
2
4
3
5
7
6

初始时，奶牛们的顺序从左往右为[1,2,3,4,5,6,7]。在这一过程的第一步过后，顺序变为[1,5,4,3,2,6,7]。在这一过程的第二步过后，顺序变为[1,5,7,6,2,3,4]。再重复这两个步骤各一次可以得到样例的输出。

分析

我们看到这个题目中，如此直白的算法描述，第一个冲动的是暴力算法。数组元素的交换是“不花”时间的，我们模拟K次这样的操作不就可以了么？但K的最大取值提醒我们，这么做非常可能超时。

直觉告诉我们，这样的操作，非常大的可能是：原来的第i个元素，经过p次这样的操作后，竟然又回到了原来的位置（第i个）！以后每经过p次，就会重复出现这样的情形！

我们的直觉是对的。我们可以证明，最多经过N次（也就是\(p \le N\)），一个元素一定会到初始的位置。所以我们的关注点不再是K次，而是K%p的值。这个余数代表的次数，才是“有效”的交换。这个值不会很大，如果\(p\le N\)，那么它小于N。

证明如下：

1. 每次交换，某个位置i的数字会转换到一个新的位置。最坏的情况是，每次都到了一个不同的位置，也就是没有回到原位。
2. 但经过N次交换，这样的不同的位置最多只能有N个。如果\(p\gt N\)而且还不重复（回到原点），那么说明至少可以换到N+1个不同的点。这和题设是矛盾的。
3. 既然\(p\le N\)，那么\(K\%p \lt N\)。这个数字很小。

这个模拟计算量就大大降低了。

计算“新”位置的算法不算太复杂。有兴趣的读者可以自行推导一下。

• \(x=A_1+A_2-x\)（第一个操作）
• \(x=B_1+B_2-x\)（第二个操作）

答案

思考

这个题目用到了鸽笼原理而将“有效”反转的次数大大降低了，这也进而大大降低了运算时间。如果不这么做，本题是无法得到满分的。

另外，这道题目前的时间复杂度是\(O(N^2)\)。同样的题目出现在银牌组，但要求是达到\(O(N)\)的时间复杂度。我们会在银牌组的讲解中再讨论。