专栏文章

题解：P11503 [NordicOI 2018] Nordic Camping

NNazq
P11503题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio1itdf
此快照首次捕获于
2025/12/02 11:50
3 个月前
此快照最后确认于
2025/12/02 11:50
3 个月前
查看原文
预处理每个位置的答案。 枚举正方形右下角，二分出长度。 然后矩形取 max⁡\max。 可以树套树，两个 log。离线后，变为一个 log。
由于是正方形，性质远比普通矩形多。
我可以先求左边界覆盖这个点的最大矩形，这个用单调队列求解。
再求覆盖这个点的最大矩形，也用单调队列求解。
瓶颈在于预处理以每个位置为右下角的最大正方形边长，设为 szi,jsz_{i, j}。
障碍位置 szi,j=0sz_{i, j} = 0，非障碍位置 szi,j=min⁡(szi−1,j,szi,j−1,szi−1,j−1)+1sz_{i, j} = \min(sz_{i-1, j}, sz_{i, j - 1}, sz_{i - 1, j - 1}) + 1。
O(n2)O(n^2)
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, l, r) for(int i = (l); i <= (r); ++i)
#define per(i, r, l) for(int i = (r); i >= (l); --i)
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N = 2005, Q = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m, q, sum[N][N], sz[N][N];
int SUM(int x0, int y0, int x1, int y1) {
    return sum[x1][y1] - sum[x0 - 1][y1] - sum[x1][y0 - 1] + sum[x0 - 1][y0 - 1];
}
char s[N][N];

int tmp[N][N], ans[N][N];
int que[N], head, tail;

int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    cin >> n >> m;
    rep(i, 1, n)cin >> (s[i] + 1);
    rep(i, 1, n) rep(j, 1, m) {
        sum[i][j] = (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (s[i][j] == '#'));
    }
    rep(i, 1, n) rep(j, 1, m) {
        if(s[i][j] == '#') {
            continue;
        }
        int &len = sz[i][j];
        len = min({sz[i - 1][j], sz[i][j - 1], sz[i - 1][j - 1]}) + 1;
    }

    rep(i, 1, n) {
        head = 1, tail = 0;
        per(j, m, 1) if(s[i][j] == '.') {
//            if(head > tail || j - sz[i][j] + 1 < que[head] - sz[i][que[head]] + 1) {
                while(head <= tail && sz[i][que[tail]] <= sz[i][j])tail--;
                que[++tail] = j;
//            }
            while(head <= tail && que[head] - sz[i][que[head]] + 1 > j) head++;
            tmp[i][j] = sz[i][que[head]];
        }
    }

    rep(j, 1, m) {
        head = 1, tail = 0;
        per(i, n, 1) if(s[i][j] == '.') {
//            if(head > tail || i - tmp[i][j] + 1 < que[head] - tmp[que[head]][j] + 1) {
                while(head <= tail && tmp[que[tail]][j] <= tmp[i][j])tail--;
                que[++tail] = i;
//            }
            while(head <= tail && que[head] - tmp[que[head]][j] + 1 > i)head++;
            ans[i][j] = tmp[que[head]][j];
        }
    }


    cin >> q;
    rep(i, 1, q) {
        int x, y;
        cin >> x >> y;
        cout << ans[x][y] * ans[x][y] << '\n';
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...