Description

Solution

首先，一个串要是最小的，别的串不能是它的前缀，且和它有相同前缀的串字典序都比他小。

Trie树是显然要用的，难点在于如何判断能否最小。其实这之中蕴含了字母间的大小关系，即同一层中，钦定的最小串的字符要比其它的大。然后就可以建一个有向图跑拓扑排序判环就行。

Code

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

#include <string>

#include <vector>

namespace wyx {

typedef int ll;

ll read() {

    ll ans = 0, fl = 1;

    char c;

    for (c = getchar(); c > '9' || c < '0'; c = getchar())

        if (c == '-') fl = -1;

    ans = c - '0';

    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())

        ans = ans * 10 + c - '0';

    return fl * ans;

}

typedef double ld;

typedef unsigned long long ull;

const int N = 30010;

struct Trie {

    int to[N * 10][26], cnt, val[N * 10];

    Trie() {

        memset(to, 0, sizeof to);

        memset(val, 0, sizeof val);

        cnt = 0;

    }

    void add(const std::string& s) {

        int len = s.length();

        int now = 0;

        for (int i = 0; i < len; ++i) {

            if (!to[now][s[i] - 'a']) to[now][s[i] - 'a'] = ++cnt;

            now = to[now][s[i] - 'a'];

        }

        val[now]++;

    }

} Tr;

struct Graph {

    std::vector<int> g[26];

    int deg[26];

    void init() {

        for (int i = 0; i < 26; ++i) g[i].clear(), deg[i] = 0;

    }

    void adde(int x, int y) {

        g[x].push_back(y);

        deg[y]++;

    }

    bool toposort() {

        std::queue<int> q;

        for (int i = 0; i < 26; ++i)

            if (deg[i] == 0) q.push(i);

        while (!q.empty()) {

            int x = q.front();

            q.pop();

            for (int i : g[x])

                if (--deg[i] == 0) q.push(i);

        }

        for (int i = 0; i < 26; ++i)

            if (deg[i]) return false;

        return true;

    }

} G;

std::string s[N];

int n, vis[N];

bool work(int x) {

    int now = 0, len = s[x].length();

    for (int i = 0; i < len; ++i) {

        if (Tr.val[now]) return false;

        for (int j = 0; j < 26; ++j) {

            if (j != s[x][i] - 'a' && Tr.to[now][j]) G.adde(s[x][i] - 'a', j);

        }

        now = Tr.to[now][s[x][i] - 'a'];

    }

    return true;

}

void main() {

    n = read();

    for (int i = 1; i <= n; ++i) std::cin >> s[i], Tr.add(s[i]);

    int cnt = 0;

    for (int i = 1; i <= n; ++i) {

        G.init();

        if (work(i) && G.toposort()) {

            vis[i] = 1;

            cnt++;

        }

    }

    printf("%d\n", cnt);

    for (int i = 1; i <= n; ++i)

        if (vis[i]) {

            std::cout << s[i] << std::endl;

        }

}

};  // namespace wyx

int main() {

    wyx::main();

    return 0;

}

巴特西

[USACO12DEC]First!

Description

Solution

Code

最新文章

热门文章