Board logo

標題: 202412潛力2-外星語 (Language) [打印本頁]
作者: may    時間: 2025-1-29 21:16     標題: 202412潛力2-外星語 (Language)

外星語 (Language)
問題敘述:
科學家收到了來自遙遠銀河另一端的外星人的信號。雖然他們還沒有解讀出信號的意思，但科學家們觀察到外星人使用著酷似我們所使用阿拉伯數字、英文字母以及運算符號的文字，也就是[0-9A-Za-z]這 62 個字元，外加’+’以及’/’的2種字元，總共64種字元。以下我們統稱這64種字元為外星人所使用的「字母」。 在一次通訊中，科學家發現外星人使用這些字母的方式跟地球非常不一樣。對外星人來說，A-Z和a-z的字母之間並不是大小寫的關係，而是完全獨立的字元；這些字母的順序也與英文的字母表順序ABC…XYZ不同，在外星語的字母表中這64種字母具有別的順序。

歷經了數次通訊之後，科學家收集到了 N 筆關於外星人姓名、書籍等依照字典順序排序的資料。所謂的字典順序就是從兩個字串的第一個字母開始比對直到找到第一個相異的字元，並使用該字元的大小關係為字串作排序。例如對英文來說car 會在cat 的前面，因為在字母表中r在t的前面。而空字元視為在所有字元前面，因此car的字典順序較cargo小。 科學家好奇外星語的字母在字母表中順序為何，請寫一支程式幫助他們。

輸入格式:  
第一列有一個整數N (1 ≤ N ≤ 105)，代表收集到了多少筆外星語的字詞。 接下來有N列，每一列有一個字串S代表科學家收集到的資料，這N個字串已經使用外星語的字典順序排好。保證每個字串只會具有前述的[0-9A-Zaz]以及’+’和’/’的64種字元，且字串長度小於10。

