B. Substrings Sort

题目链接

Codeforces Round #486 (Div. 3)--B. Substrings Sort

题解

基础题,题意大概是将给定的字符串排序,使前面的字符串为后面字符串的字串,如果无法完成排序,输出NO。
数据规模非常小,用类似冒泡排序的做法,如果后一个是前一个的字串,交换顺序,重复执行,最后两两判断是否为字串。另一种思路是先将字符串按照长度排序,然后两两判断是否为字串。

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
using namespace std;
int n, k;
string a[105];
bool b[105];
vector<int>sx;
int main() {
    cin >> n ;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n-1; j++) {
            if (a[j + 1].find(a[j])==-1)
                swap(a[j + 1], a[j]);
        }
    }
    bool boo = true;
    for (int i = 1; i <= n - 1; i++) {
        if (a[i + 1].find(a[i]) == -1)boo = false;
    }
    if (boo) {
        cout << "YES" << endl;
        for (int i = 1; i <= n; i++) {
            cout << a[i] << endl;
        }
    }
    else cout << "NO" << endl;
}

标签: strings, sortings

添加新评论