d518: 文字抄寫 II
Tags: hash
出處：https://zerojudge.tw/ShowProblem?problemid=d518
提交：https://zerojudge.tw/Submissions?problemid=d518&account=allllllan123456
問題：給定至多 10000 個單字，每個單字是由至多 20 個小寫字母組成，在輸入的過程中如果當下的字串之前已經出現過，則輸出它第一次出現時被編寫的號碼，如果是第一次出現則替它編寫一個最小且尚未使用過的號碼並輸出它。
解法：這題板主很久以前是用 C 語言實作 trie，但是這樣的話會有很多繁複的操作而且還要動態配置記憶體，速度反而沒有比較快，於是今年採用 hash function 的技巧就成功同時壓低了時間和空間使用率。函式的設計沒有什麼創意，就只是將每個字母對應到 0 ~ 25 的整數所以整個單字就可以用 26 進位表示，槽的數量是經過實驗後調整的結果。
實作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <bits/stdc++.h>
using namespace std;
const int mod = 50;
int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
int N; string str;
vector<pair<string, int>> m[mod];
while (cin >> N) { int count = 1;
for (int i=0; i<mod; i++) m[i].clear();
while (N--) { cin >> str;
int sum = 0; bool find = false;
for (int i=0; i<str.length(); i++)
sum = (sum * 26 + str[i] - 'a') % mod;
for (const auto &pii: m[sum]) {
if (pii.first == str) {
cout << "Old! " << pii.second << '\n';
find = true;
break;
}
}
if (!find) {
m[sum].push_back(pair<string, int>(str, count));
cout << "New! " << count++ << '\n';
}
}
}
return 0;
}
|
結果：
alan23273850 的刷題筆記