Luogu p3065 [usaco12dec]first! G problem solution

Luogu P3065 [USACO12DEC]First! G Answer key

Topic link ：P3065 [USACO12DEC]First! G

The question ：

Bessie I've been studying strings . She found that , By changing the order of the alphabet , She can arrange strings according to the changed alphabet （ Dictionary order, size order ）.

for example ,Bessie Find out , For character strings “omm”,“moo”,“mom” and “ommnom”, She can use the standard alphabet “mom” In the first place （ That is, the dictionary order is the smallest ）, She can also use the alphabet “abcdefghijklonmpqrstuvwxyz” bring “omm” In the first place . However ,Bessie I can't think of any way （ Change the order of the alphabet ） bring “moo” or “ommnom” In the first place .

Next, let's reorder the alphabet to figure out which strings are first in the input （ That is, the dictionary order is the smallest ）, To help Bessie.

To compute a string X And string Y A rearranged order of letters , First find their first different letter X[i] And Y[i], Compare in alphabetical order after rearrangement , if X[i] Than Y[i] First , be X The dictionary order of Y Small , namely X be ranked at Y front ; If there are no different letters , Then compare X And Y length , if X Than Y short , be X The dictionary order of Y Small , namely X be ranked at Y front .
$$\sum \left|S_i\right|\le 3\times 10^5$$

obviously trie Tree save string

For each string , We all assume that it can be a character with the minimum lexicographic order

Then traverse each of its characters in turn , Make them the smallest possible

Concrete , For characters $u$ , If we want it to be better than $v$ The dictionary order is small ,

We can $u$ towards $v$ Even a directed side

Obviously, the situation without solution will form a ring , This can be used topo To judge

It is worth noting that , If the substring of a string also exists in the input data , Then it must have no solution

Time complexity $O(26\times \sum |S_i|)$

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(3e4+15)
#define M (int)(3e5+15)
int n,ans;
string s[N];
bool ok[N];
struct Trie
{
    
    int tot,trie[M][26],ed[M],e[35][35],in[26];
    queue<int> q;
    void insert(string str)
    {
    
        int u=0; 
        for(int i=0; i<str.size(); i++)
        {
    
            int c=str[i]-'a';
            if(!trie[u][c])trie[u][c]=++tot;
            u=trie[u][c];
        }
        ed[u]=1;
    }
    void topo()
    {
    
        while(!q.empty())q.pop();
        for(int i=0; i<26; i++)
            if(!in[i])q.push(i);
        while(!q.empty())
        {
    
            int u=q.front();q.pop();
            for(int c=0; c<26; c++)
                if(e[u][c]&&(!(--in[c])))
                    q.push(c);
        }
    }
    bool solve(string str)
    {
    
        int u=0;
        memset(e,0,sizeof(e));
        memset(in,0,sizeof(in));
        for(int i=0; i<str.size(); i++)
        {
    
            if(ed[u])return 0;
            int c=str[i]-'a';
            for(int j=0; j<26; j++)
            {
    
                if(j!=c&&trie[u][j]&&!e[c][j])
                    e[c][j]=1,++in[j];
            }
            u=trie[u][c];
        }
        topo();
        for(int i=0; i<26; i++)
            if(in[i])return 0;
        return 1;
    }
}tr;
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
    {
    
        cin >> s[i];
        tr.insert(s[i]);
    }
    for(int i=1; i<=n; i++)
        if(tr.solve(s[i]))
        {
    
            ++ans;
            ok[i]=1;
        }
    cout << ans << '\n';
    for(int i=1; i<=n; i++)
        if(ok[i])cout << s[i] << '\n';
    return 0;
}

Reprint please explain the source