首页 > 代码库 > [51nod1291]Farmer

[51nod1291]Farmer

2024-08-16 02:47:45   244人阅读

　　用单调栈的话不严格的O(n^3)可以轻松艹过去，统计的时候要差分。

　　可以发现，对于一个单调栈里的元素，从它进栈到出栈都会重复类似的计算。。再差分一波后就可以只在出栈的时候计算一下了。

　　具体的话看代码吧。。

 

O(n^3):

技术分享
 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define ll long long 7 #define ui unsigned int 8 #define ull unsigned long long 9 using namespace std;10 const int maxn=606;11 char s[maxn];12 int h[maxn],st[maxn],l[maxn];13 int an[maxn][maxn];14 int i,j,k,n,m;15 16 int ra,fh;char rx;17 inline int read(){18     rx=getchar(),ra=0,fh=1;19     while((rx<‘0‘||rx>‘9‘)&&rx!=‘-‘)rx=getchar();20     if(rx==‘-‘)fh=-1,rx=getchar();21     while(rx>=‘0‘&&rx<=‘9‘)ra*=10,ra+=rx-48,rx=getchar();return ra*fh;22 }23 inline void add(int y1,int x2,int y2){24 //    printf("add:1,%d  %d,%d\n",y1,x2,y2);25     an[x2][y2]++,an[x2][y1-1]--;26 }27 inline void addall(int len,int st2,int h){28     for(register int i=1;i<=len;i++)an[h][i+st2]++,an[h][i-1]--;29 //    add(i,h,i+st2);30 //    an[h][1+st2]++,an[h][len+st2+1]--,31 //    an[h][0]--,an[h][len]++;32 }33 34 char ss[10];int len;35 inline void outx(int x){36     if(!x){putchar(‘0‘);return;}37     while(x)ss[len++]=x%10,x/=10;38     while(len)putchar(ss[--len]+48);39 }40 int main(){41     n=read(),m=read();//register int k;42     for(i=1;i<=n;i++){43         scanf("%s",s+1);44         int top=0;45         for(j=1;j<=m+1;j++){46             h[j]=s[j]==‘1‘?h[j]+1:0;47             while(top&&h[st[top]]>=h[j])addall(j-st[top],st[top]-l[top],h[st[top]]),top--;48             st[++top]=j,l[top]=st[top-1]+1;49             //for(k=1;k<=top;k++)add(j-st[k]+1,h[st[k]],j-l[k]+1);50         }51     }52 //    for(i=1;i<=n;i++)for(j=1;j<=m;j++)an[i][j]+=an[i][j-1];53 //    for(i=1;i<=n;printf("%d\n",an[i][m]),i++)for(j=1;j<m;j++)printf("%d ",an[i][j]);54     for(i=n;i;i--)for(j=m;j;j--)an[i][j]+=an[i+1][j]+an[i][j+1]-an[i+1][j+1];55     for(i=1;i<=n;outx(an[i][m]),putchar(‘\n‘),i++)for(j=1;j<m;j++)outx(an[i][j]),putchar(‘ ‘);56 }
View Code

O(n^2):

技术分享
 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define ll long long 7 #define ui unsigned int 8 #define ull unsigned long long 9 using namespace std;10 const int maxn=606;11 char s[maxn];12 int h[maxn],st[maxn],l[maxn];13 int an[maxn][maxn];14 int i,j,k,n,m;15 16 int ra,fh;char rx;17 inline int read(){18     rx=getchar(),ra=0,fh=1;19     while((rx<‘0‘||rx>‘9‘)&&rx!=‘-‘)rx=getchar();20     if(rx==‘-‘)fh=-1,rx=getchar();21     while(rx>=‘0‘&&rx<=‘9‘)ra*=10,ra+=rx-48,rx=getchar();return ra*fh;22 }23 24 inline void addall(int len,int st2,int h){25     an[h][1+st2]++,an[h][len+st2+1]--,26     an[h][0]--,an[h][len]++;27 }28 29 char ss[10];int len;30 inline void outx(int x){31     if(!x){putchar(‘0‘);return;}32     while(x)ss[len++]=x%10,x/=10;33     while(len)putchar(ss[--len]+48);34 }35 int main(){36     n=read(),m=read();register int i,j;37     for(i=1;i<=n;i++){38         scanf("%s",s+1);39         int top=0;40         for(j=1;j<=m+1;j++){41             h[j]=s[j]==‘1‘?h[j]+1:0;42             while(top&&h[st[top]]>=h[j])addall(j-st[top],st[top]-l[top],h[st[top]]),top--;43             st[++top]=j,l[top]=st[top-1]+1;44         }45     }46     for(i=1;i<=n;i++)for(j=1;j<=m;j++)an[i][j]+=an[i][j-1];47     for(i=1;i<=n;i++)an[i][m+1]=0;for(i=1;i<=m;i++)an[n+1][i]=0;48     for(i=n;i;i--)for(j=m;j;j--)an[i][j]+=an[i+1][j]+an[i][j+1]-an[i+1][j+1];49     for(i=1;i<=n;outx(an[i][m]),putchar(‘\n‘),i++)for(j=1;j<m;j++)outx(an[i][j]),putchar(‘ ‘);50 }
View Code

 

[51nod1291]Farmer


联系
我们