acgo题库
  • 首页
  • 题库
  • 题单
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情题解(1)讨论(0)提交记录(7)
  • ST算法秒了

    没想到居然击败了‮队团加不)ด้้童帅_者仇 的分块 这题是ST算法模版题,套模板即可。 ST算法:把数组分成长度为2的x次方的一些块,通过小块计算大块的数据,是一种离线算法。 不过这题可以用树状数组线段树做,会不会真的有人用树状数组和线段树这样的复杂算法做这题呢? #include <bits/stdc++.h> using namespace std; int n,m,a[100001],a2[100001][20],LOG[100001]; void st(){ LOG[0]=-1; for(int i=1;i<=100000;++i)LOG[i]=LOG[i>>1]+1; for(int i=1;i<=n;++i)a2[i][0]=a[i]; for(int i=1;i<=LOG[n];++i) for(int j=1;j+(1<<i)<=n+1;++j) a2[j][i]=min(a2[j][i-1],a2[j+(1<<(i-1))][i-1]); } int main(){ cin>>n>>m; for(int i=1;i<=n;++i)cin>>a[i]; st(); for(int i=1;i<=n;++i){ int l=i-m,r=i-1; if(l<=0)l=1; if(i==1){cout<<0<<endl;continue;} cout<<min(a2[l][LOG[r-l+1]],a2[r-(1<<LOG[r-l+1])+1][LOG[r-l+1]])<<endl; } return 0; }

    userId_undefined

    Xylophone

    荣耀黄金CSP-J一等奖
    11阅读
    0回复
    0点赞
首页