手写堆(优先队列),手写hash
2022/4/18 6:15:12
本文主要是介绍手写堆(优先队列),手写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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性