做题的时候忘了 数据结构老师说的hash表了， 用二分找，还好过了， hash 表 对这题 更快一些

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 const int maxn =1000000+10; 8 typedef long long LL; 9 const int MAXN=1000010;10 const int HASH=1000007;11 inline LL read()12 {13     char ch=getchar();LL x=0,f=1;14     while(ch>'9'||ch<'0'){
   if(ch=='-')f=-1;ch=getchar();}15     while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}16     return x*f;17 }18 struct HASHMAP19 {20     int head[HASH],next[MAXN],size;21     LL state[MAXN];22     void init()23     {24         size=0;25         memset(head,-1,sizeof(head));26     }27     bool check(LL val)28     {29         int h=(val%HASH+HASH)%HASH;30         for(int i=head[h];~i;i=next[i])31             if(state[i]==val)return true;32         return false;33     }34     int insert(LL val)35     {36         int h=(val%HASH+HASH)%HASH;37         for(int i=head[h];~i;i=next[i])38         {39             if(val==state[i])40                 return 1;41         }42         state[size]=val;43         next[size]=head[h];44         head[h]=size++;45         return 0;46     }47 }H1;48 LL A[maxn];49 LL sum[maxn];50 int main()51 {52     int cas;53     scanf("%d",&cas);54     for(int cc =1; cc<=cas; ++cc){55         int n;56         LL K;57         scanf("%d%I64d",&n,&K);58         bool falg=false;59         for(int i=0; i
          
           =0; i--){71 sum[i]=sum[ i+1 ]+A[ i ]*sig;72 if(sig==1){73 to = sum[i]-K;74 if(H1.check(to)){75 falg=true ; break;76 }77 } else{78 to= -(-sum[i]-K);79 if(H1.check(to)){80 falg=true ; break;81 }82 }83 sig*=-1;84 H1.insert(sum[i]);85 }86 if(falg)87 printf("Yes.\n");88 else printf("No.\n");89 }90 91 return 0;92 }