EGOI#3 B

Candycar · 2021-07-24 17:43:36 · 个人记录

意题目中的限制条件，保证单词均不相同，所以不用担心重复单词的情况。

那么组成正方形就只与首尾字母有关，于是我们开一个二维的桶 buc 记录每个首尾搭配出现的次数。

然后枚举3条边的情况，就能确定第4条边，累乘次数统计答案，而为了防止同一单词重复用，每次枚举一种首尾搭配后，该种搭配就-1，枚举完再补回来就好了。一定要补回来，不然有去无回。

#include<bits/stdc++.h>
#define int long long
const int MAXN=26;
int buc[MAXN][MAXN];
int n;
string s;
int ans;
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> s;
        buc[s[0]-'A'][s[s.size()-1]-'A']++;
    }
    for(int i = 0;i < 26; i++){
        for(int j = 0; j < 26; j++){
            int t1 = buc[i][j];
            buc[i][j]--;
            for(int k = 0; k < 26; k++){
                int t2 = buc[i][k];
                buc[i][k]--;
                for(int w = 0; w < 26; w++){
                    int t3 = buc[j][w];
                    buc[j][w]--;
                    int t4 = buc[k][w];
                    ans += t1 * t2 * t3 * t4;
                    buc[j][w]++;
                }
                buc[i][k]++;
            }
            buc[i][j]++;
        }
    }
    cout << ans << endl;
    return 0;
}