9.22-白红宇

9.22

阅读量：6432 次

发布时间：2019-06-23

本文共 2300 字，大约阅读时间需要 7 分钟。

100+30+70=200

T1水题，单调队列

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 2005using namespace std;int n,m,ans,a[N],f[N][N],l[N],r[N],q[N];int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++){        for(int j=1;j<=m;j++)scanf("%d",&a[j]);        for(int j=m;j>=1;j--)f[i][j]=a[j]?f[i][j+1]+1:0;    }    for(int i=1,j,top;i<=m;i++){        for(j=1,top=0;j<=n;j++){            while(top>0&&f[q[top]][i]>=f[j][i])top--;            l[j]=q[top]; q[++top]=j;        }        for(j=n,top=0,q[0]=n+1;j>=1;j--){            while(top>0&&f[q[top]][i]>=f[j][i])top--;            r[j]=q[top]; q[++top]=j;        }        for(j=1;j<=n;j++)            ans=max(ans,min(r[j]-l[j]-1,f[j][i]));    }    printf("%d\n",ans);    return 0;}

T2标程，数据都是错的，其实A了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define LL long longusing namespace std;struct data{    LL x,y;    bool operator < (const data &a)const{        if(x==a.x)return y
          
           =1;i--){ f[i]=1; for(int j=n;j>i;j--)if(c[j]

T3,莫队+O3+快读卡过。。

正解只按左端点排序，又是根号算法。。。

#pragma GCC optimize ("O3")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 1000050using namespace std;int be[N],n,m,nn,a[N],f[N];struct QQ{    int l,r,id;}qu[N];bool cmp1(QQ a,QQ b){    if(be[a.l]!=be[b.l])return be[a.l]
          
           qu[i].r){ --num[a[r]]; if(num[a[r]]==a[r])++sum; if(num[a[r]]==a[r]-1)--sum; --r; } while(l
           
            qu[i].l){ --l;++num[a[l]]; if(num[a[l]]==a[l])++sum; if(num[a[l]]==a[l]+1)--sum; } f[qu[i].id]=sum; }}int read(){ int a=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){a=a*10+(ch^48);ch=getchar();} return a;}int main(){ //freopen("test.in","r",stdin); //freopen("my.out","w",stdout); n=read(); m=read(); //nn=(int)sqrt(n); nn=2000; for(int i=1;i<=n;i++){ a[i]=read(); be[i]=(i-1)/nn+1; } for(int i=1;i<=m;i++){ qu[i].l=read();qu[i].r=read(); qu[i].id=i; } sort(qu+1,qu+m+1,cmp1); work(); for(int i=1;i<=m;i++) printf("%d\n",f[i]); return 0;}