BZOJ3012 : [Usaco2012 Dec]First!

深碍√TFBOYSˉ_ 2022-04-10 11:24 169阅读 0赞

建立Trie，那么成为答案的串必须满足其终止节点到根路径上没有其它点。

对于Trie上每个节点维护一个bitset，表示哪些字符必须在哪些字符之前。

每到达一个可能成为答案的终止节点，对图进行拓扑排序进行判定。

时间复杂度$O(26^2N+26|S|)$。

#include<cstdio>
    #include<cstring>
    #define rep(i) for(int i=0;i<26;i++)
    const int N=30010,M=300010;
    int n,i,j,k,x,cnt,len,st[N],en[N],fin[N],ans;
    int tot,son[M][26],id[M],v[M],f[M][26];
    int g[26][26],d[26],q[30];
    char s[M],text[M];
    void dfs(int x){
      if(id[x]){
        rep(i)for(int j=d[i]=0;j<26;j++)g[i][j]=0;
        rep(i)rep(j)if(i!=j&&(f[x][i]>>j&1))g[i][j]=1,d[j]++;
        int h=1,t=0;
        rep(i)if(!d[i])q[++t]=i;
        while(h<=t){
          int x=q[h++];
          rep(i)if(g[x][i])if(!(--d[i]))q[++t]=i;
        }
        if(t==26)fin[id[x]]=1,ans++;
        return;
      }
      rep(i)if(son[x][i]){
        int y=son[x][i];
        rep(j)f[y][j]=f[x][j];
        f[y][i]|=v[x];
        dfs(y);
      }
    }
    int main(){
      scanf("%d",&n);
      for(i=1;i<=n;i++){
        scanf("%s",s);
        len=strlen(s);
        st[i]=cnt;
        for(j=x=0;j<len;x=son[x][k],j++)if(!son[x][k=text[cnt++]=s[j]-'a'])son[x][k]=++tot,v[x]|=1<<k;
        id[x]=i;
        en[i]=cnt;
      }
      dfs(0);
      for(printf("%d\n",ans),i=1;i<=n;i++)if(fin[i]){
        for(j=st[i];j<en[i];j++)putchar(text[j]+'a');
        puts("");
      }
      return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，169人围观）

还没有评论，来说两句吧...

相关阅读

相关 ❤BZOJ 2705: [SDOI2012]Longge的问题

2705: \[SDOI2012\]Longge的问题 Time Limit: 3 Sec Memory Limit: 128 MB Submit: 2007 Sol

我会带着你远行/ 2022年07月29日 08:59/ 0 赞/ 143 阅读

相关 BZOJ3012 : [Usaco2012 Dec]First!

建立Trie，那么成为答案的串必须满足其终止节点到根路径上没有其它点。对于Trie上每个节点维护一个bitset，表示哪些字符必须在哪些字符之前。每到达一个可能成为答案

深碍√TFBOYSˉ_/ 2022年04月10日 11:24/ 0 赞/ 170 阅读

相关 [BZOJ3940]:[Usaco2015 Feb]Censoring（AC自动机）

[题目传送门][Link 1] -------------------- 题目描述： FJ把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过105的字符串S。他有一个

柔光的暖阳◎/ 2022年01月10日 04:41/ 0 赞/ 202 阅读

相关 USACO翻译：USACO 2012 JAN三题（2）

USACO 2012 JAN（题目二）一、题目概览 <table> <tbody> <tr> <td> <p>中文题目名称</p> </td>

曾经终败给现在/ 2022年01月10日 03:53/ 0 赞/ 251 阅读

相关 [2018.12.6]BZOJ2809 [Apio2012]dispatching

考虑维护每一个点以及它的子树中被派遣的忍者。对于一个点,我们用类似树形DP的方式自底向上进行,先把它的所有孩子中被派遣的忍者放到一起,如果他们的薪水总和超过\\(m\\),

川长思鸟来/ 2022年01月09日 05:37/ 0 赞/ 180 阅读

相关 bzoj1604[Usaco2008 Open]Cow Neighborhoods 奶牛的邻居*

[bzoj1604\[Usaco2008 Open\]Cow Neighborhoods 奶牛的邻居][bzoj1604_Usaco2008 Open_Cow Neighbor

逃离我推掉我的手/ 2021年12月24日 19:39/ 0 赞/ 247 阅读

相关 [2018.12.6]BZOJ2809 [Apio2012]dispatching

考虑维护每一个点以及它的子树中被派遣的忍者。对于一个点,我们用类似树形DP的方式自底向上进行,先把它的所有孩子中被派遣的忍者放到一起,如果他们的薪水总和超过\\(m\\),

柔光的暖阳◎/ 2021年12月23日 22:35/ 0 赞/ 209 阅读

相关 BZOJ 2200: [Usaco2011 Jan]道路和航线

Description Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到T个城镇 (1 <= T <= 25,000)，编号为1T。这

朴灿烈づ我的快乐病毒、/ 2021年12月16日 12:37/ 0 赞/ 205 阅读

相关 BZOJ 1597: [Usaco2008 Mar]土地购买动态规划 + 斜率优化

Code: include<bits/stdc++.h> define maxn 1000000 define ll long long

秒速五厘米/ 2021年11月16日 05:26/ 0 赞/ 240 阅读

相关 bzoj2753: [SCOI2012]滑雪与时间胶囊

这题真的很容易想到最小生成树。而且题目有特别的性质，高处的连低处的是单向的，但是不会构环（老实讲一开始就是担心这个，但是现在发现好像没啥影响吧），所以其实先把能够访问的点d

水深无声/ 2021年09月29日 16:48/ 0 赞/ 246 阅读