15 条题解

  • 25
    @ 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;
}
      • 6
        @ 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
              @ 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-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;
}
~~？？？~~
                          • -1
                            @ 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;
}
                            • -12
                              @ 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; }

                              • -44
                                @ 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
                                标签
                                递交数
                                2330
                                已通过
                                332
                                上传者
                                1. 关于
                                2. 联系我们
                                3. 隐私
                                4. 服务条款
                                5. 版权申诉
                                6. Language
                                7. 兼容模式
                                8. 主题
                                2. © 2021-2024 Hydro.ac
                                4. Worker 0 in 120ms
                                5. Hydro v4.15.0 Professional