Negative and Positive (NP)
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
When given an array
(a0,a1,a2,?an?1) and an integer
K , you are expected to judge whether there is a pair
(i,j)(0≤i≤j<n) which makes that
NP?sum(i,j) equals to
K true. Here
NP?sum(i,j)=ai?ai+1+ai+2+?+(?1)j?iaj
Input
Multi test cases. In the first line of the input file there is an integer
T indicates the number of test cases.
In the next 2?T lines, it will list the data for each test case.
Each case occupies two lines, the first line contain two integers n and K which are mentioned above.
The second line contain (a0,a1,a2,?an?1) separated by exact one space.
[Technical Specification]
All input items are integers.
0<T≤25,1≤n≤1000000,?1000000000≤ai≤1000000000,?1000000000≤K≤1000000000
In the next 2?T lines, it will list the data for each test case.
Each case occupies two lines, the first line contain two integers n and K which are mentioned above.
The second line contain (a0,a1,a2,?an?1) separated by exact one space.
[Technical Specification]
All input items are integers.
0<T≤25,1≤n≤1000000,?1000000000≤ai≤1000000000,?1000000000≤K≤1000000000
Output
For each case，the output should occupies exactly one line. The output format is Case #id: ans, here id is the data number starting from 1; ans is “Yes.” or “No.” (without quote) according to whether you can find
(i,j) which makes
PN?sum(i,j) equals to
K .
See the sample for more details.
See the sample for more details.
Sample Input
2 1 1 1 2 1 -1 0
Sample Output
Case #1: Yes. Case #2: No.HintIf input is huge, fast IO method is recommended.
Source
BestCoder Round #32
/************************************************************************/
附上该题对应的中文题
Negative and Positive (NP)
Time Limit: 3000/1500 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
给定一个数组(a?0??,a?1??,a?2??,?a?n?1??)和一个整数K， 请来判断一下是否存在二元组(i,j)(0≤i≤j<n)使得 NP?sum(i,j) 刚好为K。这里。
输入描述
多组测试数据。在文件的第一行给出一个T，表示有T组数据。 在接下来的2?T行里，将会给出每一组数据。 每一组数据占两行，第一行包含n和K。 第二行包含(a?0??,a?1??,a?2??,?a?n?1??)以一个空格分开。 [参数说明] 所有输入均为整数。 0<T≤25,1≤n≤1000000,?1000000000≤ai≤1000000000,?1000000000≤K≤1000000000
输出描述
对于每一个数据，输出占一行，输出格式是Case #id: ans,这儿id是数据编号，从1开始，ans是根据是否找到满足的二元组而定为“Yes.” 或 “No.” (不包含引号) 看样例可以获得更多的信息。
输入样例
2 1 1 1 2 1 -1 0
输出样例
Case #1: Yes. Case #2: No.
Hint
如果数据比较多，建议使用快速读入。
/****************************************************/
出题人的解题思路：
维护前缀和sum[i]=a[0]-a[1]+a[2]-a[3]+…+(-1)^i*a[i] 枚举结尾i，然后在hash表中查询是否存在sum[i]-K的值。 如果当前i为奇数，则将sum[i]插入到hash表中。 上面考虑的是从i为偶数为开头的情况。 然后再考虑以奇数开头的情况，按照上述方法再做一次即可。 不同的是这次要维护的前缀和是sum[i]=-（a[0]-a[1]+a[2]-a[3]+…+(-1)^i*a[i]） I为偶数的时候将sum[i]插入到hash表。 总复杂度o(n)该题的解法，出题人讲得很明确，利用哈希函数，我们将求得的sum[i](前i项的NP-sum值)求出来放入哈希表中，遍历一遍即可判断是否存在一个二元组满足条件
我要提的一点是题目的读入优化，因为题目的数据比较多，普通的输入耗的时间也会比较长，容易TLE，所以此题需用到读入优化，详情可点击链接
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
#define ll __int64
using namespace std;
const int N = 1000005;
const int inf = 1000000000;
const int mod = 1000005;
struct node
{int to;ll v;
}e[N];
int s[N],h[N],p;
void add(ll x)
{e[p].v=x;x=abs(x)%N;e[p].to=h[x];h[x]=p++;
}
bool check(ll x)
{int k=abs(x)%N;for(int i=h[k];i+1;i=e[i].to)if(e[i].v==x)return true;return false;
}
int get_val(int &ret)
{int sgn=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-')sgn=-1,ret=0;elseret=c-'0';while((c=getchar())>='0'&&c<='9')ret=ret*10+c-'0';ret*=sgn;
}
int main()
{int t,n,k,i,j=1;ll sum;get_val(t);while(t--){sum=0;p=0;memset(h,-1,sizeof(h));get_val(n);get_val(k);for(i=0;i<n;i++)get_val(s[n-i-1]);add(0);printf("Case #%d: ",j++);for(i=0;i<n;i++){sum+=(i&1)?-s[i]:s[i];add(sum);if(i&1){if(check(sum+k)){puts("Yes.");break;}}else if(check(sum-k)){puts("Yes.");break;}}if(i>=n)puts("No.");}return 0;
}