ZeroJudge H083: 數位占卜

占卜籤筒有 M 支籤，每一支籤為一個由英文小寫字母組成的字串。從籤筒內抽出兩支籤，若將這兩支籤上的字串 S 和 T 連接起來形成的字串可以將該字串拆成左右兩半並且內容一樣，則抽到聖筊代表神明同意，否則神明不同意或是沒回答。

例如抽出的兩支籤上的字串分別為 piep 和 ie，則相連接起來的字串為 piepie 可以拆分左右兩半為相同的字串 pie 和 pie，但抽出的兩支籤為 foo 和 bar 時則不滿足條件。

神奇的是，若抽到的兩支籤 S 和 T 為聖筊，則不管是將 T 接在 S 後面或是順序反過來接起來，都可以是聖筊，再次說明了這兩支籤有著某種神秘力量在祝福著抽到的幸運人。

例如：piep 和 ie 不管是使用 piepie 或是 iepiep 都可以拆分成兩個一樣的字串。

詢問籤筒內這 M 支籤，有幾個 Pair 可以形成聖筊。相同的兩支籤組合計算一次即可。

範例測資

範例輸入範例輸出
輸入一個正整數 M，接下來有
的字串，每個字串長度最長為 100。		輸出一個正整數，代表有幾個 Pair 滿足條件。
3
a
aba
aaa		1
5
abyyyab
y
yy
yyy
yyyy		3

解題思路

收字串的時候使用 Map 或 Set 來存哪些字串出現過。之後一個字串一個字串判斷，用 For迴圈 從 0 跑到字串的一半 +1 (因為要 Substring)，確認這個字串的第 0 個到第 i 個字元是否等於這個字串的最後 i 個字元，如果相等的話就判斷中間的字元有沒有在輸入時出現過，如果有的話答案就 +1，最後輸出答案即可。如果 Substring 太多次的話可能會 TLE 所以需要優化一下避免太多次的 Substring。

範例程式碼－ZeroJudge H083: 數位占卜

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    unordered_map<string, int>MAP;
    string s[60000] = {};
    for (int i = 0; i<N; i++)
    {
        cin >> s[i];
        MAP[s[i]]++;
    }
    int ans = 0;
    for (int i = 0; i<N; i++)
    {
        string str = s[i];
        for (int j = 1; j<(int(str.length())/2)+1; j++)
        {
            string ascertain = str.substr(j, str.length() - j - j);
            string initial = str.substr(0, j);
            string terminal = str.substr(str.length()-j, str.length());
            if (initial == terminal)
            {
                if (MAP[ascertain] >= 1)
                {
                    ans++;
                }
            }
        }
    }
    cout << ans << "\n";
}

//ZeroJudge H083
//Dr. SeanXD
標籤

相關文章

發佈留言