题解：P11752 [COCI 2024/2025 #5] 挂画 / Zid

niuniudundun · 2025-02-19 21:37:01 · 题解

题目传送门

upd 2025/3/5：关于 38 号数据，改一个 . 变成 #，导致做法卡掉，可以将代码中 s[n][m]==0 换成 s[n][m]<=1 即可。

题目大意

一个 n 行 m 列的 c 中，有多少个矩形使得 # 数量 \le 1。

题目解法

暴力 O(n^3m^3) 显然不能过。

一眼的前缀和（不会搜百度）。

思路如下：

如果 c_{i,j} 是 # 则令 s_{i,j}=1。随后再跑一遍 s，让 s_{i,j} 加上以 (i,j) 为左下角的矩阵和 s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}。然后使用四重循环计算 (x_1,y_1) 到 (x_2,y_2) 的和：s_{x_2,y_2}-s_{x_1-1,y_2}-s_{x_2,y_1-1}+s_{x_1-1,y_{1}-1}，如果和 \le 1 则答案 ans 加一。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=501;
int n,m;
int s[maxn][maxn];
int ans;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            cin>>c;
            if(c=='#'){
                s[i][j]++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
        }
    }
    for(int x1=1;x1<=n;x1++){
        for(int y1=1;y1<=m;y1++){
            for(int x2=x1;x2<=n;x2++){
                for(int y2=y1;y2<=m;y2++){
                    int sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
                    if(sum==1||sum==0){
                        ans++;
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
3 3
...
...
..#
*/

然后你就得了 38 分，link。

复杂度有 O(nm+n^2m^2)，对于 5\times 10^2 的数据显然不行。

考虑优化。可以优化的有：

将单独跑 s 的与上面合并，减少 O(nm) 复杂度。
如果 (x_1,y_1) 到 (x_2,y_2) 和大于一，那么 (x_1,y_1) 到 (x_2,y_2+1)、(x_1,y_1) 到 (x_2,y_2+2)、(x_1,y_1) 到 (x_2,y_2+3) 等也大于一，可以结束循环，剪枝。

得到：

#include<bits/stdc++.h>
using namespace std;
const int maxn=501;
int n,m;
int s[maxn][maxn];
int ans;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            cin>>c;
            if(c=='#'){
                s[i][j]++;
            }
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
        }
    }   
    for(int x1=1;x1<=n;x1++){
        for(int y1=1;y1<=m;y1++){
            for(int x2=x1;x2<=n;x2++){
                for(int y2=y1;y2<=m;y2++){
                    int sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
                    if(sum==1||sum==0){
                        ans++;
                    }else{
                        break;
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
3 3
...
...
..#
*/

可以得到 38 的分数，只 TLE 一个点，link。

然后寄出一招——卡常小技巧：

在变量前加 register。
cin、cout 改 scanf、printf。
去掉多余变量。

然后得到：

#include<bits/stdc++.h>
using namespace std;
const int maxn=501;
int n,m;
int s[maxn][maxn];
int ans;
signed main(){
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=m;j++){
            char c;
            cin>>c;
            if(c=='#'){
                s[i][j]++;
            }
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
        }
    }   
    for(register int x1=1;x1<=n;x1++){
        for(register int y1=1;y1<=m;y1++){
            for(register int x2=x1;x2<=n;x2++){
                for(register int y2=y1;y2<=m;y2++){
                    if(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<=1){
                        ans++;
                    }else{
                        break;
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}
/*
3 3
...
...
..#
*/

可是问题没有解决，link。

当下载了数据点 #38 你会发现 500\times 500 个 .，上面做法会被卡成 O(n^2m^2)。

可以加一个特判 s_{n,m}=0 时，说明没有一个 .，可以动用数学：

我们可以将这个问题转成：

在一个 n\times m 的矩阵中有多少个子矩阵。

一个矩阵由左上角和右下角组成，枚举左上角有 nm 个情况，右下角有 (n+1)(m+1) 个情况，随后再抛出重复的矩阵 {\div}4，然后就是正确答案 \dfrac{nm(n+1)(m+1)}{4} 。具体的可以自己推一推。

总 AC 代码

#include<bits/stdc++.h>
using namespace std;
const long long maxn=501;
long long n,m,s[maxn][maxn],ans;
signed main(){
    scanf("%lld%lld",&n,&m);
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=m;j++){
            char c;
            cin>>c;
            if(c=='#'){
                s[i][j]++;
            }
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
        }
    }
    if(s[n][m]==0){
        printf("%lld",n*m*(n+1)*(m+1)/4);
        return 0;
    }
    for(register int x1=1;x1<=n;x1++){
        for(register int y1=1;y1<=m;y1++){
            for(register int x2=x1;x2<=n;x2++){
                for(register int y2=y1;y2<=m;y2++){
                    if(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<=1){
                        ans++;
                    }else{
                        break;
                    }
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}
/*
3 3
...
...
..#
*/