HDU5183 Negative and Positive (NP) 散列表

本文主要是介绍HDU5183 Negative and Positive (NP) 散列表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5183

题目大意

有一个共n个数的数组a[1],a[2],a[3],……,a[n]（这里我把a0开始转化为了a1开始）。
定义sum(i,j)为a[i]-a[i+1]+a[i+2]-…+(-1)^(j-i)*a[j]。（a^b表示a的b次方）
现在求有没有任何(i,j)使得sum(i,j)=k。

思路一——暴力枚举i和j，暴力计算sum(i,j)

思路一为暴力，时间复杂度O(n^3)，用两层for循环遍历，一层for循环计算sum(i,j)。
计算如下：

bool cal() {for(int i=1; i<=n; i++) {for(int j=i; j<=n; j++) {int sum=0;for(int k=i; k<=j; k++) {if((k-i)&1) {   //k与i奇偶性相同sum+=a[i];} else {sum-=a[i];}}if(sum==k) {return true;}}}return false;
}

然而，由于时间复杂度太高，O(n^3)的会超时，所以还要想出时间复杂度较低的算法。

思路二——暴力枚举i和j，优化计算sum(i,j)

思路二也是暴力的方法，但是sum(i,j)可以不用这么复杂。
因为sum(i,j)=a[i]-a[i+1]+a[i+2]-…+(-1)^(j-i)*a[j]
而sum(i,j+1)=a[i]-a[i+1]+a[i+2]-…+(-1)^(j-i)*a[j]+(-1)^(j-i+1) *a[j+1]，
所以可以得到sum(i,j+1)=sum(i,j)+(-1)^(j-i+1) *a[j+1]。
这样就可以少一层循环，避免暴力计算sum(i,j)，时间复杂度O(n^2)。
代码就不在这里展示了。

思路三——前缀和并将其放进散列表

思路三：考虑前缀和——
sum[i]表是sum(1,i)，即a[1]-a[2]+a[3]-…+(-1)^(i-1)*a[i]。
如果要求sum(i,j)，可以考虑把两个前缀和相减，而这里需要分类讨论：
（1）i是奇数，此时
——sum[i-1]=a[1]-a[2]+a[3]-…-a[i-1]，
——sum[j]=a[1]-a[2]+a[3]-…+a[i]-…+(-1)^(j-1)*a[j]。
——那么sum(i,j)=sum[j]-sum[i-1]。
（2）i是偶数，此时
——sum[i-1]=a[1]-a[2]+a[3]-…+a[i-1]，
——sum[j]=a[1]-a[2]+a[3]-…-a[i]+…+(-1)^(j-1)*a[j]。
——那么sum(i,j)=-(sum[j]-sum[i-1])。
现在要知道是否有sum(i,j)=k，那么只要知道
当i为奇数时是否有sum[j]-sum[i-1]=k，当i为偶数时是否有sum[j]-sum[i-1]=-k即可。
说了这么多废话，现在仍然要枚举i和j两个数，还是O(n^2)的时间复杂度，所以考虑使用散列表。
当i为奇数时，只需查找是否有sum[j]=sum[i-1]+k (i<=j)。
则将所有sum[j]都插入散列表，然后在里面查找sum[i-1]+k即可。
当i为偶数时同理查找sum[i-1]-k即可。

空间的优化

由于这里sum[1],sum[2],…,sum[n]都只用了一遍，所以可以学习思路二，用一个sum变量来表示当前的sum[i]。

注意事项

1.虽然所有的数据都在int范围内，但是sum(i,j)可能超过int范围，所以要用long long！！
2.注意初始化和一开始把0插入散列表。

代码

用结构体指针写的链表，比较丑，凑合着看看：

//HDU 5183
#include<stdio.h>
#include<cstring>
using namespace std;
typedef long long ll;               //要用long long
ll read() {                         //快速读入ll x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=10*x+ch-'0';ch=getchar();}return x*f;
}
const int C=500007;                 //取模的C值
struct node {ll val;node *next;                     //hash表中每个节点都是一个链表
} *hash[(C+1)<<1];
/*由于有负数，所以把负数模C之后再加C使其变为正数*/
bool find(ll p) {                   //在链表中寻找一个数pnode *a=hash[(p%C+C)%C];while(a!=NULL) {if(a->val==p)return true;a=a->next;}return false;
}
void Hash(ll p) {                   //把p插入到散列表中node *tmp=new node;tmp->val=p;tmp->next=hash[(p%C+C)%C];hash[(p%C+C)%C]=tmp;
}
const int Size=1000003;
int n,k;
int a[Size];
void init() {                       //初始化n=read(),k=read();for(int i=1; i<=n; i++)a[i]=read();memset(hash,0,sizeof(hash));   //将val重置成0，将next重置成NULLHash(0);                       //注意！要把0放进散列表
}
int main() {
//  freopen("data.txt","r",stdin);
//  freopen("WA.out","w",stdout);int t=read(),ans;for(int now=1; now<=t; now++) {init();ll sum=0;bool flag=false;for(int i=n; i>0; i--) {if(i&1) {               //如果i是奇数则a[i]前是正号sum+=a[i];} else {sum-=a[i];}if(i&1) {if(find(sum-k)) {flag=true;ans=i;break;}} else {if(find(sum+k)) {flag=true;ans=i;break;}}Hash(sum);             //把sum插入到散列表中}if(flag) {printf("Case #%d: Yes.\n",now);} else {printf("Case #%d: No.\n",now);}}return 0;
}
/*
2
1 1
1
2 1
-1 0
*/