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

nekoboy · 2025-02-19 18:43:09 · 题解

更好的阅读体验（无耻）。

思路

为了快速求出一直左上端点和右下端点已知的矩形含有的钉子数，采用二维前缀和，预处理前缀和数组，快速计算任意矩形区域内的钉子数量。

滑动窗口的思想，对于每一行，固定上下边界，通过滑动左右边界来快速计算满足条件的矩形数量。

在滑动窗口时，利用双指针优化，从 O(n^2m^2) 降低到 O(n^2m)。

代码

#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast", "-funroll-all-loops")
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

#define y1 kairiki
#define x first
#define y second

#define repeat(x, a, b) for(int x = a; x <= b; x ++)
#define rpless(x, a, b) for(int x = a; x >= b; x --)
#define repeatl(x, a, b) for(int x = a; x < b; x ++)
#define rplessr(x, a, b) for(int x = a; x > b; x --)

using namespace std;

const int N = 505;
int n, m, sum[N][N];
string a[N]; 

int main()
{
    ios::sync_with_stdio(false); 
    cin.tie(nullptr); 

    cin >> n >> m;
    repeatl(i, 0, n) { cin >> a[i]; }

    repeat(i, 1, n)  repeat(j, 1, m) 
    { sum[i][j] = sum[i - 1][j] + 
        sum[i][j - 1] - sum[i - 1][j - 1] + 
        (a[i - 1][j - 1] == '#'); }

    long long ans = 0;

    // 枚举上下边界
    repeat(u, 1, n) repeat(d, u, n) {
        int l = 1, r = 1;

        // 双指针法处理左右边界
        while (r <= m) {
            int cnt = sum[d][r] - sum[u - 1][r] - sum[d][l - 1] + sum[u - 1][l - 1];

            if (cnt <= 1) {
                ans += (r - l + 1); 
                r++;
            } else {
                l++;

                if (l > r) { r = l; }
            }
        }
    }

    cout << ans << endl;

    return 0;
}