[关闭]
@ysner 2018-08-03T19:07:38.000000Z 字数 1431 阅读 2312

小奇的数列

暴力 数论


题面

给定一个长度为的数列,以及次询问。每次询问在模意义下,中的最小区间和。

解析

或许是我看到的第道卡不动暴力的题。(均因为不好造数据,类比数字对

算法

枚举,用前缀和。
复杂度

算法

注意如果询问的序列长度大于,那么答案一定为
因为在极端情况下,长度为的区间中每个前缀和各不相同,覆盖了模的所有余数。
此时再加一个数,一定有前缀和相减得
特判即可。

暴力算法

在上面特判的基础上,我们可以优化一下枚举过程。
我们从前往后枚举区间。对枚到位置的区间前缀和,再从大到小枚举数字,如果数字在前面出现过就,统计这个能形成的最优答案。
同时如果
复杂度,但一点都不满,且难卡掉。(关键是这玩意儿跑得比正解快)

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=1e9+7,N=5e5+100;
  17. int n,m;
  18. ll a[N],ans,res[N];
  19. bool vis[505];
  20. il ll gi()
  21. {
  22. re ll x=0,t=1;
  23. re char ch=getchar();
  24. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  25. if(ch=='-') t=-1,ch=getchar();
  26. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  27. return x*t;
  28. }
  29. int main()
  30. {
  31. freopen("seq.in","r",stdin);
  32. freopen("seq.out","w",stdout);
  33. n=gi();m=gi();
  34. fp(i,1,n) a[i]=gi();
  35. while(m--)
  36. {
  37. re int l=gi(),r=gi(),p=gi();ll ans=1e18;
  38. if(r-l+1>p) {puts("0");continue;}
  39. res[l-1]=0;
  40. fp(i,1,p) vis[i]=0;vis[0]=1;
  41. fp(i,l,r)
  42. {
  43. res[i]=(res[i-1]+a[i])%p;
  44. fq(j,res[i],0) if(vis[j]) {ans=min(ans,res[i]-j);break;}
  45. if(!ans) break;
  46. vis[res[i]]=1;
  47. }
  48. printf("%lld\n",ans);
  49. }
  50. fclose(stdin);
  51. fclose(stdout);
  52. return 0;
  53. }

正解算法

需用平衡树寻找最小差值。
我连平衡树都不怎么会,懒得写了

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注