首页 > 代码库 > HDU 4333 [SAM WRONG！！！]

HDU 4333 [SAM WRONG！！！]

2024-09-04 04:00:26   218人阅读

题意：给一个数字，每一次把它的最后一位拿到最前面，一直那样下去，分别求形成的数字小于，等于和大于原来数的个数。

SAM上就是走n步

相等好好做啊，但是大于小于不好做啊，用类似弦论的思想也不能处理出怎样才是正好n步走到

用LCP就要加一个log呜呜

只能去写扩展KMP了

http://blog.csdn.net/acdreamers/article/details/8313828

http://wenku.baidu.com/view/64ac5384b9d528ea81c779ed.html

http://acm.hdu.edu.cn/showproblem.php?pid=4333

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <map>using namespace std;const int N=2e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();}    return x*f;}int n,ri[N],d[N];char s[N];struct State{    int ch[10],par,val;}t[N];int sz=1,root=1,last=1;void extend(int c){    int p=last,np=++sz;    t[np].val=t[p].val+1;ri[np]=1;printf("np %d   %d\n",np,c);    for(;p&&!t[p].ch[c];p=t[p].par) t[p].ch[c]=np;    if(!p) t[np].par=root;    else{        int q=t[p].ch[c];        if(t[q].val==t[p].val+1) t[np].par=q;        else{            int nq=++sz;            t[nq]=t[q];t[nq].val=t[p].val+1;            t[q].par=t[np].par=nq;            for(;p&&t[p].ch[c]==q;p=t[p].par) t[p].ch[c]=nq;        }    }    last=np;}void ini(){sz=root=last=1;memset(t,0,sizeof(t));}int c[N],a[N];void RadixSort(){    for(int i=0;i<=sz;i++) c[i]=0;    for(int i=1;i<=sz;i++) c[t[i].val]++;    for(int i=1;i<=sz;i++) c[i]+=c[i-1];    for(int i=1;i<=sz;i++) a[c[t[i].val]--]=i; }int L,E,G;void Count(){    int u=root;    for(int i=1;i<=n;i++){        int c=s[i]-‘0‘;        for(int j=0;j<c;j++) L+=d[t[u].ch[j]];        for(int j=c+1;j<10;j++) G+=d[t[u].ch[j]];        u=t[u].ch[c];    }    E=ri[u];}void dp(){    RadixSort();    for(int i=sz;i>=1;i--){        int u=a[i];        ri[t[u].par]+=ri[u];        //printf("hi %d %d  %d %d\n",u,ri[u],t[u].val,t[t[u].par].val);    }    for(int i=sz;i>=1;i--){        int u=a[i];        ri[u]= t[u].val>=n&&t[t[u].par].val<n?ri[u]:0;        d[u]=ri[u];        printf("hi %d %d  %d %d\n",u,ri[u],t[u].val,t[t[u].par].val);        for(int j=0;j<10;j++) d[u]+=d[t[u].ch[j]];        printf("d %d %d\n",u,d[u]);    }    L=E=G=0;    Count();}int main(){    freopen("in","r",stdin);    int T=read(),cas=0;    while(T--){        scanf("%s",s+1);        n=strlen(s+1);        ini();        for(int i=1;i<=n;i++) extend(s[i]-‘0‘);        for(int i=1;i<n;i++) extend(s[i]-‘0‘);        dp();        printf("Case %d: %d %d %d\n",++cas,L,E,G);    }}

 

HDU 4333 [SAM WRONG！！！]


联系
我们