[关闭]
@ysner 2018-05-19T09:05:11.000000Z 字数 1703 阅读 1589

数字对

暴力


题面

她的面前浮现出一个长度为的序列,她想找出一段区间()。
这个特殊区间满足,存在一个(),并且对于任意的(),都能被整除。这样的一个特殊区间价值为
想知道序列中所有特殊区间的最大价值是多少,而有多少个这样的区间呢?这些
区间又分别是哪些呢?

解析

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define max(a,b) (a>b?a:b)
  11. #define min(a,b) (a<b?a:b)
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=5e5+100;
  16. int n,a[N],l,r,tot,ans=0,sol[N],cnt,now;
  17. bool vis[N];
  18. il int gi()
  19. {
  20. re int x=0,t=1;
  21. re char ch=getchar();
  22. while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  23. if(ch=='-') t=-1,ch=getchar();
  24. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25. return x*t;
  26. }
  27. il void wri(re int x)
  28. {
  29. if(x<0) putchar('-'),x=-x;
  30. if(x>9) wri(x/10);
  31. putchar(x%10+'0');
  32. }
  33. il void work(re int i)
  34. {
  35. if(vis[i]) return;vis[i]=1;
  36. l=r=i;
  37. while(l>1)
  38. {
  39. l--;
  40. if(a[l]%a[i]!=0) {l++;break;}
  41. else vis[l]=1;
  42. }
  43. while(r<n)
  44. {
  45. r++;
  46. if(a[r]%a[i]!=0) {r--;break;}
  47. else vis[r]=1;
  48. }
  49. if(ans<r-l) ans=r-l,sol[tot=1]=l;
  50. else if(ans==r-l) sol[++tot]=l;
  51. }
  52. int main()
  53. {
  54. freopen("pair.in","r",stdin);
  55. freopen("pair.out","w",stdout);
  56. n=gi();
  57. tot=n;fp(i,1,n) sol[i]=i;
  58. fp(i,1,n) a[i]=gi();
  59. if(n>3000)
  60. {
  61. re int gaoshi=min((1e8/n),(n+100));
  62. fp(i,1,gaoshi-1) work(n/gaoshi*i);
  63. }
  64. fp(i,1,n) work(i);
  65. sort(sol+1,sol+1+tot);re int ysn=0;//printf("%d\n",tot);
  66. fp(i,1,tot) if(sol[i]==sol[i-1]) ysn++;
  67. printf("%d %d\n",tot-ysn,ans);
  68. fp(i,1,tot) if(sol[i]!=sol[i-1]) printf("%d ",sol[i]);
  69. printf("\n");
  70. fclose(stdin);
  71. fclose(stdout);
  72. return 0;
  73. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注