18 条题解

  • 27
    @ 2021-10-2 15:12:45

    标准的数组 Trie 。

    #include <bits/stdc++.h>

using namespace std;

int n, p = 1, trie[10000005][26], size[10000005];
char s[4000005];

void insert(int u, const char* s) {
    if (!strlen(s)) {
        size[u] = 1;
        return;
    }
    if (!trie[u][s[0] - 'a']) trie[u][s[0] - 'a'] = ++p;
    insert(trie[u][s[0] - 'a'], s + 1);
}

void calcsize(int u) {
    for (int i = 0; i < 26; i++) {
        if (trie[u][i]) {
            calcsize(trie[u][i]);
            size[u] += size[trie[u][i]];
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        insert(1, s);
    }
    calcsize(1);
    printf("%d\n", size[1]);
    return 0;
}

    Personal Homepage | Blog | OI Blog

    • 12
      @ 2021-8-26 15:24:32

      显然，这题也可以考虑字符串哈希。

      将每个字符串看成 pp 进制数,将其对 MM 取模后的结果作为哈希值。

      例如 S=abb,p=10,M=16384S=abb,p=10,M=16384 , hs=122hs=122

      通常 P=13331,131P=13331,131 M=264M=2^{64} 或者较大质数。

      我写的是拉 MM 个 vector 存另一模数的哈希值。

      int main() {
    int n;
    scanf("%d", &n);
    int ans = n;

    for (int i = 1; i <= n; ++i) {
        string str;
        cin >> str;
        int len = str.length();
        //cerr<<104<<endl;
        ll hs1 = 0, hs2 = 0;

        for (int j = 0; j < len; ++j) {
            hs1 *= p, hs2 *= p;
            hs1 += str[j], hs2 += str[j];
            hs1 %= mod1, hs2 %= mod2;
        }

        //cerr<<hs1<<' '<<hs2<<endl;
        int fl = 0;

        for (int j = 0; j < h[hs1].size(); ++j) {
            if (h[hs1][j] == hs2) {
                ans--;
                fl = 1;
                break;
            }
        }

        if (fl == 0)
            h[hs1].push_back(hs2);
    }

    cout << ans << endl;
    return 0;
}
      • 7
        @ 2022-3-3 10:47:28

        在添加字符串结尾的时候判断一下，之前是否已经是结尾，如果不是ans++，如果是就不执行++操作。最后主函数直接输出ans即可。

        #include<iostream>
using namespace std;

typedef long long ll;

const int N = 1e7;

int n,m,ans = 0;
int trie[N][26],tot = 1;
bool End[N];

void insert(string str)
{
    int len = str.length(),p = 1;
    for(int k = 0;k < len; k ++)
    {
        int ch = str[k] - 'a';
        if(trie[p][ch] == 0)
        {
            trie[p][ch] = ++ tot;
        }
        p = trie[p][ch];
    }
    if(!End[p])
    {
        End[p] = true;
        ans ++;
    }
}

string str;

int main()
{
    cin >> n;
    while(n --)
    {
        cin >> str;
        insert(str);
    }
    cout << ans << endl;
}
        • 4
          @ 2022-11-11 19:23:25

          显然，这题也能通过高效的 unordered_set 水过，其单次操作的时间复杂度均摊是 O(1)O(1) 的。

          #include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

const int MAXN = 1e6 + 5;
unordered_set<string> s;
string t;
int cnt = 0, n;

signed main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> t;
        if (s.find(t) == s.end()) {
            ++cnt;
            s.insert(t);
        }
    }
    cout << cnt << endl;
    return 0;
}
          • 4
            @ 2022-10-13 20:59:55

            优化单哈希就可以过！

            // code
#pragma GCC optimize("Ofast", "inline")
#include <bits/stdc++.h>
#define int unsigned long long
#define SIZE 200010
#define all(x) x.begin(), x.end()
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;

char s[4000005];
unordered_map<int, int> S;

signed main()
{
	signed n; scanf("%d", &n);
	for(signed i=0; i<n; i++)
	{
		scanf("%s", s);
		int x=0;
		for(signed i=0; i<strlen(s); i++) x=(x*(1<<7)+s[i]);
		S[x];
	}
	printf("%u", S.size());

    return 0;
}
            • 1
              @ 2024-11-3 17:39:36

              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分）

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

              #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++

              • 1
                @ 2023-12-25 20:33:23

                这个问题可以通过使用集合（Set）来解决。集合是一种不包含重复元素的数据结构，因此将所有的字符串放入集合中，最后统计集合的大小即可得到不同的字符串数量（50分）

                #include<bits/stdc++.h> using namespace std;

                int main() { int n; cin >> n;

                 set<string> uniqueStrings;

 for (int i = 0; i < n; i++) {
      string s;
      cin >> s;
      uniqueStrings.insert(s);
 }

 cout << uniqueStrings.size() << endl;

 return 0;

                }

                • 1
                  @ 2023-4-13 10:50:24 
                  use std::io::stdin;
use std::str::FromStr;
use std::collections::HashSet;

fn read<T: FromStr>() -> Result<T, T::Err> {
    let mut tmp = String::new();
    stdin().read_line(&mut tmp).unwrap();
    tmp.trim().parse::<T>()
}

