题解：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:

#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