题解 P4596 【[COCI2011-2012#5] RAZBIBRIGA】

ccsc · 2019-10-20 17:23:51 · 题解

本题……

奥义！---真！！---暴力！！！

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

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

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

　　时间复杂度O(ac)

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int M=26;
ll cnt[M][M],n;
char s[M];
ll ans;
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        cnt[s[0]-'A'][s[strlen(s)-1]-'A']++;
    }
    for(int i=0;i<26;i++){
        for(int j=0;j<26;j++){
            ll t1=cnt[i][j];cnt[i][j]--;
            for(int k=0;k<26;k++){
                ll t2=cnt[i][k];cnt[i][k]--;
                for(int w=0;w<26;w++){
                    ll t3=cnt[j][w];cnt[j][w]--;
                    ll t4=cnt[k][w];
                    ans+=t1*t2*t3*t4;
                    cnt[j][w]++;
                }
                cnt[i][k]++;
            }
            cnt[i][j]++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}