用set处理链地址会TLE,但是vector枚举链地址却能过?
查看原帖
用set处理链地址会TLE,但是vector枚举链地址却能过?
25016
icysky楼主2020/7/17 22:25

是set的常数太大吗?一般来说查找set不是应该比枚举vector快的吗?

T掉的代码在这里:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#define _for(i, a, b) for (int i = (a); i < (b); i++)
#define _rep(i, a, b) for (int i = (a); i <= (b); i++)

using namespace std;
typedef long long ll;
const ll MOD = 56611;
const ll maxn = MOD * 2;
const ll K = 2147483648 + 5;


set<ll> Hash[maxn];
ll T, n, tmp;

void read(ll &x) {
    x = 0; int f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    x *= f;
}

void init() {
    _for(i, 0, maxn) Hash[i].clear();
}

ll GetHash(const ll &x) {
    return (x % MOD + MOD) & MOD;
}

ll find(const ll &x) {
    ll hs = GetHash(x);
    if (Hash[hs].count(x)) return hs;
    return -1;
}

void insert(const ll &x) {
    Hash[GetHash(x)].insert(x);
}

int main() {
    read(T);
    while (T--) {
        init();
        read(n);

        _for(i, 0, n) {
            read(tmp);
            if (find(tmp) != -1) continue;

            if (i != 0)
                printf(" %lld", tmp);
            else 
                printf("%lld", tmp);
            insert(tmp);
        }
        putchar('\n');
    }
    return 0;
}
2020/7/17 22:25
加载中...