首页 > 编程语言 > 详细

bestcoder#32 1002 哈希+后缀数组

时间:2015-03-12 16:41:58      阅读:211      评论:0      收藏:0      [点我收藏+]

bestcoder#32 1002 哈希+后缀数组

Negative and Positive (NP)


Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1161    Accepted Submission(s): 59


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
 
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.
 
Sample Input
2
1 1
1
2 1
-1 0
 
Sample Output
Case #1: Yes.
Case #2: No.
 
题意:查找是否存在sum(i,j)==K
思路:构造后缀数组d[],对sum(i,j)=d[j]-d[i-1],从n到1遍历i-1,插入d[i-1],从哈希表中查找是否存在d[i-1]+K;
注意这里不从1到n遍历j是因为项的正负是由i-1决定,所以比较方便;当然从n开始遍历j更容易理解,但不好处理正负号
题目还卡了STL的set,更坑的是还卡了scanf,我也因此学会了手写hash和读入外挂,很好的一道题
技术分享
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctype.h>
#include<algorithm>
#include<cmath>
#include<set>

using namespace std;

const int maxn=1000100;
const int HM=100100;
int n,K;
int a[maxn];
long long d[maxn];

struct Hash
{
    long long date;
    Hash *next;
};Hash h[HM];

void insert(long long date,Hash *h)
{
    int t=abs(date)%HM;
    Hash *pre=&h[t],*p=pre->next;
    while(p!=NULL){
        if(p->date=date) return;
        pre=p;
        p=p->next;
    }
    p=(Hash*)malloc(sizeof(Hash));
    p->date=date;p->next=NULL;
    pre->next=p;
}

bool find(long long date,Hash *h)
{
    int t=abs(date)%HM;
    Hash *pre=&h[t],*p=pre->next;
    while(p!=NULL){
        if(p->date==date) return true;
        pre=p;
        p=p->next;
    }
    return false;
}

inline int read()
{
    char c=getchar();
    while(c!=‘-‘&&!isdigit(c)) c=getchar();
    int f=0,tag=1;
    if(c==‘-‘){
        tag=-1;
        f=getchar()-‘0‘;
    }
    else f=c-‘0‘;
    while(isdigit(c=getchar())) f=f*10+c-‘0‘;
    return f*tag;
}

int main()
{
    int T=read();
    int tag=1;
    while(T--){
        n=read();K=read();
        d[0]=0;
        for(int i=1;i<=n;i++){
            a[i]=read();
            if(i&1) d[i]=d[i-1]+a[i];
            else d[i]=d[i-1]-a[i];
        }
        for(int i=0;i<HM;i++) h[i].next=NULL;
        bool flag=0;
        for(int i=n;i>=0;i--){
            insert(d[i],h);
            if(i&1){
                if(find(d[i]-K,h)) flag=1;
            }
            else if(find(d[i]+K,h)) flag=1;
            if(flag) break;
        }
        printf("Case #%d: ",tag++);
        if(flag) printf("Yes.\n");
        else printf("No.\n");
    }
    return 0;
}
bestcoder#32_1002

 

bestcoder#32 1002 哈希+后缀数组

原文:http://www.cnblogs.com/--560/p/4332548.html

踩
(0)
赞
(0)
   
举报
评论 一句话评论(0)
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!