Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

usaco数据全过为什么wa啊

Posted by zw7840 at 2010-04-16 11:36:30 on Problem 3261
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator