這道題在a,b,c,d未知的情況下，是有200萬(wàn)的可能的結(jié)果，但是當(dāng)a,b,c,d給定則變成2萬(wàn)了，當(dāng)然這2萬(wàn)是不連續(xù)的，那么為了節(jié)省空間，可以用線性探測(cè)，數(shù)組要開(kāi)的比2萬(wàn)大。
無(wú)線性探測(cè)代碼
1 #include<cstdio>
2 #include<cstring>
3 int hash[2000001] ;
4 int hash_fun(int num){
5 return num + 1000000;
6 }
7 int main(){
8 int a,b,c,d;
9 int sq[101] ={0};
10 for(int i = 1; i <= 100; i++)
11 sq[i] = i*i;
12 while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){
13 if((a<0 && b<0 && c<0 && d<0) ||
14 (a>0 && b>0 && c>0 && d>0) ){
15 printf("0\n");
16 continue;
17 }
18 memset(hash,0,sizeof(hash));
19 for(int i = 1; i <= 100; i++)
20 for(int j = 1; j <= 100; j++)
21 hash[hash_fun(-sq[i]*a - sq[j]*b)]++;
22 int ans = 0;
23 for(int i = 1; i <= 100; i++)
24 for(int j = 1; j <= 100; j++)
25 ans += hash[hash_fun(sq[i]*c + sq[j]*d)];
26 printf("%d\n",ans*16);
27 }
28 }
29
線性探測(cè)：h(k)%S被占用，則用(h(k)+i)%S,直到找到?jīng)]有被占用的，因?yàn)槭褂镁€性探測(cè)就使h(k)存在不確定性，故在h(k)處必須保存k的值，即該數(shù)組是一結(jié)構(gòu)體的數(shù)組。
先說(shuō)一下一段錯(cuò)誤的代碼
1 #include<cstdio>
2 #include<cstring>
3 const int maxn = 21000;
4 struct hashn{
5 int k;
6 int c;
7 };
8 hashn hash[100000] ;
9 int hash_fun(int num){
10 int t = num % maxn;
11 if(t < 0)t += maxn;
12 while(hash[t].k != 0 ){
13 if(hash[t].k == num)return t;
14 t = (t+1)%maxn;
15 if(t<0) t+= maxn;
16 }
17 hash[t].k = num;
18 return t;
19 }
20 int hash_fun2(int num){
21 int t = num % maxn;
22 if(t < 0)t += maxn;
23 while(hash[t].k != 0 ){
24 if(hash[t].k == num)return t;
25 t = (t+1)%maxn;
26 if(t<0) t+ maxn;
27 }
28 return t;
29 }
30 int main(){
31 int a,b,c,d;
32 int sq[101] ={0};
33 for(int i = 1; i <= 100; i++)
34 sq[i] = i*i;
35 while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){
36 if((a<0 && b<0 && c<0 && d<0) ||
37 (a>0 && b>0 && c>0 && d>0) ){
38 printf("0\n");
39 continue;
40 }
41 for(int i = 1; i <= 100000;i++)
42 hash[i].c = hash[i].k = 0;
43 for(int i = 1; i <= 100; i++)
44 for(int j = 1; j <= 100; j++)
45 hash[hash_fun(-sq[i]*a - sq[j]*b)].c++;
46 int ans = 0;
47 for(int i = 1; i <= 100; i++)
48 for(int j = 1; j <= 100; j++){
49 int temp = hash_fun(sq[i]*c + sq[j]*d);
50 ans += hash[temp].c;
51 }
52 printf("%d\n",ans*16);
53 }
54 }
這段代碼有一個(gè)比較明顯的錯(cuò)誤，還有一個(gè)不明顯但是很容易錯(cuò)的地方。
maxn定為21000過(guò)小了，即使數(shù)組足夠大，但是這也只用到了21000。
另一個(gè)就是：
初始化hash表的時(shí)候的值在所有可能的取值中出現(xiàn)了！（k初始化為0）
改正后的代碼：
1 #include<cstdio>
2 #include<cstring>
3 const int maxn = 51000;
4 struct hashn{
5 int k;
6 int c;
7 };
8 hashn hash[100000] ;
9 int hash_fun(int num){
10 int t = num % maxn;
11 if(t < 0)t += maxn;
12 while(hash[t].k != -1){
13 if(hash[t].k == num)return t;
14 t = (t+1)%maxn;
15 }
16 hash[t].k = num;
17 return t;
18 }
19 int main(){
20 int a,b,c,d;
21 int sq[101] ={0};
22 for(int i = 1; i <= 100; i++)
23 sq[i] = i*i;
24 while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){
25 if((a<0 && b<0 && c<0 && d<0) ||
26 (a>0 && b>0 && c>0 && d>0) ){
27 printf("0\n");
28 continue;
29 }
30 for(int i = 0; i <= 100000;i++){
31 hash[i].c = 0;
32 hash[i].k = -1;
33 }
34 for(int i = 1; i <= 100; i++)
35 for(int j = 1; j <= 100; j++)
36 hash[hash_fun(-sq[i]*a - sq[j]*b)].c++;
37 int ans = 0;
38 for(int i = 1; i <= 100; i++)
39 for(int j = 1; j <= 100; j++){
40 int temp = hash_fun(sq[i]*c + sq[j]*d);
41 ans += hash[temp].c;
42 }
43 printf("%d\n",ans*16);
44 }
45 }