h083 - 3. 數位占卜

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算從給定的 $m$ 個字串中，有多少對字串可以連接起來形成一個迴文串。迴文串是指正讀和反讀都相同的字串。相同的字串組合只計算一次。

解題思路

程式碼的核心思想是枚舉所有可能的字串對，並檢查它們的連接是否形成迴文串。對於每對字串 $S$ 和 $T$，程式碼會連接它們形成 $S+T$ 和 $T+S$，然後檢查這兩個字串是否為迴文串。為了避免重複計算，程式碼使用一個 set 來儲存所有輸入的字串，以便快速查找。

具體步驟如下：

1. 讀取字串數量 $m$。
2. 讀取 $m$ 個字串，並將它們儲存在一個 set 中。
3. 枚舉所有可能的字串對 $(a[i], a[j])$，其中 $i \le j$。
4. 對於每對字串，計算 $S = a[i] + a[j]$ 和 $T = a[j] + a[i]$。
5. 檢查 $S$ 和 $T$ 是否為迴文串。
6. 如果 $S$ 或 $T$ 是迴文串，則增加計數器 ans。
7. 輸出 ans。

程式碼中，迴文串的判斷是通過將字串分成兩半，然後比較兩半是否相等來實現的。具體來說，對於一個長度為 $2k$ 的字串，它會比較前 $k$ 個字元和後 $k$ 個字元是否相等。

複雜度分析

• 時間複雜度: O(n^2 * k)，其中 n 是字串的數量，k 是字串的平均長度。外層迴圈枚舉所有字串對，需要 O(n^2) 的時間。內層迴圈檢查字串是否為迴文串，需要 O(k) 的時間。
• 空間複雜度: O(n * k)，其中 n 是字串的數量，k 是字串的平均長度。set 儲存所有輸入的字串，需要 O(n * k) 的空間。

程式碼

#include <iostream>
#include <set> 
using namespace std;
int n,ans;
string a[50005];
set <string> st;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> a[i];
		st.insert(a[i]);
	} 
	for(int i=0;i<n;++i){
		for(int A=1;A*2<a[i].size();++A){
			int B=a[i].size()-A*2,cnt=0;
			for(int j=0;j<A;++j){
				if(a[i][j]!=a[i][j+B+A]){
					cnt=1;
					break;
				}
			}
			if(cnt)continue;
			string tmp;
			for(int j=A;j<A+B;++j)
				tmp+=a[i][j];
			ans+=st.count(tmp);
		}
	}
	cout << ans;
}