fn main() {
    let mut len_lines = read::<i32>().unwrap();
    let mut set = HashSet::new();
    let sin = stdin();
    while len_lines > 0 {
        let mut s = String::new();
        sin.read_line(&mut s).unwrap();
        set.insert(s);
        len_lines -= 1;
    }
    println!("{}", set.len());
}
                  • 0
                    @ 2024-12-6 21:02:09

                    #include <bits/stdc++.h>

                    using namespace std;

                    int n, p = 1, trie[10000005][26], size[10000005]; char s[4000005];

                    void insert(int u, const char* s) { if (!strlen(s)) { size[u] = 1; return; } if (!trie[u][s[0] - 'a']) trie[u][s[0] - 'a'] = ++p; insert(trie[u][s[0] - 'a'], s + 1); }

                    void calcsize(int u) { for (int i = 0; i < 26; i++) { if (trie[u][i]) { calcsize(trie[u][i]); size[u] += size[trie[u][i]]; } } }

                    int main() { std::ios::sync_with_stdio(false); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%s", s); insert(1, s); } calcsize(1); printf("%d\n", size[1]); return 0; }

                    • 0
                      @ 2024-10-10 20:25:55 
                      #include<bits/stdc++.h>
using namespace std;
int read();
int n,ans;
string st;
unordered_map <string,bool> vis;
int main()
{
	n=read();
	while(n--)
	{
		cin>>st;
		if(!vis[st]) ans++,vis[st]=1;
	}
	cout<<ans;
	return 0;
}
int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
                      • 0
                        @ 2024-9-19 21:43:22

                        让我们有请，unordered_map ！！！

                        #include<bits/stdc++.h>
using namespace std;
int read();
int n,ans;
string st;
unordered_map <string,bool> vis;
int main()
{
	n=read();
	while(n--)
	{
		cin>>st;
		if(!vis[st]) ans++,vis[st]=1;
	}
	cout<<ans;
	return 0;
}
int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
                        • 0
                          @ 2024-7-26 14:38:18

                          umap 秒了：

                          #include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, ans = 0;
unordered_map<string, bool> Map;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        string s; cin >> s;
        if(!Map[s]) Map[s] = true, ans++;
        else continue;
    }
    cout << ans << endl;
    return 0;
}
                          • 0
                            @ 2024-6-23 9:59:15 
                            #include <bits/stdc++.h>
using namespace std;

int n, cnt = 1, t[10000005][26], info[10000005], ans;
string s;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int u = 1;
        cin >> s;
        for (auto c : s) {
            if (t[u][c - 'a'] == 0) t[u][c - 'a'] = ++cnt;
            u = t[u][c - 'a'];
        }
        if (!info[u]) ans++, info[u] = 1;
    }
    cout << ans;
    return 0;
}
                            • 0
                              @ 2023-8-8 11:00:37

                              STL轻松水过

                              #include<bits/stdc++.h>
using namespace std;
int n; 
unordered_map<string,bool> mp;
int cnt=0;
string s;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	while(n--)
	{
		cin>>s;
		if(mp[s]==0)
			cnt++;
		mp[s]=1;
	}
	cout<<cnt;
	return 0;
}
                              • 0
                                @ 2023-3-23 20:07:35 
                                #include<iostream>
using namespace std;

typedef long long ll;

const int N = 1e7;

int n,m,ans = 0;
int trie[N][26],tot = 1;
bool End[N];

void insert(string str)
{
    int len = str.length(),p = 1;
    for(int k = 0;k < len; k ++)
    {
        int ch = str[k] - 'a';
        if(trie[p][ch] == 0)
        {
            trie[p][ch] = ++ tot;
        }
        p = trie[p][ch];
    }
    if(!End[p])
    {
        End[p] = true;
        ans ++;
    }
}

string str;

int main()
{
    cin >> n;
    while(n --)
    {
        cin >> str;
        insert(str);
    }
    cout << ans << endl;
}
~~？？？~~
                                • -2
                                  @ 2023-10-27 22:54:35 
                                  #include <bits/stdc++.h>

using namespace std;

int n, p = 1, trie[10000005][26], size[10000005];
char s[4000005];

void insert(int u, const char* s) {
    if (!strlen(s)) {
        size[u] = 1;
        return;
    }
    if (!trie[u][s[0] - 'a']) trie[u][s[0] - 'a'] = ++p;
    insert(trie[u][s[0] - 'a'], s + 1);
}

void calcsize(int u) {
    for (int i = 0; i < 26; i++) {
        if (trie[u][i]) {
            calcsize(trie[u][i]);
            size[u] += size[trie[u][i]];
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        insert(1, s);
    }
    calcsize(1);
    printf("%d\n", size[1]);
    return 0;
}
                                  • -13
                                    @ 2022-5-13 9:13:03

                                    #include using namespace std; string s; string s2; int main(){ int n,i,j,count; cin>>n; getline(cin,s); int l=s.length(); for(i=0;i<n-1;i++){ for(j=0;j<l;j++){ getline(cin,s2); if(s[j]==s2[j]) continue; else{ count++; break; } } } return 0; }

                                    • -46
                                      @ 2021-8-24 14:37:20

                                      #include <bits/stdc++.h> using namespace std; unordered_set s; string a; int n; int main() { cin.tie(0), cout.tie(0), ios::sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a, s.insert(a); cout << s.size(); return 0; } //记得开O2

                                      • 1

                                      【模板】字典树 1

                                      信息

                                      ID
                                      180
                                      时间
                                      300~1000ms
                                      内存
                                      1024MiB
                                      难度
                                      3
                                      标签
                                      递交数
                                      2750
                                      已通过
                                      368
                                      上传者
                                      1. 关于
                                      2. 联系我们
                                      3. 隐私
                                      4. 服务条款
                                      5. 版权申诉
                                      6. Language
                                      7. 兼容模式
                                      8. 主题
                                      2. © 2021-2024 Hydro.ac
                                      4. Worker 2 in 138ms
                                      5. Hydro v4.18.2 Professional