Why Did the Cow Cross the Road II

题目描述

农夫约翰的农场布局很奇特：主牧场的外围有一条很大的环形道路，奶牛白天在主牧场里吃草。 每天早晨，奶牛在前往牧场时会穿过这条路；每天傍晚，它们离开牧场返回牛棚时又会再次穿过这条路。

众所周知，奶牛有很强的习惯性，每头奶牛每天都以相同的方式过路。每头奶牛进入牧场的过路点与离开牧场的过路点不同，并且所有这些过路点彼此互不相同。农夫约翰恰好有 26 头奶牛，他偷懒把它们命名为 A 到 Z（他不确定如果有第 27 头奶牛该怎么办……），因此在环形道路上一共有 52 个过路点。农夫约翰通过顺时针绕圈扫描这些过路点，并在每个过路点记下对应奶牛的名字，从而得到一个长度为 52 的字符串，其中每个字母恰好出现两次。 他不会记录哪些过路点是进入点、哪些是离开点。

看着这张过路点地图，农夫约翰想知道白天不同奶牛对之间可能会有多少次路径相交。他称一对奶牛 $(a,b)$ 为“相交”对，当且仅当奶牛 $a$ 从进入到离开的路径必然与奶牛 $b$ 从进入到离开的路径相交。请帮助农夫约翰计算相交对的总数。

输入格式

输入包含一行，一个由 52 个大写字母组成的字符串。字母表中的每个字母恰好出现两次。

输出格式

请输出相交对的总数。

ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ

1

提示

在这个例子中，只有奶牛 A 和 B 是一对相交对。 题目来源：Brian Dean

标签: USACO|2017|Bronze

来源

USACO|2017|Bronze