手写堆（优先队列），手写hash

本文主要是介绍手写堆（优先队列），手写hash，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 1 struct rec {
 2     int a, b; // 两个变量，其中a>=b
 3     int val, cnt; // 未来估价val，当前次数cnt
 4     rec() {}
 5     rec(int a_, int b_, int val_, int cnt_) {
 6         a = a_, b = b_, val = val_, cnt = cnt_;
 7     }
 8 };
 9 int n;
10 const int N = 1000000, mod = 999983;
11 priority_queue<rec> q;
12 pair<int, int> ver[N];
13 int head[N], d[N], nxt[N], tot; // 手动hash
14 
15 inline bool operator <(const rec &a, const rec &b) {
16     return a.val + a.cnt > b.val + b.cnt;
17 }
18 
19 // 估价函数，把a不断自加直至>=n所需的次数（注意a>=b），显然实际所需次数不会小于这一次数
20 inline int calc(int a, int b) {
21     int val = 0;
22     for (; a < n; a *= 2) val++;
23     return val;
24 }
25 
26 inline int gcd(int a, int b) {
27     return b ? gcd(b, a%b) : a;
28 }
29 
30 inline bool get_or_update(int a, int b, int cnt) {
31     int hash = (long long)a * b % mod;
32     for (int i = head[hash]; i; i = nxt[i]) {
33         if (ver[i].first == a && ver[i].second == b) {
34             if (d[i] > cnt) {
35                 d[i] = cnt;
36                 return true;
37             }
38             return false;
39         }
40     }
41     d[++tot] = cnt;
42     ver[tot] = make_pair(a, b);
43     nxt[tot] = head[hash], head[hash] = tot;
44     return true;
45 }
46 
47 inline void insert(int a, int b, int cnt) {
48     if (a < b) swap(a, b); // 保证a>=b
49     if (n % gcd(a, b)) return; // 剪枝
50     bool updated = get_or_update(a, b, cnt);
51     if (updated) q.push(rec(a, b, calc(a, b), cnt));
52 }

这篇关于手写堆（优先队列），手写hash的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！