wa#12求助
查看原帖
wa#12求助
1021784
ethanliu9楼主2024/5/2 14:52
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <deque>
using namespace std;
vector<vector<int>> a(27);
int pa(string sp1, string sp2)
{
    for (int i = 0; i < min(sp1.size(), sp2.size()); i++)
    {
        if (sp1[i] != sp2[i])
        {
            a[sp1[i] - 'a'].push_back(sp2[i] - 'a');
            return 1;
        }
    }
    if (sp1.size() < sp2.size())
        return 0;
    return 1;
}
int main()
{
    int n;
    cin >> n;
    vector<string> s(n + 2, "");
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    for (int i = 1; i < n; i++)
    {
        // cout << s[i] << " " << s[i - 1] << endl;
        if (!pa(s[i], s[i - 1]))
        {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    // for (int i = 0; i < 26; i++)
    // {
    //     for (int j = 0; j < a[i].size(); j++)
    //     {
    //         cout << char(i + 'a') << " " << char(a[i][j] + 'a') << endl;
    //     }
    // }
    int cnt = 26;
    vector<int> ans;
    while (cnt--)
    {
        int d = 0, co = 0;
        for (int i = 0; i < 26; i++)
        {
            if (a[i].empty())
            {
                a[i].push_back(-1);
                d = i;
                co = 1;
                break;
            }
        }
        if (co == 0)
        {
            cout << "Impossible" << endl;
            return 0;
        }
        // cout << d << endl;
        ans.push_back(d);
        for (int i = 0; i < 26; i++)
        {
            for (int j = 0; j < a[i].size(); j++)
                if (a[i][j] == d)
                {
                    a[i].erase(a[i].begin() + j);
                }
        }
    }
    // for (int i = 0; i < ans.size(); i++)
    // {
    //     cout << char(ans[i] + 'a') << endl;
    // }
    string anss;
    vector<int> ton(30, 0);
    for (int i = 0; i < ans.size(); i++)
    {
        anss += (ans[i] + 'a');
        ton[ans[i]] = 1;
    }
    for (int i = 0; i < 26; i++)
    {
        if (ton[i] == 0)
        {
            anss += (ans[i] + 'a');
        }
    }
    cout << anss;
}
2024/5/2 14:52
加载中...