Board logo

標題: 資料結構 304 完美拼布(中) [打印本頁]
作者: may    時間: 6 天前 17:08     標題: 資料結構 304 完美拼布(中)

資料結構 304 完美拼布
最新一次更新時間：2024-05-08 13:11:45

1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1) 美術老師有 m 塊布料，每一塊布料上面皆印有英文小寫字母組成的字串。若兩塊布料上面的「A字串」和「B字串」連接起來的字串「AB」或「BA」，皆可拆成左右各半且內容完全一樣的子字串，則稱為「完美拼布」。

例如：兩塊布料上面的「A字串」和「B字串」分別為「piep」和「ie」，則連接起來的字串為「piepie」或「iepiep」，皆可以拆成左右各半且內容相同的子字串「pie」、「pie」或「iep」、「iep」，如此符合「完美拼布」的條件。

(2) 現在美術老師有 m 塊布料，請問有幾對布料可以形成「完美拼布」？

提示：相同的兩個字串組合計算一次即可。

3. 輸入輸出：
輸入說明
第 1 列：輸入一個正整數 m（1 ≤ m ≤ 5000），表示有 m 塊布料。
第 2~m+1 列：輸入每一塊布料上的字串，字串皆相異且字串長度不超過1000。

輸出說明
有幾對布料滿足完美拼布的條件。

範例輸入1
3
a
aba
aaa
範例輸出1
1
範例輸入2
5
abyyyab
y
yy
yyy
yyyy
範例輸出2
3
作者: may    時間: 6 天前 17:13

回復 1# may
  1. //#include <iostream>
  2. //#include <vector>
  3. #include <bits/stdc++.h>
  4. using namespace std;

  6. // 檢查字串 s 是否可以均分為兩個相同的部分
  7. bool isPerfectPatch(const string& s) {
  8.     int len = s.length();
  9.     if (len % 2 != 0) return false; // 長度必須是偶數
  10.     int mid = len / 2;
  11.     return s.substr(0, mid) == s.substr(mid, mid); // 檢查前後段是否相等
  12. }

  14. int main() {
  15.     int m;
  16.     cin >> m;
  17.    
  18.     vector<string> fabrics(m);
  19.     for (int i = 0; i < m; ++i) {
  20.         cin >> fabrics[i];
  21.     }
  22.    
  23.     int count = 0;
  24.    
  25.     // 枚舉所有 (i, j) 配對，i < j 避免重複
  26.     for (int i = 0; i < m; ++i) {
  27.         for (int j = i + 1; j < m; ++j) {
  28.             string AB = fabrics[i] + fabrics[j];
  29.             string BA = fabrics[j] + fabrics[i];
  30.             
  31.             // 若 AB 或 BA 其中之一是完美拼布
  32.             if (isPerfectPatch(AB) || isPerfectPatch(BA)) {
  33.                 count++;
  34.             }
  35.         }
  36.     }
  37.    
  38.     cout << count << endl;
  39.     return 0;
  40. }
複製代碼
---------------------------------------------
程式解釋
讀取輸入

先讀取 m（布料數量）。

接著讀取 m 個字串，存入 vector<string> fabrics。

檢查所有可能的組合

使用雙重迴圈遍歷所有 (i, j) 的字串組合。

檢查 AB = fabrics + fabrics[j] 和 BA = fabrics[j] + fabrics 是否為「完美拼布」。

判斷「完美拼布」條件

若 AB 或 BA 其一符合 isPerfectPatch()，則計數增加。

isPerfectPatch() 判斷：

字串長度是否為偶數。

前半段與後半段是否相等。

輸出結果

最終輸出符合條件的布料對數。

時間複雜度分析
雙層迴圈組合檢查：O(m^2)

isPerfectPatch() 需執行 O(N)（N 為最大字串長度）。

總體時間複雜度為 O(m^2 * N)，在 m=5000, N=1000 時仍可接受。
--------------------------------------------
測資
測試資料 00（最小邊界）
說明：最小輸入 m=1，不可能形成「完美拼布」。

輸入
1
abc
輸出
0

測試資料 01（基本案例）
說明："a" 和 "aaa" 形成 "aaaa"，可以拆成 "aa" + "aa"，滿足條件。

輸入

3
a
aaa
b
輸出

1
測試資料02（多組合可匹配）
說明："abcabc" 與 "abc" 可以形成 "abcabcabc"，但不符合條件。"abab" 與 "abab" 可形成 "abababab"，可以拆成 "abab" + "abab"，符合條件。

輸入

4
abcabc
abab
abc
abab
輸出

1
測試資料 03（全部可匹配）
說明：所有字串都可以兩兩匹配形成「完美拼布」。

輸入

3
xyxy
xy
xyxyxyxy
輸出

3
測試資料 04（長字串測試）
說明：測試長度較大的字串，確保程式正確性。

輸入

3
abcabcabcabc
abcabc
abcabcabcabc
輸出

1
這些測資涵蓋：

最小邊界

單一可匹配組合

部分可匹配組合

全部可匹配組合

長字串測試



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2