Negative and Positive (NP)
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2177 Accepted Submission(s): 556
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.
Case #2: No.
Hint
If input is huge, fast IO method is recommended.
Source
#include<stdio.h>
#include<string.h>
typedef long long ll ;
const int mod = + ;
int a[mod] ;
ll sum[mod] ;
int n , k ; struct edge
{
int nxt ;
int node ;
}e[mod];
int head[mod] , top ; void init ()
{
memset (head , , sizeof(head)) ;
top = ;
} void insert (ll x)
{
int y = x % mod ;
if (y < )
y += mod ;
e[++top].nxt = head[y] ;
e[top].node = x ;
head[y] = top ;
} bool find (ll x)
{
int y = x % mod ;
if (y < )
y += mod ;
for (int i = head[y] ; i ; i = e[i].nxt) {
if (e[i].node == x)
return true ;
}
return false ;
} int main ()
{
//freopen ("a.txt" , "r" , stdin) ;
int T ;
scanf ("%d" , &T) ;
int ans = ;
while (T--) {
scanf ("%d%d" , &n , &k) ;
for (int i = ; i <= n ; i++) {
scanf ("%d" , &a[i]) ;
}
sum[] = ;
for (int i = ; i <= n ; i++) {
if (i & )
sum[i] = sum[i - ] + a[i] ;
else
sum[i] = sum[i - ] - a[i] ;
}
init () ;
bool flag = ;
for (int i = n ; i > && !flag ; i--) {
insert (sum[i]) ;
ll w ;
if (i & )
w = sum[i - ] + k ;
else
w = sum[i - ] - k ;
if (find (w))
flag = true ;
}
if (flag)
printf ("Case #%d: Yes.\n" , ++ans ) ;
else
printf ("Case #%d: No.\n" , ++ans ) ;
}
return ;
}
583ms
第一次遇到哈希表，它能把查找一个数的复杂度降到0（1） 。
我学会的那种写法是通过“ 前向星 ”实现的，
他通过对插入数取余把数字存到数组中，从而防止了carsh ， nxt记录的是上一个和当前输入的数 取余 后相等的数 在 数组中的下标。
这道题思路：
sum[i] = a0 － ａ１…… （－１）＾ｎ*an ;
将他们存入哈希表中
然后从n~1寻找哈希表中是否有sum[i] + k
ps:另外用lower_bound + sort也能办到