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)