悬赏关注求调

求解字典序最小的词链这句话，实在是没有完全理解感觉需要满足三个条件(不知道对不对)

词链是由偶数个单词组成
词链中每一个单词是经过string由小到大进行排序的

根据数据测试，我感觉

aloha.arachnid.dog.gopher

这一条数据也是满足条件的啊

还有我发现如果按照我的代码，对字符串进行排序不知道为什么还会出现结果丢失的情况

测试样例输入测试

不加排序前

CPP

aloha.arachnid
aloha.arachnid.dog
aloha.arachnid.dog.gopher
aloha.arachnid.dog.gopher.rat
aloha.arachnid.dog.gopher.rat.tiger

加完排序后

CPP

aloha.arachnid.dog.gopher.rat
aloha.arachnid.dog.gopher
aloha.arachnid.dog
aloha.arachnid
arachnid
gopher

？？？？？直接给我整懵了，调麻了

Code 并不是提交上去的答案，主要还在调试中

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
string s[N];
char h[N],t[N];
bool st[N];
string s1;
vector<int> v[N];
vector<string> ans;
bool cmp(string a,string b){
    if(a.size() != b.size()) return a.size() > b.size();
    else return a < b;
}
void dfs(int u,string str) {
    // if(str.find(".") != -1) ans.push_back(str);
    ans.push_back(str);
    st[u] = 1;
    for(int i = 0;i < v[u].size();i++) {
        int j = v[u][i];
        if(!st[j]) {
            dfs(j,str + "." + s[j]);
        }
    }
    
}



bool check(string s) {
    s += ".";
    vector<string> tmp;
    for(int i = 0,j = 0;i <= s.size();i++) {
        if(s[i] == '.') {
            string t1 = s.substr(j,i - j);
            if(tmp.size() && t1 < tmp.back()) return false;
            tmp.push_back(t1);
            j = i + 1;
        }
    }

    if(tmp.size() % 2 == 1) return false;
    return true;
}

int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) {
        cin >> s[i];
        h[i] = s[i][0],t[i] = s[i][s[i].size() - 1];
    }


    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            if(i != j) {
                if(t[i] == h[j]) v[i].push_back(j);
                // else if(h[i] == t[j]) v[j].push_back(h[i]);
            }
        }
    }

    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) st[i] = 0;
        dfs(i,s[i]);
    }

    // sort(ans.begin(),ans.end(),cmp);

    for(int i = 1;i <= n;i++) cout << ans[i] << endl;
    // for(int i = 1;i <= n;i++) {
    //     if(check(ans[i])) {
    //         cout << ans[i] << endl;
    //         return 0;
    //     }
    // }

    // cout << "***" << endl;
    
    
    return 0;
}

讨论操作

回复

相关推荐

悬赏关注求调