14 solutions

  • 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

    • 13
      @ 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} 或者较大质数。

      我写的是拉 MMvector 存另一模数的哈希值。

      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;
        }
        
        • 5
          @ 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;
          }
          
          • 5
            @ 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;
            }
            
            • 2
              @ 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
                @ 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;
                }
                
                • 1
                  @ 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;
                  }
                  
                  • 1
                    @ 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;
                    }
                    
                    • 1
                      @ 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;
                      }
                      ~~???~~
                      
                      • 0
                        @ 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;
                        }
                        
                        • 0
                          @ 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());
                          }
                          
                          • -10
                            @ 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; }

                            • -41
                              @ 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

                              Information

                              ID
                              180
                              Time
                              300~1000ms
                              Memory
                              1024MiB
                              Difficulty
                              3
                              Tags
                              # Submissions
                              2252
                              Accepted
                              317
                              Uploaded By