USACO3.3 Home on the Range【思维】

做完之后看到题解里面很多bfs,dfs,甚至还有dp?

写了一个不知道怎么称呼它的方法，暂且叫他乱搞吧。用数组a[][]预处理出以当前行作为最底层，这一列从上往下的最长的1的长度。如果这个格子为0的话，a[i][j]就是0，当然也可以特殊标记一下（比如我就用的-1）统计答案的时候，就枚举每个非0的格子作为最底层第一个格子依次往右边拓展，记录途中最短的从上往下1的长度。由于是正方形，能构成的正方形的边长为min(pos-j+1,m)min(pos−j+1,m)（见代码）。当纵向延伸的长度大于途中最短的从上往下1的长度时，后面就已经不能再构成正方形了，就可以break掉

当然还可以用单调队列，悬线法什么的做，不过这道题的数据范围是真的小。

和之前在纪中培训的这道题有点像：餐桌数据范围还要小一点来着。

 /*

 ID: Starry21

 LANG: C++

 TASK: range

 */

 #include<iostream>

 #include<string>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 #include<vector>

 using namespace std;

 #define N 255

 #define ll long long

 #define INF 0x3f3f3f3f

 int n;

 char s[N][N];

 int a[N][N];

 int ans[N];

 int main()

 {

     //freopen("range.in","r",stdin);

     //freopen("range.out","w",stdout);

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         scanf("%s",s[i]+);

         for(int j=;j<=n;j++)

             if(s[i][j]=='') a[i][j]=-;

     }

     for(int i=;i<=n;i++)

         if(a[][i]!=-) a[][i]=;

     for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

         {

             if(a[i][j]==-) continue;

             if(a[i-][j]==-) a[i][j]=;

             else a[i][j]=a[i-][j]+;

         }

     /*for(int i=1;i<=n;i++)

     {

         for(int j=1;j<=n;j++)

             printf("%2d ",a[i][j]);

         puts("");

     }*/

     for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

             if(a[i][j]>)

             {

                 int pos=j,m=INF;

                 while(a[i][pos]>)

                 {

                     m=min(m,a[i][pos]);

                     if(pos-j+>m) break;

                     ans[min(m,pos-j+)]++;

                     //if(min(m,pos-j+1)==2) printf("%d %d %d\n",i,j,pos);

                     pos++;

                 }

             }

     for(int i=;i<=n;i++)

         if(ans[i]>)

             printf("%d %d\n",i,ans[i]);

     return ;

 }

Code

巴特西

USACO3.3 Home on the Range【思维】

最新文章

热门文章