hdu-3833 YY's new problem(数组标记)

http://acm.hdu.edu.cn/showproblem.php?pid=3833

做这题时是因为我在网上找杭电的数论题然后看到说这道题是数论题就点开看了以下。

然后去杭电上做，暴力，超时了，想了半天还是没啥好办法，到底哪要用到数论的知识呢，想不出还得去搜题解，脑子笨啊。

然后说用hash再报暴力，没看人家代码，然后就顺着这思路写，我写的是当前是a[i];然后j从1到i-1,用2*a[i]-a[j]的另一个数并且这个数的范围为1到N;而且在1到i-1中没出现过

那么必定在i的右侧，这个可以用hash数组记录一下，在1到i出现的a[i]都标记为1；也就是hash[a[i]]=1;

那么如过相减所得的数在a[i]的后面那么hash[2*a[i]-a[j]]==0;那么只要这个成立就可跳出，那么就有解。

哈哈，超时了这个复杂度基本上还是（n*n）；

后来看了一下别人的代码，我觉得复杂程度还是没降，可为啥就过了？

希望知道的能指导下;

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<stdlib.h>

 5 #include<string.h>

 6 #include<math.h>

 7 const int N=10005;

 8 using namespace std;

 9 int flag[N];//hash数组

10 int a[N];

11 int main(void)

12 {

13     int i,j,k,p,q,pp;

14     scanf("%d",&k);

15     while(k--)

16     {

17         memset(flag,0,sizeof(flag));

18         pp=0;

19         scanf("%d",&p);

20

21         for(i=1; i<=p; i++)

22         {

23             scanf("%d",&a[i]);

24             if(pp)

25             {

26                 continue;

27             }

28             flag[a[i]]=1;

29             if(i>=2)

30             {

31                 for(j=1; j<a[i]&&a[i]+j<=p; j++)

32                 {

33

34                     if(flag[j+a[i]]+flag[a[i]-j]==1)//找关于a[i]对称的也就是与a[i]的间距的数时否在a[i]的两端.

35                     {

36                         pp=1;

37                         break;

38                     }

39                 }

40             }

41

42         }//我认为上面的复杂度为（p+2）*p/4;我认为基本上还是p*p的，如过知道咋分析的教我一下

43         if(pp)

44         {

45             printf("Y\n");

46         }

47         else printf("N\n");

48

49     }

50     return 0;

51 }

巴特西

hdu-3833 YY's new problem(数组标记)

最新文章

热门文章