HDU 3833 YY's new problem （hash）

YY's new problem

Time Limit: 12000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3158    Accepted Submission(s): 890

Problem Description

Given a permutation P of 1 to N, YY wants to know whether there exists such three elements P[i₁], P[i₂], P[i₃] that 
P[i₁]-P[i₂]=P[i₂]-P[i₃], 1<=i₁<i₂<i₃<=N.

 

Input

The first line is T(T<=60), representing the total test cases.
Each test case comes two lines, the former one is N, 3<=N<=10000, the latter is a permutation of 1 to N.

 

Output

For each test case, just output 'Y' if such i₁, i₂, i₃ can be found, else 'N'.

 

Sample Input

2 3 1 3 2 4 3 2 4 1

 

Sample Output

N Y

 

Source

2011 Multi-University Training Contest 1 - Host by HNU

 

Recommend

xubiao

一是利用二级排序，二是利用hash表。先说说hash表吧。既然要找到1到n序列中是否存在满足题意的三个元素，注意这三个元素有先后顺序之分，可以用一个数组来模拟。首先将数组全部清0，然后开始读入元素i，每读入一个元素就将以该元素为下标的hash表中的元素加1，即hash[i]++，然后在hash表中寻找，在hash[i]的对称的前面和后面查找，如果hash[i-j]+hash[i+j]==1, 说明在i出现时，有两种可能，一是比i小的数已经出现但比i大的数还没出现，或者比i大的数已经出现，比i小的数还没出现，没出现的数在i的后面，已经出现的在i的前面，这就找到了满足题意的序列。

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int n,hash[20010];

int main(){

    //freopen("input.txt","r",stdin);

    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(hash,0,sizeof(hash));
        int flag=0,x;
        for(int k=1;k<=n;k++){
            scanf("%d",&x);
            hash[x]++;
            if(flag==0){
                for(int i=1;i<x && i+x<=n;i++)
                    if(hash[x-i]+hash[x+i]==1){
                        flag=1;
                        break;
                    }
            }
        }
        if(flag)
            printf("Y\n");
        else
            printf("N\n");
    }
    return 0;
}

这个算法应用范围更广：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int n,num[10010];

int main(){

    //freopen("input.txt","r",stdin);

    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int x;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            num[x]=i;
        }
        int lim=2*(n-1),flag=0;
        for(int i=4;i<=lim && !flag;i+=2){
            for(int j=(i>n?i-n:1);j<(i>>1);j++){
                int k=i-j;
                if((num[j]-num[i>>1])*(num[i>>1]-num[k])>0){
                    flag=1;
                    break;
                }
            }
        }
        if(flag)
            printf("Y\n");
        else
            printf("N\n");
    }
    return 0;
}