自动搬运

查看原文

来自洛谷，原作者为

	ccsc 拥有你就像拥有全世界

搬运于2025-08-24 22:01:47，当前版本为作者最后更新于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;
}