H1001【模板】字典树 1 题解

本题解将会分成不同的方法与不同的分数来讲解，请勿跳读。

1. set 做法（50分）

每次读入字符串，将该字符串 insert 到 set 容器当中，由于 set 会自动去重，最后输出该容器的 size 即可。

代码详见下方：

#include <bits/stdc++.h>
using namespace std;
set<string> st;
int n; string s;
int main() {
    cin >> n;
    while (n--) cin >> s, st.insert(s);
    cout << st.size() << "\n";
    return 0;
}

2. map 做法（50分）

map 的 key 是 string 类型，value 是 bool 类型，记录该字符串是否之前被记录过。

代码详见下方：

#include <bits/stdc++.h>
using namespace std;
map<string, bool> mp;
int n, ans;
string s;
int main() {
    cin >> n;
    while (n--) {
        cin >> s;
        if (!mp[s]) {
            ans++;
            mp[s] = true;
        }
    }
    cout << ans << "\n";
    return 0;
}

3. unordered_set 做法（80分）

由于 unordered_set 会比 set 略快，所以超时的点会变少。

代码详见下方：

#include <bits/stdc++.h>
using namespace std;
unordered_set<string> st;
int n; string s;
int main() {
    cin >> n;
    while (n--) cin >> s, st.insert(s);
    cout << st.size() << "\n";
    return 0;
}

4. unordered_map 做法（100分）

由于 unordered_map 会比 map 快，所以正确 的点数增多。

代码详见下方：

#include <bits/stdc++.h>
using namespace std;
unordered_map<string, bool> mp;
int n, ans;
string s;
int main() {
    cin >> n;
    while (n--) {
        cin >> s;
        if (!mp[s]) {
            ans++;
            mp[s] = true;
        }
    }
    cout << ans << "\n";
    return 0;
}

5. 字符串哈希（100分）

采用字符串哈希，但是大质数千万不要开成 $998244353$，会费的！

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1024;
const int mod = 1987806193;
#define int long long
int n, ans;
string s;
vector<int> vt;
int Hash(string s) {
	int res = 0;
	for (char ch : s) res = (ch + res * 256) % mod;
	return res; 
}
#undef int
int main() {
	#define int long long
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	while (n--) {
		cin >> s;
		vt.emplace_back(Hash(s));
	}
	sort(vt.begin(), vt.end());
	ans = unique(vt.begin(), vt.end()) - vt.begin();
	cout << ans << "\n";
	return 0;
}

本题解就到这里了，写题解不容易，点个赞再走吧！

RP++