本文主要是介绍bzoj3012[Usaco2012 Dec]First! 一号单词，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3012
题目大意：
给n个字符串，问如果重新定义英文字符的顺序（就是重定义字典序），有哪些单词可能排在字典的第一名
举例来说，假设有四个单词：omm，moo，mom 和ommnom，如果奶牛定义o 在m 之前，则omm 可排第一，如果定义m 在o 之前，则mom 可排第一，但余下两个单词是无论如何不可能排在第一的。
题解：
trie+拓扑
辣鸡的OxQ自以为trie+贪心能轻松一A，结果只有一半的分，啊一定是哪里又sb打错了，调调调！what???数据辣磨大???不怕！调调调！于是调了一下午QwQ讲真，眼睛都花了，感觉离近视不远了。。。当我调出来的时候。。(我真的调出来了)发现想法有bugQwQ不能贪心QwQ啊悲伤
==============正解分割线===============
按输入建trie树啦。
对于一个字符串来说，要想排第一，首先没有其他的字符串是它的前缀，那么就走一下字典树，遇到了标记的话就说明有人是它前缀，就直接判断为不可以啊。
其次的话，它字符的优先度要比和它有着相同前缀的高。也就是说，在同一个父亲下，这个儿子要比其他兄弟的优先度高。那么我们就连一条有向边，设为x->y表示x的优先度比y高。如果出现环就说明有矛盾啊，冲突了，就不可以了。
没想到每一个串的长度不超过20..以为要开三万*三十万
搞的我都不敢用字符数组存.输入的时候.把所有串都连到了一起，记录了每个串的长度之后，每次处理都搞什么起始位置啊烦死！输出的时候就一个一个字符输出,,慢出天际！然后我就交去bzoj上卡评测了8s多倒数第二..我简直佩服自己。讲真，知道能开三万*20之后，改了交，六百多毫秒..差得不是一点半点！瞬间Rank10...(所以拿我代码对拍的时候不要出20+的字符串 不然帮我把注释删了弄回八秒多那个 此处@GDXB
下面代码里屏蔽的就是那个八秒多的输入输出和处理，标记起始位置的那个st我还没删，感受一下我的怨念！
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 300010
#define N 30010struct node
{int son[26];bool cnt;
}tr[maxn];int tlen;
int len[N];
char s[N][20];
//char s[maxn+N];
int sum,rt,rk[30];
void insert(int c,int st)
{int i,now=rt;len[c]=strlen(s[c]);// len[c]=strlen(s)-sum;for (i=0;i<len[c];i++){int k=s[c][i]-'a';// int k=s[i+st]-'a';if (tr[now].son[k]!=0) now=tr[now].son[k];else {tr[now].son[k]=++tlen;now=tlen;}}tr[now].cnt=1;
}
queue<int > q;
bool v[30][30];
int ru[30],chu[30][30];//入度 出度及连出去的边
bool top()
{int cnt=0;for (int i=0;i<26;i++) if (!ru[i]) {q.push(i);cnt++;}while (!q.empty()){int x=q.front();q.pop();for (int i=1;i<=chu[x][0];i++)if (ru[chu[x][i]]){ru[chu[x][i]]--;if (!ru[chu[x][i]]) {q.push(chu[x][i]);cnt++;}}}if (cnt==26) return true;return false;
}
bool bub(int c,int st)//走一下trie树
{int now=rt,i=0,j;for (i=0;i<len[c];i++){int k=s[c][i]-'a';// int k=s[i+st]-'a';if (tr[now].cnt) return false;//发现有标记了for (j=0;j<26;j++) if (j!=k && tr[now].son[j]!=0) if (!v[k][j]){v[k][j]=1;chu[k][++chu[k][0]]=j;ru[j]++;}now=tr[now].son[k];}return true;
}
bool bo[N];
int main()
{//freopen("first.in","r",stdin);//freopen("first.out","w",stdout);int n,i,st,cnt;scanf("%d",&n);tlen=rt=1;sum=st=0;for (i=1;i<=n;i++){scanf("%s",s[i]);// scanf("%s",s+sum);insert(i,st);// sum+=len[i];st=sum;}cnt=0;//st=0;memset(bo,false,sizeof(bo));for (i=1;i<=n;i++){memset(v,0,sizeof(v));memset(ru,0,sizeof(ru));memset(chu,0,sizeof(chu));if (bub(i,st)){if (top()) {cnt++;bo[i]=true;}}//st+=len[i];}//st=0;printf("%d\n",cnt);for (i=1;i<=n;i++){if (bo[i]){printf("%s",s[i]);// for (int j=st;j<st+len[i];j++) // printf("%c",s[j]);printf("\n");}// st+=len[i];}return 0;
}这篇关于bzoj3012[Usaco2012 Dec]First! 一号单词的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
