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(。根据差分可以找线段被多少哥线段覆盖。
代码:文章来源:https://www.toymoban.com/news/detail-655372.html
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)文章来源地址https://www.toymoban.com/news/detail-655372.html
到了这里,关于区间覆盖 & 线段覆盖 & 二分的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!