HDU 3833 YY's new problem (hash)
9097 ワード
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
1], P[i
2], P[i
3] that
P[i
1]-P[i
2]=P[i
2]-P[i
3], 1<=i
123<=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
1, i
2, i
3 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
1つは2次ソートを利用することであり,2つはhashテーブルを利用することである.まずhash表について話しましょう.1からnシーケンスに題意を満たす3つの要素があるかどうかを見つける以上、この3つの要素には前後の順序があることに注意して、1つの配列でシミュレーションすることができます.まず配列をすべて0にしてから要素iの読み込みを開始し、1つの要素を読み込むたびにその要素を下付きのhashテーブルの要素に1、すなわちhash[i]++を加え、hashテーブルで探し、hash[i]の対称の前と後ろで検索し、hash[i-j]+hash[i+j]=1であれば、iが現れるときに2つの可能性があることを示します.一つはiより小さい数が現れたがiより大きい数が現れなかったり、iより大きい数が現れたり、iより小さい数が現れなかったり、現れなかった数がiの後ろに現れたり、すでに現れたのがiの前に現れたりして、これで問題意を満たすシーケンスが見つかった.
このアルゴリズムの応用範囲はもっと広いです.
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
1], P[i
2], P[i
3] that
P[i
1]-P[i
2]=P[i
2]-P[i
3], 1<=i
1
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
1, i
2, i
3 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
1つは2次ソートを利用することであり,2つはhashテーブルを利用することである.まずhash表について話しましょう.1からnシーケンスに題意を満たす3つの要素があるかどうかを見つける以上、この3つの要素には前後の順序があることに注意して、1つの配列でシミュレーションすることができます.まず配列をすべて0にしてから要素iの読み込みを開始し、1つの要素を読み込むたびにその要素を下付きのhashテーブルの要素に1、すなわちhash[i]++を加え、hashテーブルで探し、hash[i]の対称の前と後ろで検索し、hash[i-j]+hash[i+j]=1であれば、iが現れるときに2つの可能性があることを示します.一つは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
");
else
printf("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
");
else
printf("N
");
}
return 0;
}