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 |
怎么这样的?复杂度O(1000000*log(1000000) )会超时?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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator