absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] [1] UOJ 212
[这个Blog需要恢复] 568B

[破碎的状态] [1] Hdu 4691(Failed)

absi2011 posted @ Jul 23, 2016 10:34:49 PM in 刷题记录 with tags 后缀数组 HDU 小高考 , 822 阅读

其实我觉得代码是对的..

反正..

后缀数组写对了..

后面st表..

不管了..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[100005];
struct node
{
    int x;
    int y;
    int id;
    friend bool operator < (const node &a,const node &b)
    {
        return a.y<b.y;
    }
};
node b[100005];
int c[100005];
int m;
void suffix_sort(int x)
{
    if (x>m) return;
    int i;
    c[b[0].id]=0;
    for (i=1;i<m;i++)
    {
        if ((b[i].x!=b[i-1].x)||(b[i].y!=b[i-1].y))
        {
            c[b[i].id]=c[b[i-1].id]+1;
        }
        else
        {
            c[b[i].id]=c[b[i-1].id];
        }
    }
    for (i=0;i<m;i++)
    {
        b[i].x=c[b[i].id];
        if (b[i].id+x<m)
        {
            b[i].y=c[b[i].id+x];
        }
        else
        {
            b[i].y=-1;
        }
    }
    int last=0;
    for (i=1;i<m;i++)
    {
        if (b[i-1].x!=b[i].x)
        {
            sort(b+last,b+i);
            last=i;
        }
    }
    sort(b+last,b+m);
    suffix_sort(x*2);
}
int lcp[100005];
int st[100005][20];
int d[1<<20];
int get_lcp(int x,int y)
{
    if (x>y) swap(x,y);
    if (x==y) return 1000000;
    int k=d[y-x];
    return min(st[x][k],st[y-(1<<k)][k]);
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    int i;
    for (i=0;i<19;i++)
    {
        int j;
        for (j=(1<<i);j<(1<<(i+1));j++)
        {
            d[j]=i;
        }
    }
    for (;;)
    {
        if (scanf("%s",a)==-1) break;
        int n;
        scanf("%d",&n);
        m=strlen(a);
        int i;
        for (i=0;i<m;i++)
        {
            b[i].id=i;
            b[i].x=0;
            b[i].y=a[i];
        }
        sort(b,b+m);
        suffix_sort(1);
        int last=-1;
        for (i=0;i<m;i++)
        {
            if (b[i].x==m-1) continue;
            if ((i==0)||(lcp[i-1]==0))
            {
                last=0;
            }
            else
            {
                last=lcp[i-1]-1;
            }
            lcp[i]=0;
            if (c[i]==0) continue;
            for (;;)
            {
                if (a[i+last]==a[last+b[c[i]-1].id])
                {
                    last++;
                }
                else
                {
                    break;
                }
            }
            lcp[i]=last;
        }
        for (i=m-1;i>=0;i--)
        {
            int j;
            if (i==m-1)
            {
                st[i][0]=0;
            }
            else
            {
                st[i][0]=lcp[b[i+1].id];
            }
            for (j=1;j<20;j++)
            {
                if (((1<<j)+i)>m) continue;
                st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
            }
        }
        if (n==0)
        {
            cout<<"0 0\n";
            continue;
        }
        int lastx,lasty;
        scanf("%d%d",&lastx,&lasty);
        long long sum1=n,sum2=n;
        sum1+=lasty-lastx;
        sum2+=lasty-lastx+2;
        for (i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            sum1+=y-x;
            int k=get_lcp(c[x],c[lastx]);
            k=min(k,lasty-lastx);
            k=min(k,y-x);
            lastx=x;
            lasty=y;
            sum2+=(y-x-k);
            sum2++;
            sum2++;
            if (k>=10) sum2++;
            if (k>=100) sum2++;
            if (k>=1000) sum2++;
            if (k>=10000) sum2++;
            if (k>=100000) sum2++;
        }
        cout<<sum1<<" "<<sum2<<'\n';
    }
    return 0;
}
NCERT Hindi Sample P 说:
Sep 26, 2022 01:33:12 AM

Hindi is a very important language subject to know in India and we are here to tell you why. In this article, NCERT Hindi Sample Paper Class 10 we will be discussing the importance of learning Hindi. From children to adults, everyone takes up a second language at some point in their life. With the ongoing situation, you could have not found a better time to learn a new language.Hindi is a very important language subject to know in India and we are here to tell you why. In this article


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter