Advertisement
Dang_Quan_10_Tin

AUTOTYPE

Aug 7th, 2022
990
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.00 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. using ull = unsigned long long;
  7.  
  8. template <class T>
  9. void read(T &x)
  10. {
  11.     x = 0;
  12.     register int c;
  13.     while ((c = getchar()) && (c > '9' || c < '0'))
  14.         ;
  15.     for (; c >= '0' && c <= '9'; c = getchar())
  16.         x = x * 10 + c - '0';
  17. }
  18.  
  19. constexpr bool typetest = 0;
  20. constexpr int N = 1e5 + 5;
  21.  
  22. // mot node cua cay trie
  23. struct node
  24. {
  25.     node *child[26];
  26.     int keystrokes, numberOfString;
  27.     node()
  28.     {
  29.         for (int i = 0; i < 26; ++i)
  30.             child[i] = NULL;
  31.         keystrokes = numberOfString = 0;
  32.     }
  33. };
  34.  
  35. // Cay trie
  36. struct Trie
  37. {
  38.     node root;
  39.  
  40.     void Add(const string &s)
  41.     {
  42.         node *a = &root;
  43.         int id = 0;
  44.  
  45.         while (id <= (int)s.size())
  46.         {
  47.             ++a->numberOfString;
  48.  
  49.             if (id == (int)s.size())
  50.                 break;
  51.  
  52.             if (!(a->child[s[id] - 'a']))
  53.                 a->child[s[id] - 'a'] = new node;
  54.  
  55.             a = a->child[s[id] - 'a'];
  56.             ++id;
  57.         }
  58.     }
  59.  
  60.     int dfs(node *a, int dep = 0)
  61.     {
  62.         int ans(0), cnt(0);
  63.  
  64.         for (int i = 0; i < 26; ++i)
  65.             if (a->child[i])
  66.             {
  67.                 if ((a != &root) && (a->child[i]->numberOfString) == (a->numberOfString))
  68.                     a->child[i]->keystrokes = a->keystrokes;
  69.                 else
  70.                     a->child[i]->keystrokes = a->keystrokes + 1;
  71.  
  72.                 cnt += a->child[i]->numberOfString;
  73.                 ans += dfs(a->child[i], dep + 1);
  74.             }
  75.  
  76.         // cout << dep << ": " << (a->keystrokes) << " " << a->numberOfString << " " << cnt << "\n";
  77.  
  78.         ans += (a->numberOfString - cnt) * (a->keystrokes);
  79.  
  80.         return ans;
  81.     }
  82.  
  83.     int GetKeyStroke()
  84.     {
  85.         return dfs(&root);
  86.     }
  87.  
  88.     void Delete(node *a)
  89.     {
  90.         for (int i = 0; i < 26; ++i)
  91.             if (a->child[i])
  92.             {
  93.                 Delete(a->child[i]);
  94.                 delete a->child[i];
  95.             }
  96.     }
  97.  
  98.     void Destroy()
  99.     {
  100.         Delete(&root);
  101.     }
  102. };
  103.  
  104. int n;
  105. string s[N];
  106.  
  107. void Solve();
  108.  
  109. void Read()
  110. {
  111.     while (cin >> n)
  112.     {
  113.  
  114.         for (int i = 1; i <= n; ++i)
  115.             cin >> s[i];
  116.  
  117.         Solve();
  118.     }
  119. }
  120.  
  121. void Solve()
  122. {
  123.     Trie f;
  124.     for (int i = 1; i <= n; ++i)
  125.         f.Add(s[i]);
  126.  
  127.     cout << fixed << setprecision(2) << (ld)1.0 * f.GetKeyStroke() / n << "\n";
  128.  
  129.     f.Destroy();
  130. }
  131.  
  132. int32_t main()
  133. {
  134.     ios::sync_with_stdio(0);
  135.     cin.tie(0);
  136.     cout.tie(0);
  137.     if (fopen("tests.inp", "r"))
  138.     {
  139.         freopen("test.inp", "r", stdin);
  140.         freopen("test.out", "w", stdout);
  141.     }
  142.  
  143.     int t(1);
  144.     if (typetest)
  145.         cin >> t;
  146.     for (int _ = 1; _ <= t; ++_)
  147.     {
  148.         // cout << "Case #" << _ << endl;
  149.         Read();
  150.         // Solve();
  151.     }
  152.     // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  153. }
  154.  
  155. /*
  156. 1
  157. 3
  158. 1 0
  159. 1 1 2
  160. 0 3 4
  161. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement