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(n*n)的,我用"I a 1"2000次,再"Q 1"2000次在本机上300毫秒左右,为什么还是超时?#include "stdio.h" #include "string.h" #include <time.h> char str[1000010],node[5000]; int b[5000],e[5000],max,v[5000],l[5000],r[5000],root,flag[5000],next; void insert(char ch ,int k, int ps){ if( flag[k] == 1 ){ flag[k] = 0,v[k] = ps - 1; next ++ ; node[k] = ch; l[k] = next; b[next] = b[k]; e[next] = b[k] + ps - 2; flag[next] = 1; next ++; r[k] = next; b[next] = b[k] + ps - 1; e[next] = e[k]; flag[next] = 1; }else{ if( ps <= v[k] + 1 ){ v[k] ++ ; insert( ch, l[k] , ps ); } else{ ps -= v[k] ; ps-- ; insert( ch, r[k], ps ); } } } void search( int k , int ps ){ if( flag[k] == 1 ) { printf("%c\n",str[b[k] + ps -1]); return ; }else{ if( v[k] + 1 == ps ) { printf( "%c\n", node[k] ); return ; }else{ if( ps <= v[k] ) search( l[k] , ps ); else{ ps -= v[k]; ps --; search( r[k] , ps ); } } } } int main(void){ // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int k, cs; char ch; // clock_t start, finish; // start = clock(); k = 0 ; while( 1 ){ scanf("%c",str+k); if(str[k] == '\n' ) break; k++; } max = k,next = 0; // start = clock(); b[0] = 0 , e[0] = max - 1,flag[0] = 1; scanf( "%d", &cs ); while ( cs -- ){ scanf(" %c", &ch); if( ch == 'I'){ scanf(" %c %d", &ch, &k); if( k > max ) k = max + 1; insert( ch , 0, k ); max ++ ; }else{ scanf( "%d", &k); search( 0, k ); } } // finish = clock(); // printf("time = %d\n",finish - start); return 0 ; } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator