Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
usaco数据全过为什么wa啊#include <stdio.h> long str[40005]={0}; long rank[40005]={0}; long hash[4000005]={0}; long line[40005]={0}; long line2[40005]={0}; long h[40005]={0},height[40005]={0}; long sa[40005]={0}; int main() { long n,k,i,tot=0,tmp=0,l=1,r,mid,s=0,max=0,j; //freopen("3261.in","r",stdin); //freopen("3261.out","w",stdout); scanf("%ld%ld",&n,&k); for(i=1;i<=n;i++) { scanf("%ld",&str[i]); hash[str[i]]=1; } r=n+1; for(i=1,tot=0;i<=2000000;i++) if(hash[i]) hash[i]=++tot; for(i=1;i<=n;i++) rank[i]=hash[str[i]]; for(i=0;i<=n;i++) hash[i]=0; for(i=1;(1<<(i-1))<=n;i++) { for(j=1;j<=n;j++) { rank[j]=rank[j]*(n+1); if(j+(1<<(i-1))<=n) rank[j]+=rank[j+(1<<(i-1))]; hash[rank[j]%(n+1)]++; } for(j=1,tmp=hash[0];j<=n;j++) if(hash[j]) { hash[j]+=tmp; tmp=hash[j]; } for(j=n;j>=1;j--) { line[hash[rank[j]%(n+1)]]=j; hash[rank[j]%(n+1)]--; } for(j=0;j<=n;j++) hash[j]=0; for(j=1;j<=n;j++) hash[rank[line[j]]/(n+1)]++; for(j=1,tmp=0;j<=n;j++) if(hash[j]) { hash[j]+=tmp; tmp=hash[j]; } for(j=n;j>=1;j--) { line2[hash[rank[line[j]]/(n+1)]]=line[j]; hash[rank[line[j]]/(n+1)]--; } for(j=0;j<=n;j++) hash[j]=0; for(j=1,tot=0,tmp=0;j<=n;j++) { if(rank[line2[j]]!=tmp) { tmp=rank[line2[j]]; ++tot; } rank[line2[j]]=tot; } if(tot>=n) break; } for(i=1;i<=n;i++) sa[rank[i]]=i; for(i=1;i<=n;i++) { h[i]=h[i-1]-1>=0?h[i-1]-1:0; if(rank[i]-1) for(j=sa[rank[i]-1];j+h[i]-1<=n&&i+h[i]-1<=n&&str[i+h[i]]==str[j+h[i]];h[i]++); height[rank[i]]=h[i]; } for(;l<r;) { mid=(l+r)/2; for(i=1,s=1,max=0;i<=n;i++) { if(height[i]<mid) { if(s>max) max=s; s=1; } else s++; } if(s>max) max=s; if(max<k) r=mid; else l=mid+1; } printf("%ld\n",r-1); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator