題目簡介

• 題源：1073 - 小龍的字符串函數 | CCUT OJ
• 題意：給定 \(n\) 個等長字符串，定義函數 \(f(s_i,s_j)\) 表示字符串 \(s_i\) 與 \(s_j\) 中位置和字符相同的總數。輸出 \(\sum f(s_i,s_j)\) ( 其中 \(i<j\) )。
• 數據范圍：\(1\le n\le 2000,1\le |s_i|\le 2000\)
• 注：若無特殊說明，博主的代碼模板如下，通過 solve 函數處理多組測試用例。本文后續代碼僅給出 solve 函數。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ln '\n'

int solve(){

}

int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int T;cin>>T;
	while(T--){
		cout<<solve()<<ln;
	}
	return 0;
}

樸素想法

樸素想法極其簡單，雙循環兩兩遍歷字符串，逐位檢查是否相同即可。復雜度 \(O(n^2 \cdot |s_i|)\)，超時。

int solve(){
	int n;cin >> n;
	vector<string> strs(n);
	for (auto &i:strs) cin >> i;
	int L = strs[0].size();
	i64 ans = 0;
	for (int i = 0; i < n; i++) 
	    for (int j = i + 1; j < n; j++) 
	        for (int k = 0; k < L; k++) 
	            if (strs[i][k] == strs[j][k]) 
	                ans++;
	return ans;
}

題解

定義權值數組 cnt[i][26]，表示這些字符串第 \(i\) 位上各字母出現的頻率。根據排列組合知識，假設字符 \(j\) 在第 \(i\) 位上出現了 cnt[i][j] 次，則其在該位上可兩兩配對的次數為\(C_{cnt[i][j]}^2=\dfrac{cnt[i][j]\cdot (cnt[i][j]-1)}{2}\) 次。時間復雜度 \(O(n \cdot|s_i|\cdot 26)\)。

int solve() {
	int n; cin >> n;
	vector<string> strs(n);
	for (auto &i:strs) cin >> i;
	int L = strs[0].size();
	int cnt[2000][26] = {0};
	for (int k = 0; k < n; k++)
	    for (int i = 0; i < L; i++)
	        cnt[i][strs[k][i]-'a']++;
	i64 ans = 0;
	for (int i = 0; i < L; i++)
	    for (int j = 0; j < 26; j++)
	        ans += 1LL * cnt[i][j] * (cnt[i][j]-1) / 2;
	return ans;
}