求大佬找错
2026-06-14 21:13:53
发布于：广东
题目
Problem Statement
You are given positive integers ( N ) and ( M ). For each ( j = 1,2,\dots,M ), you are given a pair of integers ( (L_j, R_j) ) satisfying ( 1 \le L_j \le R_j \le N ).
Consider a length-( N ) positive integer sequence ( A = (A_1, A_2, \dots, A_N) ) satisfying the following condition for all ( j = 1,2,\dots,M ):
( A_{L_j}, A_{L_j+1}, \dots, A_{R_j} ) are all distinct.
It can be proved that such a positive integer sequence ( A ) always exists. Among all positive integer sequences ( A ) satisfying the condition, output one that minimizes the value of ( \max(A_1, A_2, \dots, A_N) ).
( T ) test cases are given; solve each of them.
Constraints
- ( 1 \le T \le 10^5 )
- ( 1 \le N \le 2 \times 10^5 )
- ( 1 \le M \le 2 \times 10^5 )
- ( 1 \le L_j \le R_j \le N ) (for all ( j ))
- All input values are integers.
- The sum of ( N ) over all test cases is at most ( 2 \times 10^5 ).
- The sum of ( M ) over all test cases is at most ( 2 \times 10^5 ).
Input
The input is given from Standard Input in the following format:
T
case1
case2
...
caseT
Each test case is given in the following format:
N M
L1 R1
L2 R2
...
LM RM
Output
Output one line per test case. For each test case, output the elements, space-separated, of a positive integer sequence ( A ) satisfying the condition that minimizes ( \max(A_1, A_2, \dots, A_N) ).
A1 A2 ... AN
If multiple such ( A ) exist, any of them will be accepted.
Sample Input 1
2
5 1
1 5
5 3
1 2
2 3
3 5
Sample Output 1
1 2 3 4 5
3 1 2 1 3
For the first test case, the output can be verified to satisfy the condition as follows:
( A_1, A_2, A_3, A_4, A_5 ) are ( 1,2,3,4,5 ), which are all distinct.
In this case, ( \max(A_1, A_2, \dots, A_N) = 5 ), which is the minimum value for a positive integer sequence satisfying the condition.
For the second test case, the output can be verified to satisfy the condition as follows:
- ( A_1, A_2 ) are ( 3,1 ), which are all distinct.
- ( A_2, A_3 ) are ( 1,2 ), which are all distinct.
- ( A_3, A_4, A_5 ) are ( 2,1,3 ), which are all distinct.
In this case, ( \max(A_1, A_2, \dots, A_N) = 3 ), which is the minimum value for a positive integer sequence satisfying the condition.
题目翻译
A - 彩色区间 /
时间限制：2 秒 / 内存限制：1024 MiB
问题描述
给定正整数 ( N ) 和 ( M )。对于每个 ( j = 1, 2, \dots, M )，给出一个整数对 ( (L_j, R_j) )，满足 ( 1 \le L_j \le R_j \le N )。
考虑一个长度为 ( N ) 的正整数序列 ( A = (A_1, A_2, \dots, A_N) )，满足以下条件：
对所有 ( j = 1, 2, \dots, M )，
( A_{L_j}, A_{L_j+1}, \dots, A_{R_j} ) 互不相同。
可以证明，这样的正整数序列 ( A ) 总是存在。在所有满足条件的正整数序列 ( A ) 中，输出一个使得 ( \max(A_1, A_2, \dots, A_N) ) 最小的序列。
共有 ( T ) 个测试用例，请分别求解。
约束条件
- ( 1 \le T \le 10^5 )
- ( 1 \le N \le 2 \times 10^5 )
- ( 1 \le M \le 2 \times 10^5 )
- ( 1 \le L_j \le R_j \le N )（对所有 ( j )）
- 所有输入均为整数
- 所有测试用例的 ( N ) 之和不超过 ( 2 \times 10^5 )
- 所有测试用例的 ( M ) 之和不超过 ( 2 \times 10^5 )
输入格式
输入从标准输入中按以下格式给出：
T
case1
case2
...
caseT
每个测试用例的格式如下：
N M
L1 R1
L2 R2
...
LM RM
输出格式
每个测试用例输出一行。对于每个测试用例，输出满足条件且使得 ( \max(A_1, A_2, \dots, A_N) ) 最小的正整数序列 ( A )，元素之间用空格分隔。
A1 A2 ... AN
如果存在多个这样的 ( A )，输出任意一个均可。
样例输入1
2
5 1
1 5
5 3
1 2
2 3
3 5
样例输出1
1 2 3 4 5
3 1 2 1 3
对于第一个测试用例，输出序列可以验证满足条件：
( A_1, A_2, A_3, A_4, A_5 ) 为 1,2,3,4,5，全部互不相同。
此时 ( \max(A_1, \dots, A_N) = 5 )，这是满足条件的正整数序列中能达到的最小值。
对于第二个测试用例，输出序列可以验证满足条件：
- ( A_1, A_2 ) 为 3,1，互不相同。
- ( A_2, A_3 ) 为 1,2，互不相同。
- ( A_3, A_4, A_5 ) 为 2,1,3，互不相同。
此时 ( \max(A_1, \dots, A_N) = 3 )，这是满足条件的正整数序列中能达到的最小值。
本蒟蒻代码:
#include<bits/stdc++.h>
using namespace std;
long long a,b,c;//石头、剪刀、布
long long t;
int main(){
cin>>t;
while(t--){
long long sum=0;
cin>>a>>b>>c;
if(a<=b&&a<=c){
if(a==0&&c==b){
cout<<c<<endl;
continue;
}
if(b>=c){
if(c>0){
sum=sum+c-1;
b=b-c+1;
}//剪刀 剪刀
if(b<=a){
if(b==0)b++;
cout<<sum+b-1<<endl;
}else{
cout<<sum+a<<endl;
}
}else{
if(b>0){
sum=sum+b;
c=c-b-1;
}
if(a<=c){
if(a==0)a++;
cout<<sum+a-1<<endl;
}else{
cout<<sum+c<<endl;
}
}
}else if(b<=a&&b<=c){
if(b==0&&c==a){
cout<<a<<endl;
continue;
}
if(a<=c){
if(a>0){
sum=sum+a-1;
c=c-a+1;
}
if(c<=b){
if(c==0)c++;
cout<<sum+c-1<<endl;
}else{
cout<<sum+b<<endl;
}
}else{
if(c>0){
sum=sum+c;
a=a-c-1;
}
if(b<=a){
if(b==0)b++;
cout<<sum+b-1<<endl;
}else{
cout<<sum+a<<endl;
}
}
}else if(c<=a&&c<=b){
if(c==0&&a==b){
cout<<a<<endl;
continue;
}
if(b<=a){
if(b>0){
sum=sum+b-1;
a=a-b+1;
}
if(a<=c){
if(a==0)a++;
cout<<sum+a-1<<endl;
}else{
cout<<sum+c<<endl;
}
}else{
if(a>0){
sum=sum+a;
b=b-a-1;
}
if(c<=b){
if(c==0)c++;
cout<<sum+c-1<<endl;
}else{
cout<<sum+b<<endl;
}
}
}
}
return 0;
}//
问了deepseek根本找不到错.....
有帮助，赞一个