hdu3833 YY's new problem--哈希表

2016-12-02 12:52:26来源:网络收集作者:一线码农人点击

原题链接:
/2014th7cj/d/file/p/20161129/mecrapvbteb.php Description
Given a permutation P of 1 to N, YY wants to know whether there exists such three elements P[i1], P[i2], P[i3] thatP[i1]-P[i2]=P[i2]-P[i3], 1<=i1Input
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 i1, i2, i3 can be found, else 'N'.
Sample Input
2
3
1 3 2
4
3 2 4 1Sample Output
N
Y

二:分析理解


好吧!再次感受到算法的强大。


把问题转化下就好。


P[i1]-P[i2]=P[i2]-P[i3]转化为P[i1]+P[i3]=2*P[i2]


枚举i1和i3,和是偶数才可以继续判断,看代码。


三:AC代码


#include
#include
#include
#include
using namespace std;
#define N 10005
int a[N];
int hash1[N];
int T;
int n;
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
hash1[a[i]] = i;
}
int flag = 0;
for (int i = 0; i <= n - 2; i++)
{
for (int j = i + 2; j <= n - 1; j++)
{
int s = a[i] + a[j];
if (s % 2)
continue;
if (hash1[s / 2] > i&&hash1[s / 2] < j)
{
flag = 1;
break;
}
}
if (flag)
break;
}
printf("%s/n", flag ? "Y" : "N");
}

return 0;
}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台