AT_joisc2017_a 開拓 (Cultivation)

_LPF_ · 2022-11-15 08:19:48 · 题解

「JOISC 2017 Day 1」开荒者

• 给定 r\times c 的网格，其中 n 个点初始长了草，之后每一天，可以钦定所有草同时向 上/下/左/右 扩展一格。
• 求最少多少天可以使整个网格被草覆盖。

这题还是很厉害的。

• 性质一：草的扩展结果与操作顺序无关。因为当上下左右分别的总次数确定后，无论以任何顺序操作，每个初始节点扩展的都是一个矩形。

这样就只需要考虑 u,d,l,r 这四个参数。

考虑枚举 u,d，这样每个初始节点会变成一列长条，此时容易贪心的计算出 l+r 的最小值。

具体方法为，对于每一行，处理出能覆盖到它的列坐标并升序排序，假设为 a_1,a_2,\cdots,a_m，那么：

最终答案用 \max(A+B,C) 更新即可。

对行离散化后可以做到 \text{calc}(u,d) 复杂度为 O(n^2)，考察真正能出现本质不同 a 序列的 (u,d) 组合，能得到一个多项式复杂度的算法。

• 性质二：设 s=u+d，对于 s 相等的 (u,d)，u 的不同只会导致图形的整体上下平移，不会改变相对形态。

且不难发现有用的 s 只有 O(n^2) 种。

考虑对于每个 s 计算答案，对于初始有草的点 (x,y)，连出 (x-s,y) 的列长条。

然后在这个长度为 r+s 的图形中截取长度恰为 r 的连续段，恰好代表了每一种 (u,d) 的情况。

例如在最上端就代表 u=0,d=s，最下端就是 u=s,d=0，从上往下每平移一格等价于 u\gets u+1,d\gets d-1。

对于每一段求答案需要的无非是 3 个区间 \max，用单调队列可以优化至 O(n)。

但是没完，\max_{1\leq i<m} a_{i+1}-a_i-1 本身的维护需要 O(n^2)，也就是说每次调用 s 时预处理甚至比正式处理耗时，总复杂度 O(n^4)。

• 性质三：将有用的 s 升序排序后依次考虑，每次只对 a 数组有变的列重构，总重构次数是 O(n^2) 的。

这个实现起来可能比较清楚。

因为每次会将 (x-s,y) 变成 (x-s-\Delta,y)，唯一能改变 a 数组的就是这个点在往上延申的过程中经过了某个列的下端点 (x',y')。

每次类似于冒泡排序的维护，每个上端点超过一个下端点后就一直在它上方，所以每个上端点至多导致 O(n) 次重构，总次数就是 O(n^2)。

这样总复杂度就是 O(n^3) 的了，问题完美解决！

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define per(i, a, b) for(int i = (a); i >= (b); i --)
#define Ede(i, u) for(int i = head[u]; i; i = e[i].nxt)
using namespace std;

#define eb emplace_back

inline void cmax(int &x, int y) {x = x > y ? x : y;}

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') f = (c == '-') ? - 1 : 1, c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

const int N = 310, M = N << 1;
int R, C, n, m;
struct node {int x, y;} a[N];
struct edge {int pos, opt, idx;} b[M];
int vl[M], vr[M], vm[M];
bool vis[M][N], valid[M];

void calc(int i) {
    rep(j, 1, n) vis[i][j] = vis[i - 1][j];
    vis[i][b[i].idx] = (b[i].opt == 1);
    int pre = 0; vm[i] = 0;
    rep(j, 1, n) if(vis[i][j]) {
        if(! pre) vl[i] = a[j].y - 1; else cmax(vm[i], a[j].y - a[pre].y - 1);
        pre = j;
    }
    assert(pre > 0);
    vr[i] = C - a[pre].y, cmax(vm[i], vl[i] + vr[i]);
}

bool cmp(edge p, edge q) {return (p.pos != q.pos) ? p.pos < q.pos : p.opt > q.opt;}

void init(int s) {
    sort(a + 1, a + n + 1, [](node p, node q) {return p.y < q.y;});
    rep(i, 1, n)
        b[++ m] = (edge) {a[i].x - s,  1, i}, 
        b[++ m] = (edge) {a[i].x + 1, -1, i};
    sort(b + 1, b + m + 1, cmp);
    rep(i, 1, m - 1) valid[i] = (b[i].pos != b[i + 1].pos), calc(i);
}

void moi(int x) {swap(b[x], b[x + 1]); calc(x), calc(x + 1);}

ll solve(int delta) {
    rep(i, 1, m) if(b[i].opt == 1) b[i].pos -= delta;
    while(true) {
        bool modify = false;
        rep(i, 1, m - 1)
            if(cmp(b[i + 1], b[i])) moi(i), modify = true;
        if(! modify) break;
    }
    rep(i, 1, m - 1) valid[i] = (b[i].pos != b[i + 1].pos);

    // rep(i, 1, m - 1) cerr << valid[i] << ' ' << vl[i] << ' ' << vr[i] << ' ' << vm[i] << endl;

    int ans = R + C - 2;
    deque<int> ql, qr, qm;
    for(int i = 1, j = 1; i < m; i ++) {
        while(j < m && b[j].pos - b[i].pos < R) {
            if(valid[j]) {
                while(! ql.empty() && vl[ql.back()] < vl[j]) ql.pop_back(); ql.push_back(j);
                while(! qr.empty() && vr[qr.back()] < vr[j]) qr.pop_back(); qr.push_back(j);
                while(! qm.empty() && vm[qm.back()] < vm[j]) qm.pop_back(); qm.push_back(j);
            }
            j ++;
        }
        if(b[j].pos - b[i].pos < R) break;
        ans = min((ll) ans, max((ll) vl[ql.front()] + vr[qr.front()], (ll) vm[qm.front()]));
        while(! ql.empty() && ql.front() == i) ql.pop_front();
        while(! qr.empty() && qr.front() == i) qr.pop_front();
        while(! qm.empty() && qm.front() == i) qm.pop_front();
    }
    return ans;
}

int main() {
    R = read(), C = read(), n = read();
    rep(i, 1, n) a[i].x = read(), a[i].y = read();

    sort(a + 1, a + n + 1, [](node p, node q) {return p.x < q.x;});
    vector<int> arcu, arcd, arc;
    int lim = (a[1].x - 1) + (R - a[n].x);
    rep(i, 2, n) cmax(lim, a[i].x - a[i - 1].x - 1);
    rep(i, 1, n) {
        arcu.eb(a[i].x - 1);
        arcd.eb(R - a[i].x);
        rep(j, i + 1, n) if(a[j].x - a[i].x - 1 >= lim) arc.eb(a[j].x - a[i].x - 1);
    }
    for(int u : arcu) for(int d : arcd) if(u + d >= lim) arc.eb(u + d);

    sort(arc.begin(), arc.end());
    arc.erase(unique(arc.begin(), arc.end()), arc.end());

    init(arc[0]);
    int ans = R + C - 2, siz = arc.size();
    rep(i, 0, siz - 1) {
        int delta = i ? arc[i] - arc[i - 1] : 0;

        // cerr << "val " << arc[i] << endl;

        ans = min((ll) ans, (ll) arc[i] + solve(delta));
    }
    printf("%d\n", ans);
    return 0;
}