HDU5183Negative and Positive (NP)(哈希表)

HDU5183Negative and Positive (NP)(哈希表)

題意：

給定一個長度為n的序列，判斷是否存在

一段序列 sum（i,j）= a i −a i+1 +a i+2 +?+(−1) j−i aj = k;

分析：

我們維護一段前綴和

sum[j]表示從開始到第j個元素， 即 sum(0,j);

然後我們將其加入到哈希表中

因為不同要麼是正負正 。。。。，要麼就是負正負。。。。的結構

因此我們維護兩個哈希表

表1插入 sum ,表2插入-sum;

當i為奇數的時候在表2中查詢 sum-k;

當i為偶數的時候在表1中查詢 sum+k

然後判斷存不存在就好

代碼如下：

#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int MAXN=1000010;
const int HASH=1000007;

inline LL read()//輸入外掛
{
    char ch=getchar();LL x=0,f=1;
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

struct hashmap//建立哈希表
{
    LL a[MAXN];
    int head[HASH],next[MAXN],size;
    void init(){//初始化
        memset(head,-1,sizeof(head));
        size=0;
    }
    bool find(LL val){//查找一個元素是否在哈希表內
        int tmp = (val%HASH + HASH)%HASH;
        for(int i = head[tmp];i!=-1;i=next[i])
            if(val==a[i]) return true;
        return false;
    }
    void add(LL val){//添加元素到哈希表中
        int tmp =(val%HASH+HASH)%HASH;
        if(find(val)) return;
        a[size]=val;
        next[size]=head[tmp];
        head[tmp]=size++;
    }
}h1,h2;

LL a[MAXN];

int main()
{
    int t,n,cas=1,k;
    t=read();
    while(t--){
        n=read();
        k=read();
        for(int i=0;i=0;i--){
            if(i&1) sum-=a[i];
            else sum+=a[i];
            if(i%2==0){
                if(h1.find(sum-k)) flag=1;
            }
            else{
                if(h1.find(sum+k)) flag=1;
            }
            h1.add(sum);
            h2.add(-sum);
            if(flag) break;
        }
        printf(Case #%d: ,cas++);
        if(flag)puts(Yes.);
        else puts(No.);
    }
    return 0;
}