摘要
Title: 1789. 牛为什么过马路 II
Tag: 模拟
Memory Limit: 64 MB
Time Limit: 1000 ms

1789. 牛为什么过马路 II

题意

农夫约翰的农场布局十分奇特，一条大型的环形道路将奶牛吃草的田地围了起来。
每天早晨，奶牛们穿过这条道路，进入到田地吃草；每天晚上，奶牛们穿过这条道路，离开田地，返回牛棚休息。
众所周知，奶牛是有习性的动物，每头奶牛每天通过道路的方式都相同。
每头奶牛每天固定地从道路的某一位置进入田地，从道路的另一不同位置离开田地。
所有奶牛的所有进出位置之间互不相同
约翰共有 26 头奶牛，依次命名为 A∼Z。
因此，道路上共有 52 个不同的进出位置。
约翰沿着环形道路按顺时针方向扫描了每个位置，并记录了每个位置处经过的奶牛的名字，最终形成了一个包含 52 个字母的序列，A∼Z 中的每个字母恰好出现两次。
他并没有记录哪些位置是入口，哪些位置是出口。
看着地图上记录的这些位置，约翰想要知道一天当中，有多少对奶牛之间的从入口穿过田地到达出口的路径可能会存在交叉。
如果奶牛 A 从入口穿过田地到达出口的路径必须穿过奶牛 B 从入口穿过田地到达出口的路径，那么称这对牛 (A,B) 是“交叉”对。
请帮助约翰计算“交叉”对（不考虑顺序，即 (A,B) 与 (B,A) 视为同一对）的总数。
思路

当某个字母有且仅有一个在两个相同字母中间时，算交叉

代码

'''
Author: NEFU AB-IN
Date: 2022-02-04 18:06:33
FilePath: \ACM\Acwing\1789.py
LastEditTime: 2022-02-04 19:53:32
'''

from collections import defaultdict
from string import ascii_uppercase

d = defaultdict(list)

if __name__ == "__main__":
    s = input()
    for i in range(len(s)):
        d[s[i]].append(i)
    # print(d)
    res = 0
    for i in ascii_uppercase:
        x1 = d[i][0]
        x2 = d[i][1]
        for j in d.keys():
            if i == j:
                continue
            y1 = d[j][0]
            y2 = d[j][1]
            if ((y1 < x1 < y2) and
                (not (y1 < x2 < y2))) or ((y1 < x2 < y2) and
                                          (not (y1 < x1 < y2))):
                res += 1
    print(res // 2)

1789. 牛为什么过马路 II

题意

思路

代码