CF2261D1.Come Be My Friend, Don't Be So Scared (Easy Version)
普及-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
This is the easy version of the problem. The difference between the versions is that in this version, m=0. You can hack only if you solved all versions of this problem.
You are hiding from the formidable Lord Verity.
There are n possible hiding spots in a row, numbered from 1 to n from left to right. You can hide in exactly one spot.
In order to find you, Lord Verity can install special detectors. Each detector covers a segment of consecutive spots and reports whether you are hiding in one of the spots in this segment. All detectors are activated simultaneously, so the segments of all detectors must be chosen before any report is known.
Lord Verity already has m detectors; the i-th of them covers the spots from li to ri. Find the minimum number of additional detectors Lord Verity needs to install so that, wherever you hide, the reports of all detectors are enough to uniquely determine the spot that you are hiding in. You also need to find a way to install them.
这是该问题的简单版本。两个版本的区别在于,在此版本中,m=0。仅当您解决了该问题的所有版本时,才可进行 Hack。
你正在躲避强大的真理领主(Lord Verity)。
一共有 n 个可能的藏身点,从左到右依次编号为 1 到 n。你只能藏在其中恰好一个位置。
为了找到你,真理领主可以安装特殊的探测器。每个探测器覆盖一段连续的藏身点,并报告你是否藏在该段内的某个位置。所有探测器同时启动,因此必须在获得任何探测报告之前就选定所有探测器所覆盖的区间。
真理领主已拥有 m 个探测器;其中第 i 个探测器覆盖从 li 到 ri 的藏身点。请找出真理领主还需额外安装的最少探测器数量,使得无论你藏在哪个位置,所有探测器的报告结果都足以唯一确定你的藏身点。此外,你还需给出一种具体的安装方案。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains two integers n and m (1≤n≤2⋅105, m=0) — the number of hiding spots and the number of detectors Lord Verity already has.
The i-th of the next m lines contains two integers li and ri (1≤li≤ri≤n) — the i-th detector covers the spots from li to ri.
It is guaranteed that no two given detectors cover the same range of hiding spots.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。随后是各测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 m(1≤n≤2⋅105,m=0)——分别表示藏匿点的数量以及领主维里蒂已有的探测器数量。
接下来的 m 行中,第 i 行包含两个整数 li 和 ri(1≤li≤ri≤n)——表示第 i 个探测器覆盖从 li 到 ri 的藏匿点。
保证任意两个给定的探测器所覆盖的藏匿点区间互不相同。
保证所有测试用例的 n 值之和不超过 2⋅105。
输出格式
For each test case, first output a single integer k — the minimum number of additional detectors.
Then output k lines. The j-th of them should contain two integers uj and vj (1≤uj≤vj≤n), meaning that the j-th additional detector covers the hiding spots from uj to vj.
If there are multiple solutions, print any of them.
对于每个测试用例,首先输出一个整数 k —— 所需额外探测器的最小数量。
然后输出 k 行。其中第 j 行应包含两个整数 uj 和 vj(1≤uj≤vj≤n),表示第 j 个额外探测器覆盖从 uj 到 vj 的藏匿点。
若存在多种解法,输出任意一种即可。
输入输出样例
输入#1
3 1 0 2 0 3 0
输出#1
0 1 1 1 2 1 1 2 2
说明/提示
In the first test case, since there is only one hiding spot, Lord Verity knows you must be hiding there. No detectors are required.
In the second test case, there are two possible hiding spots. Lord Verity can install one detector with u=v=1, which tells him if you are hiding in position 1 or not. Therefore, he can uniquely determine whether you are hiding in position 1 or 2 depending on the result.
在第一个测试用例中,由于只有一个藏身之处,维里蒂领主知道你一定藏在那里,因此无需安装任何探测器。
在第二个测试用例中,存在两个可能的藏身之处。维里蒂领主可以安装一个探测器,其参数为 u=v=1,该探测器可告诉他你是否藏在位置 1。因此,他可根据探测结果唯一确定你藏在位置 1 还是位置 2。
输入解题思路,AI测评打分。不知道怎么写?