牛客多校六 Intervals on the Ring 数学知识

本文主要是介绍牛客多校六 Intervals on the Ring 数学知识，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Intervals on the Ring

题目描述

There is a ring of numbers consisting of 1to n sequentially. For every number i (1≤i≤n−1), i and i+1 are adjacent to each other. Particularly, n and 1 are adjacent. We use [l,r] to describe an interval on the ring. Formally, if l≤r, then the interval [l,r] is equivalent to the set {l,l+1,…,r−1,r}. Otherwise, the interval [l,r] is equivalent to {l,l+1,…,n,1,…,r−1,r}.

Yukikaze has m non-intersecting intervals. She wants you to construct a set of intervals such that the intersection of them is the union of the m intervals that Yukikaze has. The intersection of the intervals is the set of integers that the intervals have in common.

输入描述:

The first line of the input contains a single integer T (1≤T≤1000) denoting the number of test cases.

The first line of each test case contains two integers n (3≤n≤1000)nand m (1≤m≤n), denoting that the ring consists of numbers from 1 to n.

Each of the next m lines contains two integers l,r (1≤l,r≤n) denoting an interval Yukikaze has. It's guaranteed that the m intervals won't intersect with each other.

输出描述:

For each test case, if the answer doesn't exist, output −1 in a line. Otherwise, output an integer k indicating the number of intervals you construct in a line. Then output the k intervals in k lines. The number of intervals you used should never be less than one or greater than 2000.

If there are multiple solutions, print any. Don't print any extra spaces at the end of each line.

示例1

输入

2
3 1
2 2
4 2
1 1
3 3

输出

1
2 2
2
3 1
1 3

题意：给出T个测试样例，每个·测试样例给出n，集合为1-n，给出m个区间的左右端点，求出几个集合使它们的交集为m个集合的并集。

思路：由数学知识知：区间的并集的补集等于区间的补集的交集，所以先将区间按左端点由小到大排序，然后输出每一段未被覆盖区间的补集。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
pair<int,int> p[maxn];
int main(){int t,n,m,l,r;cin>>t;while(t--){cin>>n>>m;for(int i=0;i<m;i++){cin>>p[i].first>>p[i].second;//first为左端点，second为右端点 }cout<<m<<endl;sort(p,p+m);//排序时左端点为第一关键字 for(int i=0;i<m;i++){cout<<p[i].first<<" "<<p[(m+i-1)%m].second<<endl;//输出未被覆盖区间的补集 }}return 0;
}

这篇关于牛客多校六 Intervals on the Ring 数学知识的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---