Negative and Positive (NP)
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 3233 Accepted Submission(s): 871
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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<vector>
#include<set>
using namespace std;
const int maxn=1000010;
long long num[maxn];
set<long long >S;
int main()
{int t,i,j,test=1;long long n,k;scanf("%d",&t);while(t--){scanf("%lld%lld",&n,&k);for(i=1;i<=n;++i){scanf("%lld",&num[i]);if(i&1)num[i]=num[i-1]+num[i];else num[i]=num[i-1]-num[i];}S.clear();bool sign=false;for(i=n;i>=0;--i){if(i&1){if(S.find(num[i]-k)!=S.end()){sign=true;break;}}else {if(S.find(num[i]+k)!=S.end()){sign=true;break;}}S.insert(num[i]); }printf("Case #%d: ",test++);if(sign){printf("Yes.\n");}else {printf("No.\n");}}return 0;
}