USACO 2017 年 2 月竞赛，青铜组

问题 2：为什么奶牛要过马路 II

问题描述：

农场主 John 的农场布局非常特殊，主田地周围有一条大圆形道路，奶牛们每天白天都在这片田地上吃草。每天早晨，奶牛们都会从这条路上走到田地里，晚上则从田地上走回到农舍。

众所周知，奶牛是有习惯的，每只奶牛每天都会按照同样的路径过这条路。每只奶牛进田地的地方和出田地的地方是不同的，并且这些交叉点彼此之间没有重复。农场主 John 拥有恰好 26 只奶牛，他懒得给每只奶牛取名字，直接用字母 A 到 Z 给它们命名（他不确定如果有第 27 只奶牛会怎么办...）。因此，围绕这条路一共有 52 个交叉点。John 通过顺时针扫描这条路记录了这些交叉点，写下每个交叉点对应的奶牛名字，最终形成了一个包含 52 个字符的字符串，其中每个字母恰好出现两次。John 并没有记录哪个交叉点是进入点，哪个交叉点是退出点。

现在，John 看着记录下来的交叉点地图，想知道在一天中，哪些奶牛之间会交叉。他定义一对奶牛 (a, b) 为“交叉对”，如果奶牛 a 从进入点到退出点的路径必定与奶牛 b 从进入点到退出点的路径相交。请帮助 John 计算出所有交叉对的数量。

输入格式（文件 circlecross.in）： 输入包含一行，包含一个由 52 个大写字母组成的字符串。每个字母恰好出现两次。

输出格式（文件 circlecross.out）： 请输出总的交叉对数量。

样例输入：

ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ

样例输出：

1

在这个例子中，只有奶牛 A 和 B 是一对交叉对。

问题解析：

这道题目要求找出奶牛的交叉对数。每对交叉对的奶牛路径会相交。我们可以通过分析每对奶牛的路径来判断它们是否交叉。

• 先扫描字符串，确定每只奶牛进入和退出的交叉点位置。
• 对于每对奶牛 (a, b)，如果奶牛 a 的进入点到退出点的路径和奶牛 b 的路径相交，则这对奶牛是一个交叉对。

思路：

1. 对于每只奶牛，记录它的进入点和退出点。
2. 对每一对奶牛，检查它们的路径是否交叉。如果奶牛 a 的路径和奶牛 b 的路径交叉，则它们是一个交叉对。

时间复杂度：

• 对每一对奶牛进行检查，时间复杂度为 O(26^2)，即 O(676)，这个时间复杂度是可以接受的，因为最多只有 26 对奶牛。

样例解释： 对于输入字符串 ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ，只有奶牛 A 和奶牛 B 的路径相交，因此输出结果是 1。