讨论 / 408题,O(n^4)算法居然Accepted了……
飞雪天涯 2009-08-15 20:42:00
点我顶贴 收藏 删除
#include<iostream>

#include<string>

#define MAXN 200

#define MAXM 200

using namespace std;

bool map[MAXN][MAXM];

int square[MAXN][MAXM];

int main (void){

int n,m;cin>>m>>n;

string s;

for (int i=0;i<m;++i){

cin>>s;

for (int j=0;j<n;++j) map[i][j]=s[j]==’1’;

}

for (int i=0;i<m;++i)

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

if (!map[i][j]) square[i][j]=0;

else{

int k=0;

if (i>0&&j>0) k=square[i-1][j-1]-1;

k=max(k,2);

for (;k<=min(m-i,n-j);++k){

bool isok=true;

for (int y=j;y<j+k;++y){

if (!map[i+k-1][y]) {isok=false;break;}

}

if (!isok) break;

for (int x=i;x<i+k;++x){

if (!map[x][j+k-1]) {isok=false;break;}

}

if (!isok) break;

}

square[i][j]=k-1;

}

}

int p;cin>>p;

for (int i=0;i<p;++i){

int range;cin>>range;

if (range>n) cout<<"0";

else{

int place=0;

for (int j=0;j<m;++j)

for (int k=0;k<n;++k)

if (square[j][k]>=range) ++place;

cout<<place;

}

if (i!=p-1) cout<<endl;

}

return 0;

}

#1 vamos@2009-08-09 22:44:00
回复 删除
看来我的也可以AC
#2 飞雪天涯@2009-08-09 22:51:00
回复 删除
同喜同喜!
#3 hws_sheng@2009-08-09 23:22:00
回复 删除
不是吧

N^4也粗点吧

#4 hws_sheng@2009-08-09 23:24:00
回复 删除
#include<iostream>

using namespace std;

int H,W,Map[210][210],a[210];

int main()

{

memset(a,0,sizeof(a));

scanf("%d%d",&H,&W);

memset(Map,0,sizeof(Map));

char chr;

for (int i=1;i<=H;i++){

getchar();

for (int j=1;j<=W;j++){

scanf("%c",&chr);

Map[i][j]=Map[i-1][j]+Map[i][j-1]-Map[i-1][j-1];

if (chr==’1’)

Map[i][j]++;

}

}

for (int i=H;i>=1;i--)

for (int j=W;j>=1;j--)

if (Map[i][j]){

int d=min(i,j);

for (int k=d;k>=1;k--){

int s=Map[i][j]-Map[i-k][j]-Map[i][j-k]+Map[i-k][j-k];

if (s==k*k) a[k]++;

}

}

int t;scanf("%d",&t);

for (int i=1;i<=t;i++){

int x;scanf("%d",&x);

cout<<a[x]<<endl;

}

return 0;

}

#5 Havenking@2009-08-10 06:34:00
回复 删除
我也N^4

问标准算法..

#6 Havenking@2009-08-10 06:35:00
回复 删除
我也N^4

问标准算法..

#7 wx--168@2009-08-10 12:16:00
回复 删除
O(n^3)dp
#8 phoeagon@2009-08-10 12:42:00
回复 删除
当然是平方级啦
#9 phoeagon@2009-08-10 12:43:00
回复 删除
我搞错了,还要加一维枚举,三次方。
#10 canss@2009-08-10 14:47:00
回复 删除
七组到十组的数据是什么啊,为什么我全挂了
查看更多回复
提交回复