[数据结构与算法]每日一题--AcWing 1789. 牛为什么过马路 II

原题链接
题目关键：怎么样算作交叉？

ABAB or BABA就算作交叉，

枚举

#include<bits/stdc++.h>

using namespace std;
vector<int> p[26];

int main() {
    string s;
    cin >> s;
    //统计每个字母的进出位置
    for (int i = 0; i < s.size(); i++) {
        p[s[i] - 'A'].push_back(i);
    }
    int res = 0;
    //i:枚举每个字母，j:枚举除了i的其他字母
    for (int i = 0; i < 26; i++) {
        for(int j=i+1; j<26; j++){
            int cnt = 0;
            for(int k = 0 ; k<2; k++){
                if(p[i][0]<p[j][k]&&p[j][k]<p[i][1]){
                    cnt++;
                }
            }
            //只有交叉才算，即cnt ==1
            if(cnt == 1) res+=1;
        }
    }
    cout << res;
    return 0;
}