20pts萌新st表求助
  • 板块P2251 质量检测
  • 楼主LYqwq
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/10/13 21:04
  • 上次更新2023/10/27 07:38:53
查看原帖
20pts萌新st表求助
399116
LYqwq楼主2022/10/13 21:04
#include <iostream>
using namespace std;
template<typename T=int>
inline T read(){
    T X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+(ch^48),ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

template<typename T=int>
inline void write(T X){
    if(X<0) putchar('-'),X=~(X-1);
    T s[20],top=0;
    while(X) s[++top]=X%10,X/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    putchar('\n');
}

const int N=1e5+5,Log=35,log=30;
int n,m;
int a[N];
int lg[Log],f[N][Log];

void init(int *a,int n){
    lg[0]=-1;
    for(int i=1; i<=n; i++) f[i][0]=a[i],lg[i]=lg[i>>1]+1;
    for(int j=1; j<=log; j++)
        for(int i=1; i+(1<<j)-1<=n; i++)
            f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
}

int main(){
    n=read(),m=read();
    for(int i=1; i<=n; i++) a[i]=read();
    init(a,n);
    for(int l=1,r=m; r<=n; l++,r++){
        int x=lg[r-l+1];
        // printf("%d %d min(%d,%d): ",l,r,f[l][x],f[r-(1<<x)+1][x]);
        write(min(f[l][x],f[r-(1<<x)+1][x]));
    }
    return 0;
}

第一组数据错了:

1000 782
...

标准输出全部是 3535,这个代码输出 6,6,7,,7,8,,8,9,,9,35,,356,6,7,\dots,7,8,\dots,8,9,\dots,9,35,\dots,35 awa

2022/10/13 21:04
加载中...