首页 > 代码库 > POJ 3474 Gold Balanced Lineup Hash
POJ 3474 Gold Balanced Lineup Hash
题意一开始不是很明确， 后来发现是每一种特征出现的次数相同
这样一来就变成简单hash问题了，如果把每个特征看看做是一个(n+1)进制数的话，对奶牛序列求一下前缀和，如果i - j这一段每一种特征出现的次数相同的话，把i - 1点和j点的每一位减去所有位中的最小值之后，必然相等，所以hash判断一下就好。
#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_backtypedef 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 int maxn = 100000 + 10;const int maxk = 30;const int mod = 65536;int n,k;struct Node { int data[maxk]; Node(int val = 0) { int pos = 0; memset(data,0,sizeof(data)); while(val) { data[pos++] = val & 1; val >>= 1; } } bool operator == (const Node &node) const { for(int i = 0;i < k;i++) if(node.data[i] != data[i]) return false; return true; }};Node operator + (Node a,Node b) { for(int i = 0;i < k;i++) { a.data[i] += b.data[i]; } return a;}void con(Node &node) { int minval = INF; for(int i = 0;i < k;i++) minval = min(minval,node.data[i]); for(int i = 0;i < k;i++) node.data[i] -= minval;}int gethash(const Node &node) { int ret = 0; for(int i = 0;i < k;i++) { ret = ret * (n + 1) + node.data[i]; } return ret & (mod - 1);}Node cow[maxn],val[maxn];int head[mod],nxt[maxn],pos[maxn],sz;int ask(const Node &node,int p) { int hc = gethash(node); for(int i = head[hc];~i;i = nxt[i]) { if(val[i] == node) return pos[i]; } val[sz] = node; pos[sz] = p; nxt[sz] = head[hc]; head[hc] = sz++; return p;}int main() { while(scanf("%d%d",&n,&k) != EOF) { memset(head,-1,sizeof(head)); sz = 0; for(int i = 1;i <= n;i++) { int tmp; scanf("%d",&tmp); cow[i] = cow[i - 1] + Node(tmp); } for(int i = 1;i <= n;i++) con(cow[i]); int ans = 0; for(int i = 0;i <= n;i++) { // for(int j = 0;j < k;j++) printf("%d ",cow[i].data[j]); putchar(‘\n‘); int pos = ask(cow[i],i); ans = max(ans,i - pos); } printf("%d\n",ans); } return 0;}
POJ 3474 Gold Balanced Lineup Hash
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。