hdu 5138

参考……！！！！

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <cctype>
#include <string>
#include <malloc.h>
#include <queue>
#include <map>
#include <set>

using namespace std;

const int INF = 0xffffff;
const double esp = 10e-8;
const double Pi = 4 * atan(1.0);
const int maxn =  1000000 + 10;
const long long mod =  1000000007;
const int dr[] = {1,0,-1,0,-1,1,-1,1};
const int dc[] = {0,1,0,-1,1,-1,-1,1};
typedef long long LL;

LL gac(LL a,LL b){
    return b?gac(b,a%b):a;
}
const int hashtable = 1000007;
struct Hash{
    int head[hashtable];
    int _next[maxn];
    long long state[maxn];
    int cnt;
    void init(){
        cnt = 1;
        memset(head,0,sizeof(head));
    }
    bool _find(LL s){
        int h = (s % hashtable+hashtable)%hashtable;
        int u = head[h];
        while(u){
            if(s == state[u])
                return 1;
            u = _next[u];
        }
        return 0;
    }
    bool try_to_insert(LL s){
        int h = (s % hashtable+hashtable)%hashtable;
        _next[cnt] = head[h];
        state[cnt] = s;
        head[h] = cnt;
        cnt++;
        return 0;
    }

};
Hash H1,H2;
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;
}
LL a[maxn];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("inpt.txt","r",stdin);
   // freopen("output.txt","w",stdout);
#endif
    int t;
    scanf("%d",&t);
    for(int cas = 1;cas <= t;cas++){
        int n,k;
        scanf("%d%d",&n,&k);
        H1.init();
        H2.init();
        LL sum = 0;
        bool ok = 0;
        H1.try_to_insert(0);
        H2.try_to_insert(0);
        for(int i = 0;i < n;i++){
            a[i] = read();
        }
        for(int i = n-1;i > -1 && !ok;i--){
            if(ok)
                continue;
            if(i % 2 == 1){
                sum -= a[i];
                if(H2._find(-sum-k)){
                    ok = 1;
                }
            }
            else{
                sum += a[i];
                if(H1._find(sum-k)){
                    ok = 1;
                }
            }
            H1.try_to_insert(sum);
            H2.try_to_insert(-sum);
        }
        printf("Case #%d: %s.
",cas,ok?"Yes":"No");
    }
    return 0;
}