题目大意
给出环上的一组区间,你需要构造环上的一组区间使得这些区间的交是给定的区间的并。
解题思路
集合的德摩根律告诉我们 \overline{\cup{A_i}}=\cap\overline{A_i}(区间的并的补等于区间的补的交),所以输出每一段未被给出区间覆盖的区间的补即可。
老实说还是有点一知半解。。。如果让我自己手动从头推理或许给多长时间也想不到吧:(
代码实现
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5+7;
const int eps = 1e-8;
const int inf = 0x7f7f7f7f;
const int mod = 1e9+7;
int T;
int n,m,k;
struct node{
int l,r;
} a[N];
int cmp(node a,node b){
if(a.l==b.l) return a.r<b.r;
return a.l<b.l;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i].l>>a[i].r;
}
sort(a+1,a+m+1,cmp);
cout<<m<<endl;
for(int i=2;i<=m;i++){
cout<<a[i].l<<" "<<a[i-1].r<<endl;
}
cout<<a[1].l<<" "<<a[m].r<<endl;
}
return 0;
}
0 条评论