加载中…
个人资料
lovedream
lovedream
  • 博客等级:
  • 博客积分:0
  • 博客访问:59,866
  • 关注人气:40
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

HDU4125——福州赛E题

(2011-11-28 13:19:37)
标签:

杂谈

分类: ACM/ICPC解题报告

题意很清晰,模拟一棵树,求遍历得到的序列。然后用KMP求出现次数。

有2个点需要注意:

1.由于点有60W个,遍历的时候不能递归,否则可能栈溢出。

2.点太多,而树可能会退化,这里如果模拟插入过程会TLE。

对于第一个问题,只需要改用非递归就可以了;第二个问题,则可以用一种O(log(N))插入的方法:新节点的父亲一定是已有节点中小于它的节点中最大的,或是大于它的节点中最小的,证明自己想吧。

有这个结论,就很容易想到用线段树来求出小于它的最大的节点,和大于它的最小的节点(当前节点是最大节点或最小的节点另外处理)。取可以插入那个。

KMP部分没有任何trick,本题完美解决了。

#include<stdio.h>
#include<string.h>

char s[2000000],ss[10000];
int sta[700000],top,root,ch[700000][2],cnt;
int zhu[700000],C[700000];

inline void f()
{
    zhu[root]=0;cnt=0;
    sta[0]=root,top=1;

    if(!ch[root][0]&&!ch[root][1])
    {
        s[0]=root%2+'0';
        return;
    }
    int t=root;
    while(t-root||((zhu[t]==1&&ch[t][1])||zhu[t]==0))
    {
        s[cnt++]=t%2+'0';
        if(top<0)
            return;
        if(zhu[t]==0)
        {
            if(ch[t][0])
            {
                zhu[t]=1;
                t=ch[t][0];
                zhu[t]=0;
                sta[top++]=t;
            }
            else if(ch[t][1])
            {
                zhu[t]=2;
                t=ch[t][1];
                zhu[t]=0;
                sta[top++]=t;
            }
            else if(t==root)
                return ;
            else
                zhu[t]=2,t=sta[--top-1];
        }
        else if(zhu[t]==1)
        {
            if(ch[t][1])
            {
                zhu[t]=2;
                t=ch[t][1];
                zhu[t]=0;
                sta[top++]=t;
            }
            else if(t==root)
                return ;
            else
                t=sta[--top-1];
        }
        else if(t==root)
            return ;
        else
            t=sta[--top-1];
    }
    s[cnt++]=root%2+'0';
}

int P[10000];

inline void scan(int &u)
{
    char c;
    while(c=getchar(),c<'0'||c>'9');
    u=c-'0';
    while(c=getchar(),c<='9'&&c>='0')
        u=u*10+c-'0';
}
int ff(int l)
{
    int i,j,ans=0;
    P[0]=-1;

    for(i=1,j=-1;i<l;i++)
    {
        while(j+1&&ss[j+1]-ss[i])
            j=P[j];
        if(ss[j+1]==ss[i])
            j++;
        P[i]=j;
    }

    for(i=0,j=-1;i<cnt;i++)
    {
        while(j+1&&ss[j+1]-s[i])
            j=P[j];
        if(ss[j+1]==s[i])
            j++;
        if(j==l-1)
            ans++;
    }
    return ans;
}

int N,Min,Max;
int cal(int n)
{
    int ans=0;
    while(n>=1)
        ans+=C[n],n-=n&(-n);
    return ans;
}
void update(int n)
{
    while(n<=N)
        C[n]++,n+=n&(-n);
}
void insert(int n)
{
    update(n);
    int t=cal(n);
   
    if(!root)
    {
        root=n;
        Min=Max=n;
        return;
    }
    if(n>Max)
    {
        ch[Max][1]=n;
        Max=n;
        return;
    }
    if(n<Min)
    {
        ch[Min][0]=n;
        Min=n;
        return;
    }
    int l=1,r=n-1,mid;
    Min=Min<n?Min:n;
    Max=Max>n?Max:n;

    while(l<r)
    {
        mid=(l+r)>>1;
        if(cal(mid)==t-1)
            r=mid;
        else
            l=mid+1;
    }
    l=r;
    if(!ch[l][1])
    {
        ch[l][1]=n;
        return;
    }
    l=n+1,r=N;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(cal(mid)-t)
            r=mid;
        else
            l=mid+1;
    }
    ch[r][0]=n;
}
int main()
{
    int t,n,i,j;
    scanf("%d",&t);

    for(int ii=1;ii<=t;ii++)
    {
        memset(ch,0,sizeof(ch));
        memset(C,0,sizeof(C));
        Min=1000000,Max=0;
        root=0;

        scanf("%d",&n);N=n;
        for(i=1;i<=n;i++)
            scanf("%d",&j),insert(j);
        f();
        scanf("%s",ss);

        printf("Case #%d: %d\n",ii,ff(strlen(ss)));
    }
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有