12 条题解

  • 24
    @ 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;
        }
        
        • 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;
          }
          
          • 2
            @ 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;
            }
            
            • 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-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());
                      }
                      
                      • -9
                        @ 2022-5-13 9:13:03

                        #include<iostream> 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; }

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

                          #include <bits/stdc++.h> using namespace std; unordered_set<string> 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

                          信息

                          ID
                          180
                          时间
                          300~1000ms
                          内存
                          1024MiB
                          难度
                          3
                          标签
                          递交数
                          1781
                          已通过
                          253
                          上传者