NYOJ 138 找球号(二）

 1 #include<stdio.h>
 2 #include<memory.h>
 3 #define N 1000010
 4 #define MOD 110023
 5 int ind,key[N],next[N],order[N];//key[i]保存第i个小球的编号，
 6                         //next[]保存当出现冲突时同一余数对应的多个编号的值 
 7                         //order[i]保存余数为i时对应的球的序号，进而找到其编号 
 8 void add(int n)
 9 {
10     int remainder;
11     remainder=n%MOD;
12     key[ind]=n;            
13     next[ind]=order[remainder]; 
14     order[remainder]=ind;
15     ind++;
16 }
17 int main()
18 {
19     int i,j,n,m,number,tmp;
20     char cmd[6];
21     memset(order,-1,sizeof(order));
22     scanf("%d",&n);
23     while(n--){
24         scanf("%s%d",cmd,&m);
25         if(*cmd=='A'){
26             for(i=0;i<m;i++){
27                 scanf("%d",&number);
28                 add(number);
29             }
30         }else{
31             for(i=0;i<m;i++){
32                 scanf("%d",&number);
33                 tmp=number%MOD;
34                 for(j=order[tmp];j!=-1;j=next[j])//j=1时说明哈希值为tmp的球都以找完 
35                     if(key[j]==number)
36                         break;
37                 puts(j+1?"YES":"NO");
38             }
39         }
40     }
41     return 0;
42 }

以前只知道哈希算法，但没有认真练习过，今天练习了一下，感觉哈希查找效率很高！

贴上最优代码：

 1  
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 unsigned int a[3125010] = {0} ;
 8 
 9 int main()
10 {
11     int n , m , x ;
12     int i ;
13     char op[10] ;
14     scanf("%d", &n ) ;
15     while( n-- > 0 )
16     {
17         fflush( stdin ) ;
18         memset( op , 0 , sizeof(op) );
19         scanf("%s", op ) ;
20         if( strcmp( op , "ADD" ) == 0 )
21         {
22             scanf("%d", &m ) ;
23             for( i = 0 ; i < m ; i++ )
24             {
25                 scanf("%d", &x ) ;
26 
27                 a[x/32] |= 1 << ( x % 32 ) ;
28             }
29         }
30         else
31         {
32             scanf("%d", &m ) ;
33             for( i = 0 ; i < m ; i++ )
34             {
35                 scanf("%d", &x ) ;
36 
37                 if( ( a[x/32] & ( 1 << ( x % 32 ))) )
38                 {
39                     printf("YES\n") ;
40                 }
41                 else
42                     printf("NO\n") ;
43             }
44         }
45     }
46     return 0 ;
47 }