2011-07-21 22:55:11Morris
a064. SPOJ 4580.ABCDEF (Hash 版本)
之前的做法, 是用 窮舉, 有一定的機率是 O(N^4)
這次用 Hash 平攤下去是 O(N^3)
a*b+c = (e+f)*d
用 Hash 把所有 a*b+c 的量都記錄下來 (包含次數)
之後再窮舉 (e+f)*d 看有沒有存在 Hash
curr = HASH[(v%Mod + Mod)%Mod]; //快
curr = HASH[(long long)v*v%Mod]; //慢
速度差三倍, 慘痛教訓, 記錄
Mod 值 可隨機調整, 越小基本上速度越慢, 越大不見得越好
/**********************************************************************************/
/* Problem: a064 "SPOJ 4580.ABCDEF" from SPOJ 4580 */
/* Language: C */
/* Result: AC (92ms, 3991KB) on ZeroJudge */
/* Author: morris1028 at 2011-07-21 22:49:36 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define Mod 500000
struct list {
int tag, t;
struct list *next;
}*HASH[Mod], *curr, *prev, *temp;
void InsHash(int n) {
int m = (n%Mod + Mod)%Mod;
if(HASH[m] == NULL) {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->next = NULL, curr->t = 1;
HASH[m] = curr;return;
}
temp = HASH[m], prev = NULL;
while(temp->tag <= n) {
if(temp->tag == n) {temp->t++;return;}
if(temp->next != NULL)
prev = temp, temp = temp->next;
else {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->next = NULL, curr->t = 1;
temp->next = curr; return;
}
}
if(prev != NULL) {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->t = 1;
prev->next = curr, curr->next = temp;
}
else {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->t = 1;
HASH[m] = curr, curr->next = temp;
}
return;
}
void FreeAll() {
int a;
for(a = 0; a < Mod; a++) {
curr = HASH[a], prev = NULL;
while(curr != NULL) {
prev = curr, curr = curr->next;
free(prev);
}
HASH[a] = NULL;
}
}
int Find(int v) {
curr = HASH[(v%Mod + Mod)%Mod];
while(curr != NULL) {
if(curr->tag == v) return curr->t;
curr = curr->next;
}
return 0;
}
main() {
int n, a, b, c, A[100];
while(scanf("%d", &n) == 1) {
for(a = 0; a < n; a++)
scanf("%d", &A[a]);
FreeAll();
for(a = 0; a < n; a++)
for(b = 0; b < n; b++)
for(c = 0; c < n; c++) {
InsHash(A[a]*A[b]+A[c]);
}
long long Ans = 0;
for(a = 0; a < n; a++) {
if(A[a] != 0)
for(b = 0; b < n; b++)
for(c = 0; c < n; c++) {
Ans += Find(A[a]*(A[b]+A[c]));
}
}
printf("%lld\n", Ans);
}
return 0;
}
這次用 Hash 平攤下去是 O(N^3)
a*b+c = (e+f)*d
用 Hash 把所有 a*b+c 的量都記錄下來 (包含次數)
之後再窮舉 (e+f)*d 看有沒有存在 Hash
curr = HASH[(v%Mod + Mod)%Mod]; //快
curr = HASH[(long long)v*v%Mod]; //慢
速度差三倍, 慘痛教訓, 記錄
Mod 值 可隨機調整, 越小基本上速度越慢, 越大不見得越好
/**********************************************************************************/
/* Problem: a064 "SPOJ 4580.ABCDEF" from SPOJ 4580 */
/* Language: C */
/* Result: AC (92ms, 3991KB) on ZeroJudge */
/* Author: morris1028 at 2011-07-21 22:49:36 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define Mod 500000
struct list {
int tag, t;
struct list *next;
}*HASH[Mod], *curr, *prev, *temp;
void InsHash(int n) {
int m = (n%Mod + Mod)%Mod;
if(HASH[m] == NULL) {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->next = NULL, curr->t = 1;
HASH[m] = curr;return;
}
temp = HASH[m], prev = NULL;
while(temp->tag <= n) {
if(temp->tag == n) {temp->t++;return;}
if(temp->next != NULL)
prev = temp, temp = temp->next;
else {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->next = NULL, curr->t = 1;
temp->next = curr; return;
}
}
if(prev != NULL) {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->t = 1;
prev->next = curr, curr->next = temp;
}
else {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->t = 1;
HASH[m] = curr, curr->next = temp;
}
return;
}
void FreeAll() {
int a;
for(a = 0; a < Mod; a++) {
curr = HASH[a], prev = NULL;
while(curr != NULL) {
prev = curr, curr = curr->next;
free(prev);
}
HASH[a] = NULL;
}
}
int Find(int v) {
curr = HASH[(v%Mod + Mod)%Mod];
while(curr != NULL) {
if(curr->tag == v) return curr->t;
curr = curr->next;
}
return 0;
}
main() {
int n, a, b, c, A[100];
while(scanf("%d", &n) == 1) {
for(a = 0; a < n; a++)
scanf("%d", &A[a]);
FreeAll();
for(a = 0; a < n; a++)
for(b = 0; b < n; b++)
for(c = 0; c < n; c++) {
InsHash(A[a]*A[b]+A[c]);
}
long long Ans = 0;
for(a = 0; a < n; a++) {
if(A[a] != 0)
for(b = 0; b < n; b++)
for(c = 0; c < n; c++) {
Ans += Find(A[a]*(A[b]+A[c]));
}
}
printf("%lld\n", Ans);
}
return 0;
}