深入浅出疑似有误?
  • 板块P4147 玉蟾宫
  • 楼主Null_h
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/12 19:43
  • 上次更新2024/11/12 20:40:38
查看原帖
深入浅出疑似有误?
705712
Null_h楼主2024/11/12 19:43

此题深入浅出上的代码大致为:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1010;
int n,m;
char a[N][N];
int h[N][N],l[N][N],r[N][N],ans;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			h[i][j]=1;
			r[i][j]=l[i][j]=j;
		}
		for(int j=2;j<=m;j++){
			if(a[i][j]=='F'&&a[i][j-1]=='F')l[i][j]=l[i][j-1];
		}
		for(int j=m-1;j>=1;j--){
			if(a[i][j]=='F'&&a[i][j+1]=='F')r[i][j]=r[i][j+1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i!=1&&a[i][j]=='F'){
				if(a[i-1][j]=='F'){
					h[i][j]=h[i-1][j]+1;
					l[i][j]=max(l[i][j],l[i-1][j]);
					r[i][j]=min(r[i][j],r[i-1][j]);
				}
				ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]);
			}
		}
	}
	cout<<ans*3;
	return 0;
}

写法有细微差别。

用的悬线法,可以 AC,但是代码里为了防止越界对i=1的时候加了特判,而更新又是写在特判里的

所以无法处理有些 n=1 的数据:

1 2
F F

代码给出 0

应该这么写:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1010;
int n,m;
char a[N][N];
int h[N][N],l[N][N],r[N][N],ans;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			h[i][j]=1;
			r[i][j]=l[i][j]=j;
		}
		for(int j=2;j<=m;j++){
			if(a[i][j]=='F'&&a[i][j-1]=='F')l[i][j]=l[i][j-1];
		}
		for(int j=m-1;j>=1;j--){
			if(a[i][j]=='F'&&a[i][j+1]=='F')r[i][j]=r[i][j+1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i!=1&&a[i][j]=='F'){
				if(a[i-1][j]=='F'){
					h[i][j]=h[i-1][j]+1;
					l[i][j]=max(l[i][j],l[i-1][j]);
					r[i][j]=min(r[i][j],r[i-1][j]);
				}
			}
			if(a[i][j]=='F')ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]);
		}
	}
	cout<<ans*3;
	return 0;
}

如果是我自己眼瞎请告知一下。

2024/11/12 19:43
加载中...