注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 3012  

2013-02-05 13:26:47|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

first

考试的时候我做出来的只有第二题……首先这道题一眼看上去就知道要用丢进一个trie里面。

然后,如果串A<串B,那么就一定是a[LCP(A,B)+1]<b[LCP(A,B)+1],这就相当于有了约束条件。将约束条件用若干条有向边代替,题目就成了图论题,判断有木有环。

有木有环应该有正常做法吧?比如听说拓扑排序可做?还听说DFS的时候乱搞一下就可以了……

反正我由于不会又由于yy能力不够,所以就傻叉的写了个诡异般差分约束……

最后在bzoj上用时倒数第一
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXM 300010
#define MAXN 30010
#define now tree[root]
#define N 30
using namespace std;
struct trie
{
    int son[30],mark,father;
    char p;
}tree[MAXM];
char a[MAXM],stack[MAXM];
int n,total,pos[MAXN],ans[MAXN],s,top,dis[MAXN],update[MAXN],queue[40];
bool use[MAXN];
int tot,num[710],next[710],start[30];
void make(int a,int b){  tot++,num[tot]=b,next[tot]=start[a],start[a]=tot;  }
void Insert(char a[],int k)
{
    int root=0;
    for(int i=0;a[i];i++)
    {
        if(now.son[a[i]-'a']==0)  now.son[a[i]-'a']=++total,tree[total].father=root,tree[total].p=a[i];
        root=now.son[a[i]-'a'];
    }
    now.mark=k,pos[k]=root;
}
void read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",a);
        Insert(a,i);
    }
}
void makegraph()
{
    memset(start,0,sizeof(start));
    tot=0;
    int root=0;
    for(int i=top;i>=1;i--)
    {
        int k=stack[i]-'a';
        for(int j=0;j<26;j++)
            if(j!=k&&now.son[j])
                make(k,j);
        root=now.son[k];
    }
}
bool check(int k)
{
    for(int root=pos[k];root;root=now.father)
        if(root!=pos[k]&&now.mark)
            return false;
    memset(use,false,sizeof(use));
    memset(update,0,sizeof(update));
    int front=0,rear=1;
    queue[rear]=26;
    for(int i=0;i<26;i++)
        make(26,i),dis[i]=-1<<30;
    int p;
    while(front!=rear)
    {
        front=front%N+1,p=queue[front],use[p]=false;
        for(int i=start[p];i;i=next[i])
            if(dis[num[i]]<dis[p]+1)
            {
                dis[num[i]]=dis[p]+1,update[num[i]]++;
                if(update[num[i]]>26)  return false;
                if(!use[num[i]])  rear=rear%N+1,queue[rear]=num[i],use[num[i]]=true;
            }
    }
    return true;
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        top=0;
        for(int root=pos[i];root;root=now.father)
            stack[++top]=now.p;
        makegraph();
        if(check(i))  ans[++s]=i;
    }
}
void print()
{
    printf("%d\n",s);
    for(int i=1;i<=s;i++)
    {
        top=0;
        for(int root=pos[ans[i]];root;root=now.father)
            stack[++top]=now.p;
        for(int i=top;i>=1;i--)
            printf("%c",stack[i]);
        printf("\n");
    }
}
int main()
{
    read();
    solve();
    print();
    return 0;
}
  评论这张
 
阅读(165)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017