Skip to content

11224: 【原1224】hash

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1224

Description

现在给出A,B,C,D四个集合，每个集合中元素的个数n都是相同的，现在从每个集合中任取出一个数，记为a,b,c,d,现在要求统计有多少组不同的(a,b,c,d)使得a+b+c+d=0。

注意请写散列表类。

Input Format

第一行为各集合中元素的个数n;

第二行到第n+1行，每行有4个数字，依次为A,B,C,D中的一个元素。

Output Format

一行，为不同的(a,b,c,d)使得a+b+c+d=0的组数。

Sample Input

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

Sample Output

5

Limits

a,b,c,d的绝对值小于1000000，n小于500

Tips

将式子变形为(a+b)=-(c+d),可以将A,B两集合中元素相加得到n^2个和的集合E,散列存储后,对C,D两集合中元素任意取和,查找和在E中出现的次数，累加即为解。

BugenZhao's solution 

//
// Created by BugenZhao on 2019/5/29.
//

//
// Created by BugenZhao on 2019/5/29.
//

#ifndef SBL_BSEPARATECHAININGHASHST_H
#define SBL_BSEPARATECHAININGHASHST_H


template<typename Key, typename Value, typename Hasher>
class BSeparateChainingHashST {
    static constexpr int INIT_CAPACITY = 4;

    class Pair {
    public:
        Key key;
        Value value;
    };

    class Node {
    public:
        Pair pair;
        Node *next;

        Node(const Pair &pair, Node *next = nullptr) : pair(pair), next(next) {}

        Node() : next(nullptr) {}
    };

    int n;
    int m;
    Hasher hasher;
    Node **st;

private:
    int hash(const Key &key) {
return (hasher(key) & 0x7fffffff) % m;
    }

public:
    BSeparateChainingHashST() : BSeparateChainingHashST(INIT_CAPACITY) {}

    BSeparateChainingHashST(int m) : m(m) {
        n = 0;
        st = new Node *[m]{};
    }

    virtual ~BSeparateChainingHashST() {
        for (int i = 0; i < m; ++i) {
            Node *p = st[i];
            Node *q;
            while (p) {
                q = p->next;
                delete p;
                p = q;
            }
        }
        delete[] st;
    }

    int size() {
        return n;
    }

    bool isEmpty() {
        return size() == 0;
    }

    bool contains(const Key &key) {
        return get(key) != nullptr;
    }

    Pair *get(const Key &key) {
        int i = hash(key);
        Node *p = st[i];
        while (p) {
            if (p->pair.key == key) return &(p->pair);
            p = p->next;
        }
        return nullptr;
    }

    void put(const Key &key, const Value &val) {
//        if (n >= 10 * m) resize(2 * m);

        int i = hash(key);
        Node *p = st[i];
        while (p) {
            if (p->pair.key == key) {
                p->pair.value = val;
                return;
            }
            p = p->next;
        }
        ++n;
        st[i] = new Node(Pair{key, val}, st[i]);
    }

    void increment(const Key &key) {
        int i = hash(key);
        Node *p = st[i];
        while (p) {
            if (p->pair.key == key) {
                ++p->pair.value;
                return;
            }
            p = p->next;
        }
        ++n;
        st[i] = new Node(Pair{key, 1}, st[i]);
    }

    void remove(const Key &key) {
        int i = hash(key);
        Node *p = st[i];

        if (st[i] == nullptr) return;

        if (st[i]->pair.key == key) {
            st[i] = st[i]->next;
            delete p;
            --n;
        } else {
            while (p->next) {
                if (p->next->pair.key == key) {
                    auto q = p->next;
                    p->next = q->next;
                    delete q;
                    --n;
                    break;
                }
                p = p->next;
            }
        }
    }

};

#endif //SBL_BSEPARATECHAININGHASHST_H


#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;

struct hasher {
    inline int operator()(int i) {
        return i + 2000000;
    }
};

int main() {
    int n;
    scanf("%d", &n);
    auto a = new int[n];
    auto b = new int[n];
    auto c = new int[n];
    auto d = new int[n];
    for (int i = 0; i < n; ++i) {
        scanf("%d%d%d%d", a + i, b + i, c + i, d + i);
    }
    BSeparateChainingHashST<int, int, hasher> st(4000001);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            st.increment(a[i] + b[j]);
        }
    }

    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            auto p = st.get(-c[i] - d[j]);
            if (p) ans += p->value;
        }
    }

    printf("%ld", ans);
    return 0;
}

ligongzzz's solution 

#include "iostream"
#include "cstring"
using namespace std;

constexpr int mod = 1000009;

class type {
public:
    int key = -99999999;
    int val = 0;
};

int val_data[509][4] = { 0 };
type hash_map[mod];

int get_pos(int key) {
    int ans = (key + 2000009) % mod;
    for (; hash_map[ans].key != key; ans = (ans + 1) % mod) {
        if (hash_map[ans].key <= -99999999) {
            hash_map[ans].key = key;
            break;
        }
    }
    return ans;
}

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 4; ++j)
            scanf("%d", &val_data[i][j]);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ++hash_map[get_pos(val_data[i][0] + val_data[j][1])].val;
        }
    }

    int ans = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ans += hash_map[get_pos(-val_data[i][2] - val_data[j][3])].val;
        }
    }

    cout << ans;

    return 0;
}

skyzh's solution

#include <iostream>
#include <cstring>

using namespace std;

unsigned alex_hash(long long i) {
    return i;
}

bool equal(long long a, long long b) { return a == b; }

template<typename K, typename V>
struct HashMap {
    struct Pair {
        bool used;
        K key;
        V value;
    } *data;
    static const unsigned cap = 1048576;

    HashMap() {
        data = new Pair[cap];
        memset(data, 0, sizeof(Pair) * cap);
    }

    V &visit(const K key) {
        unsigned pos = alex_hash(key) % cap;
        while (data[pos].used) {
            if (equal(key, data[pos].key)) {
                break;
            }
            ++pos;
            if (pos >= cap) pos = 0;
        }
        if (!data[pos].used) {
            data[pos].used = true;
            data[pos].key = key;
        }
        return data[pos].value;
    }
};

HashMap<long long, int> hash_map;

const int MAX_SET = 500;

long long A[MAX_SET], B[MAX_SET], C[MAX_SET], D[MAX_SET];

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ++hash_map.visit(A[i] + B[j]);
        }
    }
    long long ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ans += hash_map.visit(- C[i] - D[j]);
        }
    }
    cout << ans << endl;
    return 0;
}