题解：P14209 [ROI 2016 Day2] 视频监控管理

首先观察到题目中的四个按钮操作其实就是将每行或每列轮换操作，并且

2 \le n, m \le 1000

的范围导致无法依次枚举所有操作的顺序，所以这题需要使用在处理轮换操作时经常用的倍长数组法。

倍长数组法就是指通过将数组长度扩为原来的

2

倍（或

2

倍减

1

）从而包括所有轮换的排列，例如：

原数组：

1,2,3,4,5

扩倍后：

其中红线为轮换后排列。

对于二维数组也是一样，只不过需要把横长度和竖长度都扩倍：

其中

\color{00bb00}A

表示原二维数组。（其实只用开到图中黑线就行了，因为从第

m+1

列到第

2m

列与从第

1

列到第

m

列保存的数据相同，少开一列省空间~~但没啥区别~~，每行也同理。）

接下来看怎么统计便于观察的方块数量。

这题要快速查询范围，因为我们要枚举每个格子的情况，已经要循环

n \times m \le 10^6

次了，为了不见到那个乌黑的 TLE, 我们对于每次循环都要用

O(1)

的复杂度查询。而这个特点恰好符合前缀和的特性，所以在这里使用类似二维前缀和的做法完成此题。

定义数组

s

：

s_{i,j}

表示以第

1

行第

1

列为左上角，以第

i

行第

j

列为右下角的矩阵中便于观察的方块组合的数量。

在预处理

s

数组时，对于

s_{i,j}

，判断以第

i-1

行第

j-1

列为左上角，以第

i

行第

j

列为右下角的矩阵是否是一个便于观察的方块组合，如果是则初始化为

1

，否则为

0

。

最终的答案为所有

n \le x < 2n,m \le y <2m

中下面式子的最大值，其实就是二维前缀和的模板：

s_{x,y}+s_{x-n+1,y-m+1}-s_{x-n+1,y}-s_{x,y-m+1}

Code:

CPP

#include <bits/stdc++.h>
using namespace std;
int n,m,a[2005][2005],s[2005][2005],maxx=-1;
char c;
void ctrl_cv(int x,int y,int f){//扩倍
	for(int i=1;i<=x;i++){
		for(int j=1;j<=y;j++){
			if(f==1)a[n+i][j]=a[i][j];//复制到下面
			if(f==2)a[i][m+j]=a[i][j];//复制到右面
			if(f==3)a[n+i][m+j]=a[i][j];//复制到右下面
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			if(c=='1')a[i][j]=1;
			else a[i][j]=2;
		}
	}
	ctrl_cv(n-1,m,1);//复制矩阵a，向下
	ctrl_cv(n,m-1,2);//复制矩阵a，向右
	ctrl_cv(n-1,m-1,3);//复制矩阵a，向右下
	for(int i=2;i<2*n;i++){
		for(int j=2;j<2*m;j++){
			if((a[i-1][j-1]==a[i-1][j])&&(a[i-1][j-1]==a[i][j-1])&&(a[i][j-1]==a[i][j])&&(a[i-1][j]==a[i][j])){
				s[i][j]=1;
			}
		}
	}
    //更新s数组
	for(int i=2;i<2*n;i++){
		for(int j=2;j<2*m;j++){
			s[i][j]+=s[i][j-1];
		}
	}
	for(int i=2;i<2*n;i++){
		for(int j=2;j<2*m;j++){
			s[i][j]+=s[i-1][j];
		}
	}
	for(int i=n;i<2*n;i++){
		for(int j=m;j<2*m;j++){
			maxx=max(maxx,s[i][j]+s[i-n+1][j-m+1]-s[i-n+1][j]-s[i][j-m+1]);//取答案
		}
	}
	cout<<maxx;
	return 0;
}
//矩阵可以复制，代码不能复制！--by Ace2012

题解：P14209 [ROI 2016 Day2] 视频监控管理

文章操作

Code:

相关推荐

评论

题解：P14209 [ROI 2016 Day2] 视频监控管理