区间覆盖 和amp; 线段覆盖 和amp; 二分

4195. 线段覆盖 - AcWing题库

P2082 区间覆盖（加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

做法：

void solve() {
    int n; cin>>n;
    vector<array<LL,2>> seg(n);
    for(auto &t: seg) cin>>t[0]>>t[1];
    sort(all(seg), [](array<LL,2> pre, array<LL,2> suf) {
        if(pre[0] == suf[0]) return pre[1] < suf[1];
        return pre[0] < suf[0];
    });
    vector<array<LL,2>> last;
    last.push_back(seg[0]);
    for(int i = 1; i < n;   i) {
        if(seg[i][0] <= last.back()[1]) last.back()[1] = max(last.back()[1], seg[i][1]);
        else last.push_back(seg[i]);
    }
    LL ans = 0;
    for(auto &t: last) ans  = t[1] - t[0]   1;
    cout<<ans;
}

差分解决区间覆盖：（这题不能过，但是感觉这个做法有用）

void solve() {
    int n; cin>>n;
    vector<int> dif(1000   1);
    int rl = 0;
    rep(i,1,n) {
        int l, r; cin>>l>>r;
        dif[l]  ;
        dif[r 1]--; rl = max(rl, r); 
    }
    int sum = 0;
    int now = 0;
    rep(i,1,rl) {
        now  = dif[i];
        if(now > 0) sum  ;
    }
    cout<<sum;
}

4195. 线段覆盖 - AcWing题库

问题描述： 坐标轴中共有多少个整数坐标的点满足恰好被 k条线段覆盖。

思路：离散化差分，用map（。根据差分可以找线段被多少哥线段覆盖。

代码：

void solve() {
    int n; cin>>n;
    map<LL,LL> mll;
    vector<LL> ans(n   1);
    rep(i,1,n) {
        LL l,r; cin>>l>>r;
        mll[l]  ;
        mll[r 1]--;
    }
    LL last = -1,sum = 0;
    for(auto t: mll) {
        LL f = t.vf, s = t.vs;
        if(last != -1) ans[sum]  = f - last;
        sum  = s;
        last = f;
    }
    rep(i,1,n) cout<<ans[i]<<" ";
}

二分 (nowcoder.com)

问题描述：根据对话，找可能的最多正确的对话。

思路：

如果是 val ，说明猜的数val比答案要大，此时，答案在区间(-inf, val)。

如果是val -，说明猜的数val比答案要小，此时，答案在区间(val, inf)。

如果是val .，说明猜的数val等于答案，此时，答案在区间[val, val 1)。

可以用差分求最大覆盖区间。数据离散，可以用map代替差分离散化。

代码：

void solve() {
    LL inf = LONG_LONG_MAX - 123456789;
    int n; cin>>n;
    map<LL,LL> mll;
    char op[2];
    rep(i,1,n) {
        int v; cin>>v>>op;
        if(op[0] == '.') { // 等于 [val, val   1)
            mll[v]  , mll[v 1]--;
        }
        else if(op[0] == ' ') { // 大 (-inf, v)
            mll[-inf]  ;
            mll[v]--; 
        } else { // 小 (v 1, inf)
            mll[v 1]  ;
            mll[inf]--;
        }
    }
    int ans = 0, sum = 0;
    for(auto t: mll) {
        sum  = t.vs;
        ans = max(sum, ans);
    }
    cout<<ans;
}

【2023陕西训练营】day1 枚举和枚举优化 - Virtual Judge (vjudge.net)

这篇好文章是转载于：学新通技术网