洛谷 P1169 [ZJOI2007]棋盘制作

喜欢ヅ旅行 2023-08-17 17:49 144阅读 0赞

### 题意 ###

给定一个n\*m的01矩阵，寻找最大的，相邻值不相同的子矩阵与子方阵。

\\(n,m\\leq 2,000\\)

### 分析 ###

朴素的做法是枚举两个点来确定矩阵，再暴力判断能不能满足条件。

复杂度\\(O(n^4)\\)爆炸。考虑优化：判断能不能满足条件时，存在很多重复判断，可以预处理。

但是，怎样进行预处理呢？这就需要我们改变枚举方式，简化预处理的步骤。

### 悬线法 ###

今年应该不考

是一种DP(?)算法，常用于求满足条件的矩阵。

![1508659-20190831123833014-577394041.png][]

如果将一条线当做1\*k的矩阵看待，则我们枚举每一条满足条件的线，并尝试将其向左右拓展构造矩阵。

![1508659-20190831123846879-2051647038.png][]

那么只要在左右拓展长度中分别取min，就是所求答案。这种方法的复杂度是多少？

每个点如果和上方不同，就可以接到上面的线中。所以枚举每个点，就可以递推求出悬线up

\\\[up\_\{i,j\}=up\_\{i-1,j\}+(b\_\{i,j\}\\not= b\_\{i,j\})\\\]

其中b是原始矩阵，初始值是1。复杂度\\(O(n^2)\\)

左右端拓展的对象是单个点，所以对于每个点都预处理出能向左右拓展到的位置。用递推求出。

\\\[\\begin\{cases\}b\_\{i,j\}\\not=b\_\{i,j-1\}\\quad left\_\{i,j\}=j\\\\b\_\{i,j\}=b\_\{i,j-1\}\\quad left\_\{i,j\}=left\_\{i,j-1\}\\end\{cases\}\\\]

\\\[\\begin\{cases\}b\_\{i,j\}\\not=b\_\{i,j+1\}\\quad right\_\{i,j\}=j\\\\b\_\{i,j\}=b\_\{i,j+1\}\\quad right\_\{i,j\}=right\_\{i,j+1\}\\end\{cases\}\\\]

复杂度仍然\\(O(n^2)\\)

2k可过。

### 正确性 ###

我们需要证明的是，悬线法可以枚举到所有矩形。

![1508659-20190831123900118-656152493.png][]

假设我们要在这一团满足条件的联通块中找矩形。（丑，真TM丑）

![1508659-20190831123913512-1855620603.png][]

那么它会不会取蓝色呢？不会，很明显绿色比他更优。有一个性质：**矩形边缘必然紧贴联通块边缘**。

所以对于每条悬线，它取到的矩阵是尽量大的。

（其实绿色也不满足，因为左右端没有取完整。）

![1508659-20190831123923976-1885712155.png][]

画图宝才，luogu捡到鬼了

由刚才的性质得出，这个矩形所在的联通块即便边缘再粗糙，总是会有一条悬线的上端和矩形的上端重合。

所以，只要每条悬线都枚举到，每个可能是答案的矩形就会枚举到，而且会让它们尽量大。这题就解决了。

### 代码 ###

别看了 抄的

#include<cstdio>//iostream库有left函数，会冲突 #include<algorithm> using namespace std; const int MAXN=2005; int n,m; bool b[MAXN][MAXN]; int left[MAXN][MAXN],right[MAXN][MAXN],up[MAXN][MAXN]; int sq,rect,temp; int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) left[i][j]=right[i][j]=j,up[i][j]=1,scanf("%d",&b[i][j]); //输入、初始化 for(int i=1;i<=n;i++) for(int j=2;j<=m;j++) if(b[i][j]!=b[i][j-1]) left[i][j]=left[i][j-1]; for(int i=1;i<=n;i++) for(int j=m-1;j>=1;j--) if(b[i][j]!=b[i][j+1]) right[i][j]=right[i][j+1]; //递推预处理，注意范围和顺序 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(i>1&&b[i-1][j]!=b[i][j]) { up[i][j]=up[i-1][j]+1; left[i][j]=max(left[i][j],left[i-1][j]); right[i][j]=min(right[i][j],right[i-1][j]); //由于是矩形，left和right不能越界，要取一遍最小值 //另外看清楚存储的是位置不是距离，所以左端取距离更短相当于位置更靠后，下标更大。 } temp=(right[i][j]-left[i][j]+1); rect=max(rect,up[i][j]*temp); sq=max(sq,min(up[i][j],temp)*min(up[i][j],temp)); //正方形同理。 } printf("%d\n%d\n",sq,rect); return 0; }

最后，祝大家身体健康，再见。

转载于:https://www.cnblogs.com/ehznehc/p/11438592.html

[1508659-20190831123833014-577394041.png]: /images/20230808/72ba490c52904facb1bad28940d1f12a.png
[1508659-20190831123846879-2051647038.png]: /images/20230808/9be9e08dc0bc4c42ae70b745797b56a9.png
[1508659-20190831123900118-656152493.png]: /images/20230808/dbdc7a0c1319489fa9be7ac4578d3d29.png
[1508659-20190831123913512-1855620603.png]: /images/20230808/5e465ea530f14cc0a83573fc15efa056.png
[1508659-20190831123923976-1885712155.png]: /images/20230808/f69b9d67afc749498f0b25c9cef4bb35.png