輸出格式:
對於全部有出現在資料中的字元種類，請依照外星語中的字典順序由小到大輸出。保證答案有唯一的順序。
輸入範例1
4
baba
nanaba
nanana
naana
輸出範例1
bna
輸入範例2
10
6/6+/
6+/6+
///++
//++/+
/+/+66
/+/+/
++66+6
++//
++//+
+++6/
輸出範例2
6/+
輸入範例3
13
A
a
a
C
+
d
1
F
8
8
2
0
k
輸出範例3
AaC+d1F820k
作者: may    時間: 2025-1-29 21:33

  1. #include<bits/stdc++.h>
  2. //#include <iostream>
  3. //#include <vector>
  4. //#include <queue>
  5. //#include <unordered_map>
  6. //#include <unordered_set>

  8. using namespace std;

  10. const int ALIEN_ALPHABET_SIZE = 64;

  12. // 取得所有可能的字母集合
  13. string valid_chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";

  15. // 建立字母的有向圖
  16. unordered_map<char, unordered_set<char>> adj;
  17. unordered_map<char, int> in_degree; // 記錄入度（被指向的次數）

  19. // 解析外星語字母順序
  20. string alien_language_order(vector<string>& words) {
  21.     unordered_set<char> unique_chars;

  23.     // 初始化所有字母的入度為 0
  24.     for (char c : valid_chars) {
  25.         in_degree[c] = 0;
  26.     }

  28.     // 找出所有出現在字串中的字母
  29.     for (const string& word : words) {
  30.         for (char c : word) {
  31.             unique_chars.insert(c);
  32.         }
  33.     }

  35.     // 建立字母之間的順序關係
  36.     for (size_t i = 0; i < words.size() - 1; ++i) {
  37.         string word1 = words[i], word2 = words[i + 1];
  38.         size_t len = min(word1.size(), word2.size());

  40.         // 找到第一個不同的字母，建立有向邊
  41.         bool found = false;
  42.         for (size_t j = 0; j < len; ++j) {
  43.             char a = word1[j], b = word2[j];
  44.             if (a != b) {
  45.                 if (adj[a].find(b) == adj[a].end()) { // 避免重複加入相同的邊
  46.                     adj[a].insert(b);
  47.                     in_degree[b]++;
  48.                 }
  49.                 found = true;
  50.                 break;
  51.             }
  52.         }

  54.         // 特殊情況：若 word1 是 word2 的前綴，則應該合法，否則排序錯誤
  55.         if (!found && word1.size() > word2.size()) {
  56.             return ""; // 不合法的排序，直接回傳空字串
  57.         }
  58.     }

  60.     // **拓樸排序（Kahn's Algorithm / BFS）**
  61.     queue<char> q;
  62.     string result;

  64.     // 將所有入度為 0 的字母加入隊列
  65.     for (char c : unique_chars) {
  66.         if (in_degree[c] == 0) {
  67.             q.push(c);
  68.         }
  69.     }

  71.     while (!q.empty()) {
  72.         char current = q.front();
  73.         q.pop();
  74.         result += current;

  76.         for (char neighbor : adj[current]) {
  77.             in_degree[neighbor]--;
  78.             if (in_degree[neighbor] == 0) {
  79.                 q.push(neighbor);
  80.             }
  81.         }
  82.     }

  84.     return result;
  85. }

  87. int main() {
  88.     int N;
  89.     cin >> N;
  90.     vector<string> words(N);

  92.     for (int i = 0; i < N; ++i) {
  93.         cin >> words[i];
  94.     }

  96.     string result = alien_language_order(words);
  97.     if (result.empty()) {
  98.         cout << "Error: Invalid input order" << endl;
  99.     } else {
  100.         cout << result << endl;
  101.     }

  103.     return 0;
  104. }
  105. /*
  106. 輸入範例1
  107. 4
  108. baba
  109. nanaba
  110. nanana
  111. naana
  112. 輸出範例1
  113. bna
  114. 輸入範例2
  115. 10
  116. 6/6+/
  117. 6+/6+
  118. ///++
  119. //++/+
  120. /+/+66
  121. /+/+/
  122. ++66+6
  123. ++//
  124. ++//+
  125. +++6/
  126. 輸出範例2
  127. 6/+
  128. 輸入範例3
  129. 13
  130. A
  131. a
  132. a
  133. C
  134. +
  135. d
  136. 1
  137. F
  138. 8
  139. 8
  140. 2
  141. 0
  142. k
  143. 輸出範例3
  144. AaC+d1F820k
  145. */
複製代碼
作者: may    時間: 2025-1-29 21:35

解題思路
建立圖的關係：

由於輸入的 N 個字串是已經按照外星語字典順序排列的，我們可以利用這些字串的前後關係來推導出字母的相對順序。
比較相鄰字串，找到第一個不同的字母 (a, b)，表示 'a' 應該出現在 'b' 之前，這構成了一條有向邊 a → b。
重複這個過程，建立整個字母的相對順序圖。
使用拓樸排序 (Topological Sorting)：

透過 Kahn’s Algorithm（BFS）或 DFS 來進行拓樸排序，確保所有字母都按照唯一的外星語順序排列。
注意：如果某個字母沒有出現在 N 個字串的任何比較中，但有出現在輸入中，則它仍然要包含在輸出結果中。
作者: may    時間: 2025-1-29 21:36

程式解析:
1. 建立有向圖
使用 unordered_map<char, unordered_set<char>> adj 來儲存字母之間的相對順序。
使用 unordered_map<char, int> in_degree 來計算每個字母的入度（被多少個字母指向）。
比較相鄰字串的第一個不同字母，假設 baba → nanaba，那麼 b 應該出現在 n 之前，因此我們加上邊 b → n，並讓 in_degree[n]++。
2. 拓樸排序
將所有入度為 0 的字母加入隊列 queue。
進行 BFS 排序，按照順序輸出字母表。
若有環（某些字母之間有矛盾），則代表輸入字典順序有誤。



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