FZU1465

题目链接:传送门

题目大意:给你n个整数（可正可负），求有多少个连续的子序列的和==m(时限1S)

题目思路:前缀和+手写hash(map效率太慢，会超时)

具体做法是用一个数组sum，数组的第i位保存前1~i个数的和，那么从第x个元素到到第y个元素的和就可以表示为sum[y]-sum[x]

现在我们要求有多少个连续子序列的和==m，也就是找出有多少个sum[y]-sum[x]==m。

　　　　 如果给你的数都是正整数就好办了，不难想到可以用尺取法(双指针扫描)，但是难点在于有负数，也就是sum数组的值很杂乱。

但其实，我们观察一下式子    sum[y]-sum[x]==m，如果把它转换一下   sum[y]-m=sum[x]。那么我们对于sum[i]，只需要找到

在i之前出现了多少sum[i]-m，答案就加上sum[i]-m的个数，所以我们只需从头扫一遍即可。复杂度O(n)，但是map效率太慢，所以还需

手写hash

MAP超时代码

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #include <vector>

 #include <string>

 #include <stack>

 #include <cmath>

 #include <cstdlib>

 #include <iostream>

 #include <map>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 typedef long long ll;

 const int mod = ;

 const int N = 1e6 + ;

 map<ll, int> mp;

 ll sum[N];

 int main() {

     int n, m, v;

     int group; scanf("%d", &group);

     while(group--) {

         scanf("%d%d", &n, &m);

         sum[] = ;

         for(int i = ; i <= n; ++i) {

             scanf("%d", &v);

             sum[i] = sum[i - ] + v;

         }

         int ans = ;

         mp.clear(); mp[] = ;

         for(int i = ; i <= n; ++i) {

             ll s = sum[i] - m;

             int num = mp[s];

             ans += num;

             mp[sum[i]]++;

         }

         printf("%d\n", ans);

     }

     return ;

 }

AC代码

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 #include <cstring>

 #define mst(x,y) memset(x,y,sizeof(x))

 using namespace std;

 const long long MOD=(1ll<<);

 const long long MMM=;

 const int N=;

 int n,m;

 long long key[N],sum[N];

 int head[MMM],cnt[N],next[N],hcnt;

 struct Myhas{

     void init(){

         mst(head,-);

         mst(cnt,);

         hcnt=;

     }

     void ins(long long x){

         int h=x%MMM;

         key[hcnt]=x;

         cnt[hcnt]=;

         next[hcnt]=head[h];

         head[h]=hcnt++;

     }

     void add(long long x){

         int h=x%MMM;

         for(int i=head[h];~i;i=next[i]){

             if(key[i]==x){++cnt[i];return;}

         }

     }

     int query(long long x){

         int h=x%MMM;

         for(int i=head[h];~i;i=next[i]){

             if(key[i]==x) return cnt[i];

         }

         return -;

     }

 }has;

 int main(){

     int i,j,group,x,ans;

     scanf("%d",&group);

     while(group--){

         scanf("%d%d",&n,&m);

         for(i=;i<=n;++i){

             scanf("%d",&x);

             sum[i]=sum[i-]+x;

         }

         ans=;

         has.init();

         has.ins(MOD);

         for(i=;i<=n;++i){

             long long xx=sum[i]-m+MOD;

             int num=has.query(xx);

             if(num!=-)ans+=num;

             xx=(sum[i]+MOD);

             if(has.query(xx)!=-)has.add(xx);

             else has.ins(xx);

         }

         printf("%d\n",ans);

     }

     return ;

 }