Advertisement
Josif_tepe

Untitled

Oct 16th, 2022
941
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.66 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <bits/stdc++.h>
  4. #include <queue>
  5. #include <cstdio>
  6. #include <fstream>
  7. #include <cstring>
  8. #include <algorithm>
  9. using namespace std;
  10. const int maxn = 1e4 + 10;
  11. int n;
  12. string v[maxn];
  13. vector<pair<int, pair<string, vector<int> > > > g[1005];
  14. int dp[maxn];
  15. int backtrack[maxn];
  16. int rek(int prev_at){
  17.     if(dp[prev_at] != -1){
  18.         return dp[prev_at];
  19.     }
  20.     int ret = 0;
  21.     int sz = (int)v[prev_at].size();
  22.     vector<int> cnt(26, 0);
  23.     for(int i = 0; i < (int)v[prev_at].size(); i++){
  24.         ++cnt[v[prev_at][i] - 'A'];
  25.     }
  26.     int mxx = 0;
  27.     for(int i = 0; i < (int)g[sz + 1].size(); i++){
  28.         vector<int> cnt2 = g[sz + 1][i].second.second;
  29.         bool ok = false;
  30.         bool can = true;
  31.         for(int j = 0; j < 26; j++){
  32.             if(abs(cnt2[j] - cnt[j]) == 0) continue;
  33.             if(abs(cnt2[j] - cnt[j]) == 1 and ok == false){
  34.                 ok = true;
  35.                 continue;
  36.             }
  37.             if(abs(cnt2[j] - cnt[j]) >= 1 or ok){
  38.                 can = false;
  39.                 break;
  40.             }
  41.         }
  42.         if(can){
  43.             int tmp = rek(g[sz + 1][i].first) + 1;
  44.             if(tmp > ret) ret = tmp;
  45.             if(tmp > mxx){
  46.                 mxx = tmp;
  47.                 backtrack[prev_at] = g[sz + 1][i].first;
  48.             }
  49.         }
  50.     }
  51.     return dp[prev_at] = ret;
  52. }
  53. int main(int argc, const char * argv[]) {
  54.     ios_base::sync_with_stdio(false);
  55. //    ifstream cin("in.txt");
  56.     cin >> n;
  57.     for(int i = 0; i < n; i++){
  58.         cin >> v[i];
  59.         vector<int> cnt(26, 0);
  60.         for(int j = 0; j < (int)v[i].size(); j++){
  61.             ++cnt[v[i][j] - 'A'];
  62.         }
  63.         g[(int)v[i].size()].push_back(make_pair(i, make_pair(v[i], cnt)));
  64.          
  65. //        sort(v[i].begin(), v[i].end());
  66.          
  67.     }
  68.     memset(backtrack, -1, sizeof backtrack);
  69.     memset(dp, -1, sizeof dp);
  70.     int ret = 0;
  71.     int idx = -1;
  72.     for(int i = 0; i < n; i++){
  73.         if((int)v[i].size() <= 2 and rek(i) + 1 > ret){
  74.             ret = rek(i);
  75.             idx = i;
  76.         }
  77.     }
  78.     if(ret <= 1){
  79.         cout << 1 << endl;
  80.         cout << v[0][0] << endl;
  81.         return 0;
  82.     }
  83.     vector<string> ans;
  84. //    cout << ret + 2 << endl;
  85.     ans.push_back(string() + v[idx][0]);
  86.     ans.push_back(v[idx]);
  87.     int A = backtrack[idx];
  88.     while(A != -1){
  89.         ans.push_back(v[A]);
  90.         A = backtrack[A];
  91.     }
  92.     if(ans[0].size() == ans[1].size()){
  93.         ans.erase(ans.begin());
  94.     }
  95.     cout << (int)ans.size() << "\n";
  96.     for(int i = 0; i < ans.size(); i++){
  97.         cout << ans[i] << "\n";
  98.     }
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement