Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3)

题意：给一些区间，求构造最短的区间长度于所给区间有交集。

题解：贪心，取左端点最大，右端点最小，作差以后和0比较取最大值。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t;
 4 int n;
 5 int main()
 6 {
 7     cin>>t;
 8     while(t)
 9     {
10         t--;int r,l;
11         cin>>n;
12         for(int i=1;i<=n;i++)
13         {
14             int x,y;cin>>x>>y;
15             l=i==1?x:max(l,x);
16             r=i==1?y:min(r,y);
17         }
18         cout<<max(l-r,0)<<"
";
19     }
20     return 0;
21 }

B.Box（CF 1262 B）

题意：给出一个排列前缀最大值，求原排列。

题解：先令p[i]=i.如果输入的a[i]<i,肯定无解。如果a[i]>p[i],交换p[a[i]]和p[i]。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int t;
 6     cin>>t;
 7     while(t--){
 8         int n, f=0;
 9         cin>>n;
10         int a[n], p[n];
11         for(int i=1; i<=n; i++) p[i]=i;
12         for(int i=1; i<=n; i++){
13             cin>>a[i];
14             if(a[i]<i) f=1;
15             if(p[i]<a[i]) swap(p[a[i]], p[i]);
16             printf("%d %d
",p[a[i]],p[i]);
17         }
18         if(f) cout<<"-1";
19         else for(int i=1; i<=n; i++) cout<<p[i]<<" ";
20         cout<<"
";
21     }
22 }

C.Messy

不会，回头在搞

D.Optimal Subsequences

题意：给定长度n的序列，有m个询问，每组询问给k，pos，求长度为k的子序列对应位置的值。要求，该子序列和最大，字典序最小。

题解：晚上再补。。。