Negative and Positive (NP)Time Limit: 3000/1500 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2488Accepted Submission(s): 618
Problem Description
When given an arrayand an integer, you are expected to judge whether there is a pairwhich makes thatequals totrue. Here
Input
Multi test cases. In the first line of the input file there is an integerindicates the number of test cases.In the nextlines, it will list the data for each test case.Each case occupies two lines, the first line contain two integerswhich are mentioned above.The second line containseparated by exact one space.[Technical Specification]All input items are integers.
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 findwhich makesequals to.See the sample for more details.
Sample Input
21 112 1-1 0
Sample Output
Case #1: Yes.Case #2: No.
Hint
If input is huge, fast IO method is recommended.
Source
Recommend
hujie|We have carefully selected several similar problems for you:51895188518551845181
题意：问有没有数对(i,j)(0<=i<=j<n),使得a[i]-a[i+1]+…+(-1)^(j-i)a[j]为K.
思路：先计算出前缀和sum，然后枚举起点，从后往前枚举起点i，若i为奇数，则看set里面有没有sum[i-1]+k；若i为偶数，则看set里面有没有sum[i-1]-k。要用到输入外挂，不知道为什么，我的代码用G++交有时能过，，有时却TLE，难道还要看OJ的心情吗=。=
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 1005000#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FRL(i,a,b) for(i = a; i < b; i++)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;ll sum[maxn];ll a[maxn];ll n,k;set<ll>s;inline bool scan_d(ll &ret) //输入外挂{char c;ll sgn;if (c=getchar(),c==EOF) return false;while (c!='-'&&(c<'0'||c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while (c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');ret*=sgn;return true;}int main(){ll x;ll i,j,t,cas=1;scan_d(t);while (t–){scan_d(n);scan_d(k);FRL(i,1,n+1)scan_d(a[i]);sum[0]=0;sum[1]=a[1];FRL(i,2,n+1) //计算前缀和{if (i%2)sum[i]=sum[i-1]+a[i];elsesum[i]=sum[i-1]-a[i];}s.clear();bool flag=false;for (i=n;i>0;i–){s.insert(sum[i]); //现插入集合if (i%2){if (s.find(sum[i-1]+k)!=s.end()){flag=true;break;}}else{if (s.find(sum[i-1]-k)!=s.end()){flag=true;break;}}}if (flag)pf("Case #%lld: Yes.\n",cas++);elsepf("Case #%lld: No.\n",cas++);}return 0;}
带着感恩的心启程，学会爱，爱父母，爱自己，爱朋友，爱他人。
