这题的第一反应做法肯定是如题面所说: 字符串 hash
具体做法:
将每一个字符串化为一个 k 进制数, 并取模一个大素数 (这个素数要够大, 以免发生 hash 碰撞), 存入数组并判重.
代码:
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- typedef long long ll;
- const ll mod = 200512223;
- const ll base = 130;
- ll pre[10001];
- char s[10001];
- ll hashs(char s[]) {
- int len = strlen(s);
- int ans = 0;
- for (int i = 0;i <len;i++) {
- ans = (ans * base + (ll) s[i]) % mod;
- }
- return ans;
- }
- int main() {
- int n;
- cin>> n;
- for (int i = 1;i <= n;i++) {
- cin>> s;
- int ans = hashs(s);
- pre[i] = ans;
- }
- sort(pre+1,pre+1+n);
- int sum = 0;
- for (int i = 1;i <= n;i++) {
- if (pre[i] != pre[i-1]) {
- sum++;
- }
- }
- cout <<sum;
- return 0;
- }
然后! 今天在复习之前的课件, 突然发现了 map 的一种骚操作:
map 可以自动去重, 所以只要新建一个 string,int 的 map, 并将每一个字符串存入 map, 最后输出 map 的个数就可以了!
代码:
- #include <string>
- #include <iostream>
- #include <map>
- #define _for(i,a,b) for (register int i = a;i <= b;i++)
- using namespace std;
- map <string,int> m;
- int n,cnt;
- string a;
- int main() {
- cin>> n;
- _for(i,1,n) {
- cin>> a;
- m[a] = ++cnt;
- }
- cout << m.size();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2943072.html