1 条题解

  • 0
    @ 2025-3-7 14:31:07
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int n;
    vector<string> words;
    vector<int> used;
    int maxLen = 0;
    
    int getoverlap(const string& a,const string& b)
    {
      int len = min(a.size(),b.size());
      for(int l = 1;l<len;++l)
      {
        if(a.substr(a.size()-l) == b.substr(0,l))
        return l;
      }
      return 0;
    }
    void dfs(string dragon)
    {
      maxLen = max(maxLen,(int)dragon.size());
      for(int i = 0;i<n;i++)
      {
        if(used[i]<2)
        {
          int overlap = getoverlap(dragon,words[i]);
          if(overlap > 0 && overlap<min(dragon.size(),words[i].size())){
            used[i]++;
            dfs(dragon+words[i].substr(overlap));
            used[i]--;
          }
        }
      }
    }
    int main()
    {
      cin>>n;
      words.resize(n);
      used.resize(n,0);
      for(int i = 0;i<n;i++)
      {
        cin>>words[i];
      }
      char startChar;
      cin>>startChar;
      for(int i = 0;i<n;i++)
      {
        if(words[i][0] == startChar)
        {
          used[i]++;
          dfs(words[i]);
          used[i]--;
        }
      }
      cout << maxLen << endl;
      return 0;
    }
    

    信息

    ID
    5077
    时间
    1000ms
    内存
    125MiB
    难度
    3
    标签
    递交数
    34
    已通过
    22
    上传者