首页 > 代码库 > POJ 1840 Eqs Hash + 中途相遇法
POJ 1840 Eqs Hash + 中途相遇法
把等式分成两拨算用中途相遇法就好了。
不过要注意的是这里不能用map,会超时,要自己手写hash,我重载了[]操作符之后用起来和map差不多,很随意
#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <deque>#include <bitset>#include <list>#include <cstdlib>#include <climits>#include <cmath>#include <ctime>#include <algorithm>#include <stack>#include <sstream>#include <numeric>#include <fstream>#include <functional>using namespace std;#define MP make_pair#define PB push_back#define tq(x) ((x)*(x)*(x))typedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int,int> pii;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const LL mod = 1000007;LL mabs(LL x) { return x < 0 ? -x : x;}struct Hash_Table { int first[mod], nxt[mod * 2]; LL val[mod * 2], cnt[mod * 2]; int sz; void clear() { memset(first,-1,sizeof(first)); sz = 0; } int hash_code(LL val) { return mabs(val) % mod; } Hash_Table() { clear(); } LL &operator[] (LL num) { int pos = hash_code(num); for(int i = first[pos];~i;i = nxt[i]) { if(val[i] == num) return cnt[i]; } nxt[sz] = first[pos]; val[sz] = num; cnt[sz] = 0; first[pos] = sz++; return cnt[sz - 1]; }};LL a1,a2,a3,a4,a5;Hash_Table mp;int main() { while(cin >> a1 >> a2 >> a3 >> a4 >> a5) { mp.clear(); LL ans = 0; for(int x1 = -50;x1 <= 50;x1++) if(x1) { for(int x2 = -50;x2 <= 50;x2++) if(x2) { for(int x3 = -50;x3 <= 50;x3++) if(x3) { LL val = a1 * tq(x1) + a2 * tq(x2) + a3 * tq(x3); mp[val]++; } } } for(int x4 = -50;x4 <= 50;x4++) if(x4) { for(int x5 = -50;x5 <= 50;x5++) if(x5) { LL val = a4 * tq(x4) + a5 * tq(x5); ans += mp[-val]; } } cout << ans << endl; } return 0;}
POJ 1840 Eqs Hash + 中途相遇法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。