fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define all(x) x.begin(), x.end()
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace __gnu_pbds;
  9. template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  10. template <typename T, typename R> using o_map = tree<T, R, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  11. typedef long long ll;
  12.  
  13. #define inf 1e9
  14. #define MOD 1000000007
  15. #define vint vector<int>
  16. #define vll vector<ll>
  17. #define no cout << "NO" << endl;
  18. #define yes cout << "YES" << endl;
  19.  
  20. string s;
  21. int n;
  22. vector<vector<set<string>>> dp;
  23.  
  24. set<string> f(int i, int type) {
  25.     if (i >= n) return {""} ;
  26.     if (i == n - 1) {
  27.         return {string(1, s[n-1])};
  28.     }
  29.     bool test =( dp[i][type].size() == 1  && ((*(dp[i][type].begin())) == ""))   ;
  30.     if (!test) {
  31.         return dp[i][type];
  32.     }
  33.  
  34.     set<string>& st = dp[i][type];
  35.     st.insert(s.substr(i, n - i));
  36.  
  37.  
  38.  
  39.     if (type == 0) {
  40.         set<string> st1 = f(i+1, 0);
  41.         st.insert(all(st1));
  42.         char c = s[i];
  43.         set<string> st2 = f(i+2, 1);
  44.         for (auto &e : st2) {
  45.             string s1 = string(1, c) + e;
  46.             st.insert(s1);
  47.         }
  48.         return st ;
  49.     }
  50.     set < string > st2 = f(i+1 , 1) ;
  51.     st.insert(all(st2)) ;
  52.  
  53.     return st;
  54. }
  55.  
  56. void solve() {
  57.     cin >> n;
  58.     cin >> s;
  59.     dp.assign(n, vector<set<string>>(2, {""}));
  60. //    dp[0][0] = {"a", "b"} ;
  61.     set<string> ans = f(0, 0);
  62.     ll res= ans.size() ;
  63.     ans.erase("");
  64.     for (auto e : s ) {
  65.         ans.insert(string(1,e));
  66.     }
  67.     cout << ans.size() << endl;
  68. }
  69.  
  70. int main() {
  71.     ios::sync_with_stdio(false);
  72.     cin.tie(nullptr);
  73.  
  74. #ifndef ONLINE_JUDGE
  75.     freopen("input.txt", "r", stdin);
  76.     freopen("output.txt", "w", stdout);
  77. #endif
  78.  
  79.     int t = 1;
  80.     cin >> t;
  81.     while (t--) {
  82.         solve();
  83.     }
  84.     return 0;
  85. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/nbDut7
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!