刷题记录:牛客NC20471[ZJOI2007]棋盘制作

传送门:牛客

题目描述:

国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。
据说国际象棋起源 于易经的思想，棋盘是一个8*8大小的黑白相间的方阵，对应八八六十四卦，黑白对应
阴阳。
而我们的主人公小Q， 正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规
则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。
小Q找到了一张由N*M个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小Q想在这
种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。
不过小Q还没有决定是找 一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相
间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决
定哪个更好一些。于是小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？
输入:
3 3
1 0 1
0 1 0
1 0 0
输出:
4
6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

牛客网四星题,感觉思维难度挺大的.正解不易想到.但是掌握套路之后并不是一道难懂的题

主要思路:

1. 首先对于我们的每一个点,我们都可以先预处理出该点往左往右的最大的合法矩形的位置,使用$max\_left和max\_right数组来存储$,并且我们是可以向上扩展的,因此我可以使用$up\_length数组$来记录我们的这个点向上扩展的长度.
2. 然后每一次都比较该行和上一行的左右扩展程度,取一个重叠的位置,进行操作

emmm,对于此题文字不易描述,重点将在代码中注释

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,m;int max_left[2010][2010],max_right[2010][2010];
int up_lenght[2010][2010];int mp[2010][2010];
int main() {
	n=read();m=read();
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			mp[i][j]=read();
			//进行左右以及上方的初始化,显然左右扩展最小也是自己
			max_left[i][j]=j;max_right[i][j]=j;up_lenght[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=2;j<=m;j++) {
			if(mp[i][j]!=mp[i][j-1]) {
			//预处理左边的
				max_left[i][j]=max_left[i][j-1];
			}    
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=m-1;j>=1;j--) {
			if(mp[i][j]!=mp[i][j+1]) {
			//预处理右边的
				max_right[i][j]=max_right[i][j+1];
			}
		}
	}
	int ans1=-inf,ans2=-inf;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
		//此处我们发现i=1时显然是没有上一行的,但是我们是不能不记录第一行的值的
		//因为我们的最大贡献可能就是第一行,所以我们应该判断一下
			if(mp[i][j]!=mp[i-1][j]&&i>1) {
			//相对于左边,取max,相对于右边,则应该取min,感觉迷糊自己画一下
				max_left[i][j]=max(max_left[i][j],max_left[i-1][j]);
				max_right[i][j]=min(max_right[i][j],max_right[i-1][j]);
				//扩展我们的上方长度
				up_lenght[i][j]+=up_lenght[i-1][j];
			}
			//len代表水平的长度,因为是正方形,我们的边长应该取长宽较小的
			int len=max_right[i][j]-max_left[i][j]+1;
			ans1=max(ans1,min(len,up_lenght[i][j])*min(len,up_lenght[i][j]));
			ans2=max(ans2,len*up_lenght[i][j]);
		}
	}
	cout<<ans1<<endl<<ans2<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

注意,假设有人看完了本代码,觉得有一些问题,因为我们进行记录每一个矩形的长宽直接是取最小的,比如下图

假设使用我们上述的算法的话遇到我们此时的j位置就是直接记录了红色矩形的面积,但是此时我们的黑色区间才是最大的,难道是算法错了??

但是此时我们想一下,我们的j位置的右边的位置和右边的上方的位置肯定相同的.如下图

因此此时我们其实是可以靠j位置的左边和右边记录我们的黑色矩形的值的