题解：P10762 [BalticOI 2024] Fire

北文 · 2024-07-17 20:27:00 · 题解

建议管理增加描述：
要覆盖所有时间而不是所有整点！（调了很久）

那么讲讲这题怎么做。
这题有个很显然的贪心策略：如果已经选取了一段，那么在选取的这段中，选取能往后延伸最长的那一个进行扩展。
但是也有一个显然的问题，那就是不知道第一个取哪一个。怎么确定呢，枚举吗？也许只能枚举。
那么我们考虑加速这个贪心过程。选取哪一个作为第一个并不影响每一个位置的决策，考虑用倍增进行优化。
记 f[i][j] 表示在第 i 个位置再选取 2^j 个人能到达什么位置，f 数组的计算可以用 dp，这都是比较简单的。
还有就是数据范围太大需要离散化处理。

我的代码是建立在覆盖所有整点的题意上改过来的，所以有亿点丑。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5, inf=1e9;
int n, lsh[N*3], m, cn, f[N*3][21], nn;
pair<int, int> a[N*3], b[N*3];
#define fi first
#define se second
bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.fi<b.fi; 
}
inline void ckmax(int &x, int y) { if(y>x) x=y; }
int main() {
    scanf("%d %d", &n, &nn);
    for(int i=1; i<=n; i++) {
        scanf("%d %d", &a[i].fi, &a[i].se);
        lsh[++m]=a[i].fi; lsh[++m]=a[i].se;
        if(a[i].fi!=0)
        lsh[++m]=a[i].fi-1; 
        if(a[i].se!=0)
        lsh[++m]=a[i].se-1;
        if(a[i].fi!=nn-1)
        lsh[++m]=a[i].fi+1; 
        if(a[i].se!=nn-1)
        lsh[++m]=a[i].se+1;
    }
    lsh[++m]=nn-1;
    lsh[++m]=0;
    sort(lsh+1, lsh+1+m);
    m=unique(lsh+1, lsh+1+m)-lsh-1;
    for(int i=1; i<=n; i++)
        a[i].fi=lower_bound(lsh+1, lsh+1+m, a[i].fi)-lsh-1,
        a[i].se=lower_bound(lsh+1, lsh+1+m, a[i].se)-lsh-1; 
    for(int i=1; i<=n; i++) {
        if(a[i].fi<a[i].se) {
            b[++cn]=a[i];
            b[++cn]={a[i].fi+m, a[i].se+m};
        } else {
            b[++cn]={a[i].fi, a[i].se+m};
        }
    }
    for(int i=1; i<=cn; ++i) {ckmax(f[b[i].fi][0], b[i].se);}
    for(int i=0; i<=m*2; ++i) {ckmax(f[i+1][0], f[i][0]);}
    for(int k=1; k<=18; ++k) {
        for(int i=0; i<=m*2; ++i)
            f[i][k]=f[f[i][k-1]][k-1];
        for(int i=0; i<=m*2; ++i)
            ckmax(f[i+1][k], f[i][k]);
    }
    int ans=inf;
    for(int i=0; i<m; ++i) {
        int u=i, t=0;
        for(int k=18; k>=0; --k) {
            if(f[u][k]<=i+m-1) {
                t+=1<<k; 
                u=f[u][k];
            }
        }
        if(f[u][0]>i+m-1) {
            ans=min(ans, t+1);
        }
    }
    if(ans>=inf) printf("-1\n");
    else printf("%d\n", ans);
    return 0;
}