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

怎么这样的?复杂度O(1000000*log(1000000) )会超时?

Posted by 054100532 at 2008-10-03 14:52:05 on Problem 3690
In Reply To:这题不是后缀数组吗? Posted by:054100532 at 2008-10-03 13:51:29
#include<stdio.h>

//////////////////////////
#include <algorithm>
#include <math.h>
using namespace std;

#define max(a,b) (a>b?a:b)

typedef __int64 ET;
const ET A = 1;
const ET INF = A<<55;
const int M = 1005*1005 +10 ;
const int N = M ;


ET a[N];
int times[N], h[N], smem[3][N];
int *Sa, *Rank;

int d[N][20];
int n;

struct cmp
{
	ET *a;
	cmp(ET *_a):a(_a) {}
	bool operator ()(int x, int y)
	{		return a[x] < a[y];	}
};


void initSuffix( ET *a, int n )
{
	int *temp = smem[2]; 
	int i, k;
	for (i = 0; i < n; i++) Sa[i] = i;
	sort(Sa, Sa+n, cmp(a) );
	memset(Rank, 0, sizeof(int)*n );
	Rank[Sa[0]] = 0;
	for (i = 1; i < n; i++)
	{
		if (a[Sa[i-1]] == a[Sa[i]])
			Rank[Sa[i]] = Rank[Sa[i-1]];
		else 
			Rank[Sa[i]] = i;
	}
	for (k=1;k<n;k*=2)
	{
		for(i=0;i<n;i++) 
			times[Rank[Sa[i]]]=i+1;
        	for(i=n-1;i>=0;i--) 
			if(Sa[i]>=k)
				temp[--times[Rank[Sa[i]-k]]]=Sa[i]-k;  
		for(i=n-k;i<n;i++) temp[--times[Rank[i]]]=i; 
		int *t = Sa;Sa = temp;
		temp = Rank;Rank = t;
		Rank[Sa[0]] = 0;
		for (i = 1; i < n; i++)
		{
			if (temp[Sa[i-1]] == temp[Sa[i]] && temp[Sa[i-1]+k] == temp[Sa[i]+k])
				Rank[Sa[i]] = Rank[Sa[i-1]];
			else Rank[Sa[i]] = i;
		}
	}
}

/////////////////////////

//int q[1005][1005];
//__int64 q[1005];//*1005];

int judge( __int64 f[], int sn, int start )
{
	int i;
	for( i=0; i<sn; i++ )
	{
		if( f[i] > a[start+i] )
		{
			return 1;
		}
		if( f[i] < a[start+i] )
		{
			return -1;
		}
	}
	return 0;
}

__int64 aa[1005][1005];

int main()
{
	int nn,m;
	int r;
	int sn,sm;
	int casenum = 1;
	while( scanf("%d%d%d%d%d", &nn, &m, &r, &sn, &sm ) != EOF && ( nn && m && r && sn && sm ) )
	{
		int i,j;
		int last = 0;
		for( i=0; i<nn; i++ )
		{
			char tab[1005];
			scanf("%s", tab);
			__int64 cur = 0;
			int c = 0;
			int go = 0;
			for( j = m-1; j>=0; j-- )
			{
				__int64 t = 0;
				if( tab[j] == '*' )
					t = 1;
				if( c < sm - 1)
				{
					cur += (t << c);
					c++;
				}
				else
				{
					if( c >= sm || go )
						cur = cur >> 1;
					else
						go = 1;
					cur += (t << c);
					aa[i][j] = cur;
				}
			}
		}
		for( i=0; i<=m-sm; i++ )
			aa[nn][i] = -1;
		for( i=0; i<=m-sm; i++ )
		{
			for( j=0; j<=nn; j++ )
			{
				a[last++] = aa[j][i];
			}
		}
//		last -= step;
		n = last;
		Sa = smem[0], Rank = smem[1];
		a[n+1] = -INF ;		//注意
		initSuffix( a, n );
//		initLCP( n );
		///////////////////////////////
		int ans = 0;
		while( r -- )
		{
			__int64 f[100];
			for( i=0; i<sn; i++ )
			{
				char tab[110];
				scanf("%s", tab);
				int cur = 0;
				int c = 0;
				for( j=sm-1; j>=0; j-- )
				{
					__int64 t = 0;
					if( tab[j] == '*' )
						t = 1;
					cur += ( t << c );
					c ++;
				}
				f[i] = cur;
			}
			int l = 0;
			int r = last-1;
			while( r - l > 1 )
			{
				int mid = ( r + l ) / 2;
				int flag = judge(f, sn, Sa[mid] );
				if( flag <= 0 )
					r = mid;
				else
					l = mid;
			}
			int low = -1;
			if( judge(f, sn, Sa[r]) == 0 )
				low = r;
			if( judge(f, sn, Sa[l]) == 0 )
				low = l;
			if( low == -1 )
				continue;
			l = 0;
			r = last - 1;
			while( r - l > 1 )
			{
				int mid = ( r + l ) / 2;
				int flag = judge(f, sn, Sa[mid] );
				if( flag < 0 )
					r = mid;
				else
					l = mid;
			}
			int high;
			if( judge(f, sn, Sa[l]) == 0 )
				high = l;
			if( judge(f, sn, Sa[r]) == 0 )
				high = r;
			ans += high - low + 1;
		}
		printf("Case %d: %d\n", casenum++, ans);
	}
	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