题目
E[中] 假的字符串 https://ac.nowcoder.com/acm/contest/907/E
做法
一个字符串能作为最小值最基础的条件为不能出现前缀字符串
我们需要确定一种每个字符的排名使得 \(s\) 作为最小值, 另有很多字符串 \(t\), 与 \(s\) 第一个不相同的位置可以产生一种偏序限制, 如 \(s-x,t_y,rk_x<rk_y\)
而判断是否可行直接跑拓扑排序就行
- code
- #include<bits/stdc++.h>
- typedef int LL;
- const LL maxn=300009;
- typedef std::string str;
- str s[30009],ans[30009];
- LL nod,n,tot;
- LL son[maxn][27],val[maxn],du[30];
- std::vector<LL> to[27];
- inline void Insert(str t){
- LL now(0),len(t.size());
- for(LL i=0;i<len;++i){
- LL c(t[i]-'a');
- if(!son[now][c]) son[now][c]=++nod;
- now=son[now][c];
- }
- ++val[now];
- }
- std::queue<LL> que;
- inline bool top_sort(){
- LL ret(0);
- for(LL i=0;i<26;++i) if(!du[i]) que.push(i),ret|=(1<<i);
- while(que.size()){
- LL u(que.front()); que.pop();
- for(LL i=0;i<to[u].size();++i){
- LL v(to[u][i]);
- --du[v];
- if(!du[v]) que.push(v),ret|=(1<<v);
- }
- }
- return ret==((1<<26)-1);
- }
- inline bool Check(str t){
- LL now(0),len(t.size());
- memset(du,0,sizeof(du));
- for(LL i=0;i<26;++i)
- to[i].clear();
- for(LL i=0;i<len;++i){
- LL c(t[i]-'a');
- for(LL j=0;j<26;++j){
- if(son[now][j] && j!=c){
- ++du[j];
- to[c].push_back(j); //to[j].push_back(c);
- }
- }
- if(val[now]) return false;
- now=son[now][c];
- }
- return top_sort();
- }
- int main(){
- scanf("%d",&n);
- for(LL i=1;i<=n;++i){
- std::cin>>s[i];
- Insert(s[i]);
- }
- for(LL i=1;i<=n;++i)
- if(Check(s[i]))
- ans[++tot]=s[i];
- printf("%d\n",tot);
- for(LL i=1;i<=tot;++i) std::cout<<ans[i]<<std::endl;
- return 0;
- }/*
- 6
- mcfx
- ak
- ioi
- wen
- l
- a
- */
来源: http://www.bubuko.com/infodetail-3078684.html