网站首页轮播图怎么做,东莞代理公司注册,进行网站开发,网站维护 关站 seohdu 5183(Hash处理区间问题) 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid5183 题意:给出一个n个元素的数组,现在要求判断 a1-a2a3-a4...../-an 中是否存在某个某个区间使得 ai-ai1ai2...(-1)j-iaj k?? 这个题要利用Hash就可以实现几乎在 O(n) 的时间内实现查找判断…hdu 5183(Hash处理区间问题) 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid5183 题意:给出一个n个元素的数组,现在要求判断 a1-a2a3-a4...../-an 中是否存在某个某个区间使得 ai-ai1ai2...(-1)j-iaj k?? 这个题要利用Hash就可以实现几乎在 O(n) 的时间内实现查找判断. 记录前缀和然后枚举起点进行判断。分两种情况进行考虑: 1.起点 i 为奇数,那么 a[i]-a[i1]a[i2]....(-1)^(j-i)*a[j] sum[j] - sum[i-1] k ,每次枚举 sum[i-1] k 如果在hash表中存在 ,就证明存在此区间. 2.起点 i 为偶数,那么 -a[i]a[i1]-a[i2]....(-1)^(j-i)*a[j] sum[j] - sum[i-1] -k ,每次枚举 sum[i-1] - k ,查找hash表。与上一步类似. #include iostream
#include cstdio
#include cstring
#include queue
#include algorithm
#include math.h
using namespace std; typedef long long LL; const int N 1000005; const int H 1000007; int Hash[H],cur; void initHash(){ memset(Hash,-1,sizeof(Hash)); cur 0; } struct Node{ LL v; int next; }node[N]; void insertHash(LL v){ int num (int)(v%HH)%H; node[cur].v v; node[cur].next Hash[num]; Hash[num] cur; } bool searchHash(LL v){ int num (int)(v%HH)%H; for(int k Hash[num];k!-1;knode[k].next){ if(node[k].vv) return true; } return false; } LL sum[N]; int main() { int tcase,t1; scanf(%d,tcase); while(tcase--){ initHash(); int n,k; scanf(%d%d,n,k); sum[0] 0; for(int i1;in;i){ LL x; scanf(%lld,x); if(i%2) sum[i] sum[i-1]x; else sum[i] sum[i-1]-x; } insertHash(sum[n]); bool flag false; for(int in;i1;i--){ if(i%21searchHash(sum[i-1]k)){ flag true; break; } if(i%20searchHash(sum[i-1]-k)){ flag true; break; } insertHash(sum[i]); } printf(Case #%d: ,t); if(flag) printf(Yes.\n); else printf(No.\n); } return 0; }转载于:https://www.cnblogs.com/a-blog-of-taojiayi-2003/p/10589033.html
