24个样例悬关求调!
查看原帖
24个样例悬关求调!
1046636
YFF1楼主2024/5/18 22:24
#include<bits/stdc++.h>
using namespace std;
string s[300005];
char c[300005];
bool use[300005];
long long n,mp[300005][30],sum,ans;
int main () {
	cin>>n;
	for(int i=1;i<=n;i++)cin>>s[i];
	sort(s+1,s+1+n);//排序 
	for(int i=1;i<=n;i++)cout<<s[i]<<endl; 
	for(int i=1;i<=n;i++){
		for(int j=0;j<s[i].size();j++){
			int pos=int(s[i][j]-96);
			if(c[j]==s[i][j]||use[j]==0){//如果该位置上的字符与上一个字符中该位置上的字符相同或上一个该位置上的字符为空 
				c[j]=s[i][j];
				use[j]=1;
				mp[j][pos]++;//累加结果 
			}
			else{//若有不同,说明这个字符串与上一个字符串的最大公共前缀到此为止了 
				int pos2=int(c[j]-96);
				ans+=(mp[j][pos2]*(mp[j][pos2]-1))/2;//每两个匹配一次 
				for(int k=j;k<s[i].size();k++){
					mp[k][int(c[k]-96)]=0;
					c[k]=s[i][k];
					mp[k][int(s[i][k])-96]++;//将这之后所有的累计数组归零,因为要求的是前缀连续相同的长度 
				}
				break;
			}
		}
	}
	for(int j=0;j<s[n].size();j++){
		int pos3=int(s[n][j]-96);
		ans+=(mp[j][pos3]*(mp[j][pos3]-1))/2;//最后还要再补一次计算 
	}
	cout<<ans;
	return 0;
}
2024/5/18 22:24
加载中...