poj3349(Hash表，TLE和AC分析)

传送门：Snowflake Snow Snowflakes

分析：

我们可以自己定义hash函数：

$$\begin{array}{r}H\left(a_1,a_2,...,a_6\right)=\left(\sum _{i=1}^6{a}_i+\prod _{i=1}^6{a}_i\right)modp\\ \left(p选取一个较大的质数\right)\end{array}$$
之后选用合适的数据结构存储数据，并判断雪花是否相同即可

发现用vector无情tle，用数组模拟链表成功ac

TLE版本

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#define ll long long
using namespace std;
const int N = 100006, P = 99991;
int n, a[6], b[6];
struct S {int s[6];};
vector<S> snow[N];//储存每一种有相同hash值的雪花的信息
int H(){
    int s = 0, k = 1;
    for (int i = 0; i < 6; i++) {
        (s += a[i]) %= P;//二式合一 
        k = (ll)k * a[i] % P;
    }
    return (s + k) % P;
}//hash函数 
bool jud() {
    for (int i = 0; i < 6; i++)
    for (int j = 0; j < 6; j++){
        bool v = 1;
        for (int k = 0; k < 6; k++)if ( a[(i+k)%6] != b[(j+k)%6] ) {v = 0;break;}
        if (v) return 1;
        v = 1;
        for (int k = 0; k < 6; k++)if (a[(i+k)%6] != b[(j-k+6)%6]) {v = 0;break;}
        if (v) return 1;
    }
    return 0;
}
bool insert() {
    int h = H();
    for (unsigned int i = 0; i < snow[h].size(); i++) {
        memcpy(b, snow[h][i].s, sizeof(b));
        if (jud()) return 1;
    }
    S s;
    memcpy(s.s, a, sizeof(s.s));
    snow[h].push_back(s);
    return 0;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 6; j++) scanf("%d", &a[j]);
        if (insert()) {
            cout << "Twin snowflakes found." << endl;
            return 0;
        }
    }
    cout << "No two snowflakes are alike." << endl;
    return 0;
}

AC版本

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#define ll long long
using namespace std;
const int N = 100006;
const int P = 99991;
int n,tot,snow[N][6],head[N],nxt[N],a[6];
int H(){
    int s = 0, k = 1;
    for (int i = 0; i < 6; i++) {
        (s += a[i]) %= P;//二式合一 
        k = (ll)k * a[i] % P;
    }
    return (s + k) % P;
}//hash函数 
bool jud(int *b) {
    for (int i = 0; i < 6; i++)
    for (int j = 0; j < 6; j++){
        bool v = 1;
        for (int k = 0; k < 6; k++)if ( a[(i+k)%6] != b[(j+k)%6] ) {v = 0;break;}
        if (v) return 1;
        v = 1;
        for (int k = 0; k < 6; k++)if (a[(i+k)%6] != b[(j-k+6)%6]) {v = 0;break;}
        if (v) return 1;
    }
    return 0;
}
bool insert() {
    int h = H();
    for(int i=head[h];i;i=nxt[i]){
        if(jud(snow[i]))return 1;
    }
    //未找到雪花，执行插入 
    ++tot;
    memcpy(snow[tot],a,sizeof(a));
    nxt[tot]=head[h];
    head[h]=tot;
    return 0;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 6; j++) scanf("%d", &a[j]);
        if (insert()) {
            cout << "Twin snowflakes found." << endl;
            return 0;
        }
    }
    cout << "No two snowflakes are alike." << endl;
    return 0;
}