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掉
当然还可以用单调队列，悬线法什么的做，不过这道题的数据范围是真的小。
和之前在纪中培训的这道题有点像：餐桌数据范围还要小一点来着。
1 /* 2 ID: Starry21 3 LANG: C++ 4 TASK: range 5 */ 6 #include<iostream> 7 #include<string> 8 #include<cstdio> 9 #include<cstring> 10 #include<queue> 11 #include<algorithm> 12 #include<vector> 13 using namespace std; 14 #define N 255 15 #define ll long long 16 #define INF 0x3f3f3f3f 17 int n; 18 char s[N][N]; 19 int a[N][N]; 20 int ans[N]; 21 int main() 22 { 23 //freopen("range.in","r",stdin); 24 //freopen("range.out","w",stdout); 25 scanf("%d",&n); 26 for(int i=1;i<=n;i++) 27 { 28 scanf("%s",s[i]+1); 29 for(int j=1;j<=n;j++) 30 if(s[i][j]=='0') a[i][j]=-1; 31 } 32 for(int i=1;i<=n;i++) 33 if(a[1][i]!=-1) a[1][i]=1; 34 for(int i=2;i<=n;i++) 35 for(int j=1;j<=n;j++) 36 { 37 if(a[i][j]==-1) continue; 38 if(a[i-1][j]==-1) a[i][j]=1; 39 else a[i][j]=a[i-1][j]+1; 40 } 41 /*for(int i=1;i<=n;i++) 42 { 43 for(int j=1;j<=n;j++) 44 printf("%2d ",a[i][j]); 45 puts(""); 46 }*/ 47 for(int i=2;i<=n;i++) 48 for(int j=1;j<=n;j++) 49 if(a[i][j]>0) 50 { 51 int pos=j,m=INF; 52 while(a[i][pos]>0) 53 { 54 m=min(m,a[i][pos]); 55 if(pos-j+1>m) break; 56 ans[min(m,pos-j+1)]++; 57 //if(min(m,pos-j+1)==2) printf("%d %d %d\n",i,j,pos); 58 pos++; 59 } 60 } 61 for(int i=2;i<=n;i++) 62 if(ans[i]>0) 63 printf("%d %d\n",i,ans[i]); 64 return 0; 65 }Code 优质内容筛选与推荐>>
1、java 虚拟机 学习笔记 第二章 走进java
2、更加轻量级的控制器
3、判断是否是IE6的脚本
4、sql精点操作代码片段
5、CentOS6安装各种大数据软件 第一章：各个软件版本介绍