首页 > 代码库 > G - YY's new problem(HUSH算法，目前还不懂什么是HUSH算法）

G - YY's new problem(HUSH算法，目前还不懂什么是HUSH算法）

2024-07-16 01:15:10   222人阅读

 
Time Limit:4000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u
Submit Status Practice HDU 3833

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] that
P[i1]-P[i2]=P[i2]-P[i3], 1<=i1<i2<i3<=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 i1, i2, i3 can be found, else ‘N‘.
 

Sample Input

231 3 243 2 4 1
 

Sample Output

NY
 
 1 #include<cstdio> 2 #include<string.h> 3 using namespace std; 4 int hush[10005]; 5 int str[10005]; 6 int main() 7 { 8     int t,n; 9     while(scanf("%d",&t)!=EOF)10     {11         while(t--)12         {13             scanf("%d",&n);14             for(int i=1; i<=n; i++)15             {16                 scanf("%d",&str[i]);//把1——N保存到数组里17                 hush[str[i]]=i;//记录每个数的位置18             }19             int flag=0;20             for(int i=1; i<=n; i++)21             {22                  for(int j=i+1; j<=n; j++)23                 {24                    int temp=str[i]+str[j];//相加25                    if(temp%2)//优化，必须是偶数才行，尽量别写成temp%2==1,直接写temp%226                      continue;27                    if(hush[temp/2]>i&&hush[temp/2]<j)28                    {29                        flag=1;30                        break;31                    }32                 }33                 if(flag==1) break;34             }35             printf("%c",flag==1?‘Y‘:‘N‘);36             printf("\n");37         }38     }39     return 0;40 }

 

 


联系
我们