[luogu P3065] [USACO12DEC]第一!First!
[luogu P3065] [USACO12DEC]第一!First!
题目描述
Bessie has been playing with strings again. She found that by changing the order of the alphabet she could make some strings come before all the others lexicographically (dictionary ordering).
For instance Bessie found that for the strings "omm", "moo", "mom", and "ommnom" she could make "mom" appear first using the standard alphabet and that she could make "omm" appear first using the alphabet "abcdefghijklonmpqrstuvwxyz". However, Bessie couldn't figure out any way to make "moo" or "ommnom" appear first.
Help Bessie by computing which strings in the input could be lexicographically first by rearranging the order of the alphabet. To compute if string X is lexicographically before string Y find the index of the first character in which they differ, j. If no such index exists then X is lexicographically before Y if X is shorter than Y. Otherwise X is lexicographically before Y if X[j] occurs earlier in the alphabet than Y[j].
给出n个字符串,问哪些串能在特定的字母顺序中字典序最小。
输入输出格式
输入格式:
Line 1: A single line containing N (1 <= N <= 30,000), the number of strings Bessie is playing with.
- Lines 2..1+N: Each line contains a non-empty string. The total number of characters in all strings will be no more than 300,000. All characters in input will be lowercase characters 'a' through 'z'. Input will contain no duplicate strings.
输出格式:
Line 1: A single line containing K, the number of strings that could be lexicographically first.
- Lines 2..1+K: The (1+i)th line should contain the ith string that could be lexicographically first. Strings should be output in the same order they were given in the input.
说明
The example from the problem statement.
Only "omm" and "mom" can be ordered first.
来点不是很难又不是很水的题目。
这一题最开始的想法就是建一棵字典树trie,然后,对于每一个单词,沿着字典树中他的路径走下去。
那怎么判断是否可行?如果按照贪心的想法,比如当前的节点优先级设为剩下(除去前几个字母)最高的,这样显然会有反例。
那么,我们想,安排字母的顺序,优先级,我们想到了topo排序。
由于每一个节点下面,非当前路径上的点的优先级小于路径上的点,所以就可以建一条边。
在这里可以直接用邻接矩阵,更方便,且效率也没差到哪里(因为可能有很多边)。
然后,就进行topo排序了,如果可行就可以了。
还有需要注意的是,比如有两个字符串:
wzz
wzzlihai
那么,wzzlihai也不能以某种顺序排到第一位。
那这个怎么判呢?在每个单词结束的时候都在结束点打个“结束”标记。
然后询问时,如果路径上某一个点(非最后一个)上有“结束”标记,则return 0。
code:
#pragma GCC optimize(2) #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <queue> #define ms(a,x) memset(a,x,sizeof a) typedef long long LL; namespace fastIO { #define puc(c) putchar(c) inline int read() { ,f=; char ch=getchar(); ') { if (ch=='-') f=-f; ch=getchar(); } ') { x=(x<<)+(x<<)+ch-'; ch=getchar(); } return x*f; } template <) { T f=; char ch=getchar(); ') { if (ch=='-') f=-f; ch=getchar(); } ') { x=(x<<)+(x<<)+ch-'; ch=getchar(); } x*=f; } ]; template <class T> inline void write(T x) { ) { puc('); return; } ) { x=-x; puc('-'); } ; x; x/=) w[++cnt]=x%; ); } inline void newline() { puc('\n'); } inline void newblank() { puc(' '); } } namespace OJ{ void Online_Judge() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif } } using std::string; using std::queue; ,L=,A=; int n,cnt,len[N]; bool vis[N]; string s[N]; char ss[L]; int tot,f[A][A],dg[N]; queue <int> q; #define TrieNode node class TrieNode { private: bool end; node *ch[A]; public: node() { end=,ms(ch,); } inline bool topo() { while (!q.empty()) q.pop(); ; i<A; ++i) { ; j<A; ++j) { if (f[i][j]) ++dg[j]; } } ; i<A; ++i) { ) q.push(i); } ; for (int x; !q.empty(); ) { x=q.front(),q.pop(); ; i<A; i++) { if (f[x][i]) { --dg[i]; ) q.push(i); } } } ; i<A; ++i) { ) ; } ; } inline void insert(node *u,char a[],int l) { ,x; i<l; ++i) { x=a[i]-'a'; ) { u->ch[x]=new node(); } u=u->ch[x]; } u->end=; } inline bool reply(node *u,char a[],int l) { ms(f,),ms(dg,); ,x; i<l; ++i) { x=a[i]-'a'; &&u->ch[x]->end) ; ; j<; ++j) { &&j!=x) f[x][j]=; } u=u->ch[x]; } return topo(); } }t,*rot; int main() { OJ::Online_Judge(); scanf(,rot=new node(); ; i<=n; ++i) { scanf("%s",ss),len[i]=strlen(ss); s[i]=""; ; j<len[i]; ++j) { s[i]=s[i]+ss[j]; } t.insert(rot,ss,len[i]); } ; i<=n; ++i) { ; j<len[i]; ++j) { ss[j]=s[i][j]; } cnt+=vis[i]=t.reply(rot,ss,len[i]); } printf("%d\n",cnt); ; i<=n; ++i) { if (vis[i]) { ; j<len[i]; ++j) { putchar(s[i][j]); } putchar('\n'); } } ; }
最新文章
- 初探Socket
- springmvc 表单提交
- putty+xming远程登录Ubuntu16.04图形界面
- delphi dev 汉化
- Linux文件操作常用命令整理
- html回忆(一)
- IIS7.5 发布程序后cookie丢失问题
- Android保存图片到系统图库
- python模拟http请求
- AngularJS - Apply方法监听model变化
- UIScrollView,UIView转换UIImage代码(整个view截图, 不只是可视区域)
- arc项目中使用非arc文件
- ajax 同步异步调用
- FtpClient的使用
- collection set
- eclipse如何设置成保护眼的背景色
- 关于autoconf
- 【http转https】其之三 IIS_URL重写_http重定向到https
- Java中使用LocalDate根据日期来计算年龄
- Android权限Uri.parse的几种用法(转载)