记录编号	75094	评测结果	AAAAAAA
题目名称	[USACO]家的范围	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2013-10-27 09:56:54	内存使用	0.62 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<deque>
#include<cstring>
#include<cstdlib>
using namespace std;
const int SIZEN=251;
const int INF=0x7fffffff;
int n;//土地边长
bool board[SIZEN][SIZEN]={0};
int line_after[SIZEN][SIZEN]={0};//line_after[i][j]表示[i][j]及右面有多少个连着的1
void read(void){
	scanf("%d",&n);
	int i,j;
	char ch;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			cin>>ch;
			board[i][j]=(ch=='0'?0:1);
		}
	}
}
void getline(bool s[],int d[]){
	int i=1,j=1;//i始终的位置是"1的"
	int len;
	while(true){
		while(s[j]&&j<=n) j++;
		len=j-i;
		while(i<j){
			d[i]=j-i,i++;
		}
		if(j>n) break;
		while(!s[j]&&j<=n) d[j]=0,j++;
		i=j;
		if(j>n) break;
	}
}
void getline(void){
	int i;
	for(i=1;i<=n;i++) getline(board[i],line_after[i]);
}
class MNQ{//这个是"最小型"的单调队列
public:
	deque<pair<int,int> > s;//first是数据,second是位置
	MNQ(){s.clear();}
	void push_back(int x,int pos){
		while(s.size()&&x<=s.back().first) s.pop_back();
		s.push_back(make_pair(x,pos));
	}
	void erase(int pos){
		if(s.empty()) return;
		if(s.front().second==pos) s.pop_front();
	}
	int minima(void){
		if(s.empty()) return INF;
		return s.front().first;
	}
};
int ans[SIZEN]={0};
void dealrow(int x){//第x列
	MNQ Q;
	int i=1,j=0;
	for(i=1;i<=n;i++){
		while(j+1<=n&&Q.minima()>=j-i+2&&line_after[j+1][x]>=j-i+2) j++,Q.push_back(line_after[j][x],j);
		ans[j-i+1]++;
		Q.erase(i);
		if(j<i) j=i;
	}
}
void dealrow(void){
	int i;
	for(i=1;i<=n;i++) dealrow(i);
	for(i=n-1;i>=2;i--) ans[i]+=ans[i+1];
	//此时ans中存储的是"<=i的各有几个"
}
void work(void){
	getline();
	dealrow();
	int i;
	for(i=2;i<=n;i++){
		if(ans[i]){
			printf("%d %d\n",i,ans[i]);
		}
	}
}
int main(){
	freopen("range.in","r",stdin);
	freopen("range.out","w",stdout);
	read();
	work();
	return 0;
}