hdu 3833 YY's new problem
2327 ワード
YY's new problem
Time Limit: 12000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 5443 Accepted Submission(s): 1530
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
Sample Output
Source
2011 Multi-University Training Contest 1 - Host by HNU
考え方:
1個からnの配列について,前K個の数にXがなければ,残りの数には必ずXが含まれている.
与えられた式から2 P[i 2]=P[i 1]+P[i 3]、すなわちP[i 1]とP[i 3]はP[i 2]対称であることが分かる.
まず、h配列を0とマークし、その後、要素xを読み込み、1つの要素を読み込むたびに、その要素に対応する下付きh配列を1として付与する.次に,h配列において,この要素の対称前方と後方,すなわちh[x−j]とh[x+j]を探し,h[x+j]+h[x−j]=1であればシーケンスを見つけた.
Time Limit: 12000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 5443 Accepted Submission(s): 1530
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
考え方:
1個からnの配列について,前K個の数にXがなければ,残りの数には必ずXが含まれている.
与えられた式から2 P[i 2]=P[i 1]+P[i 3]、すなわちP[i 1]とP[i 3]はP[i 2]対称であることが分かる.
まず、h配列を0とマークし、その後、要素xを読み込み、1つの要素を読み込むたびに、その要素に対応する下付きh配列を1として付与する.次に,h配列において,この要素の対称前方と後方,すなわちh[x−j]とh[x+j]を探し,h[x+j]+h[x−j]=1であればシーケンスを見つけた.
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int h[20010];// 1 n ， 1。
int main()
{
int t,n,i,j,x;
scanf("%d",&t);
while(t--)
{
int flag=0;
scanf("%d",&n);
memset(h,0,sizeof(h));
for(i=1;i<=n;i++)
{
scanf("%d",&x);
h[x]=1;
if(flag) continue;
for(j=1;x-j>0&&x+j<=n;j++)
{
if(h[x-j]+h[x+j]==1)//p[i1],p[i3]
{
flag=1;break;
}
}
}
if(flag) printf("Y
");
else printf("N
");
}
return 0;
}