当前位置:网站首页>Codeforces Round #771 (Div. 2)
Codeforces Round #771 (Div. 2)
2022-07-06 09:29:00 【狗蛋儿l】
A. Reverse
You are given a permutation p1,p2,…,pn of length n. You have to choose two integers l,r (1≤l≤r≤n) and reverse the subsegment [l,r] of the permutation. The permutation will become p1,p2,…,pl−1,pr,pr−1,…,pl,pr+1,pr+2,…,pn.
Find the lexicographically smallest permutation that can be obtained by performing exactly one reverse operation on the initial permutation.
Note that for two distinct permutations of equal length a and b, a is lexicographically smaller than b if at the first position they differ, a has the smaller element.
A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).
Input
Each test contains multiple test cases. The first line contains a single integer t (1≤t≤500) — the number of test cases. Description of the test cases follows.
The first line of each test case contains a single integer n
(1≤n≤500) — the length of the permutation.
The second line of each test case contains n
integers p1,p2,…,pn (1≤pi≤n) — the elements of the permutation.
Output
For each test case print the lexicographically smallest permutation you can obtain.
Example
Input
4
1
1
3
2 1 3
4
1 4 2 3
5
1 2 3 4 5
Output
1
1 2 3
1 2 4 3
1 2 3 4 5
Note
In the first test case, the permutation has length 1, so the only possible segment is [1,1]. The resulting permutation is [1].
In the second test case, we can obtain the identity permutation by reversing the segment [1,2]. The resulting permutation is [1,2,3].
In the third test case, the best possible segment is [2,3]. The resulting permutation is [1,2,4,3].
In the fourth test case, there is no lexicographically smaller permutation, so we can leave it unchanged by choosing the segment [1,1]. The resulting permutation is [1,2,3,4,5].
#include <bits/stdc++.h>
using namespace std;
int n,t,p[510];
int main()
{
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)cin>>p[i];
for(int i=1;i<=n;i++){
if(p[i]!=i){
int j=i+1;
for(;j<=n;j++)
if(p[j]==i)break;
reverse(p+i,p+j+1);
break;
}
}
for(int i=1;i<=n;i++)cout<<p[i]<<' ';
cout<<'\n';
}
return 0;
}
B. Odd Swap Sort
You are given an array a1,a2,…,an. You can perform operations on the array. In each operation you can choose an integer i (1≤i<n), and swap elements ai and ai+1 of the array, if ai+ai+1is odd.
Determine whether it can be sorted in non-decreasing order using this operation any number of times.
Input
Each test contains multiple test cases. The first line contains a single integer t
(1≤t≤105) — the number of test cases. Description of the test cases follows.
The first line of each test case contains a single integer n
(1≤n≤105) — the length of the array.
The second line of each test case contains n
integers a1,a2,…,an (1≤ai≤109) — the elements of the array.
It is guaranteed that the sum of n
over all test cases does not exceed 2⋅105.
Output
For each test case, print “Yes” or “No” depending on whether you can or can not sort the given array.
You may print each letter in any case (for example, “YES”, “Yes”, “yes”,“yEs” will all be recognized as positive answer).
Example
Input
4
4
1 6 31 14
2
4 2
5
2 9 6 7 10
3
6 6 6
Output
Yes
No
No
Yes
Note
In the first test case, we can simply swap 31
and 14 (31+14=45 which is odd) and obtain the non-decreasing array [1,6,14,31].
In the second test case, the only way we could sort the array is by swapping 4and 2, but this is impossible, since their sum 4+2=6is even.
In the third test case, there is no way to make the array non-decreasing.
In the fourth test case, the array is already non-decreasing.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
while(t--){
ll n, x;
cin >> n;
ll even = 0 , odd = 0;
bool flag = true;
for (int i = 0; i < n; i++)
{
cin >> x;
if (x & 1)
{
if (x < odd)flag = false;
odd = max(odd, x);
}
else
{
if (x < even)flag = false;
even = max(x, even);
}
}
if (flag)cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
C. Inversion Graph
You are given a permutation p1,p2,…,pn. Then, an undirected graph is constructed in the following way: add an edge between vertices i, j such that ipj. Your task is to count the number of connected components in this graph.
Two vertices uand v belong to the same connected component if and only if there is at least one path along edges connecting u and v.
A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4in the array).
Input
Each test contains multiple test cases. The first line contains a single integer t (1≤t≤105) — the number of test cases. Description of the test cases follows.
The first line of each test case contains a single integer n (1≤n≤105) — the length of the permutation.
The second line of each test case contains n
integers p1,p2,…,pn (1≤pi≤n) — the elements of the permutation.
It is guaranteed that the sum of n
over all test cases does not exceed 2⋅105.
Output
For each test case, print one integer k — the number of connected components.
Example
Input
6
3
1 2 3
5
2 1 4 3 5
6
6 1 4 2 5 3
1
1
6
3 2 1 6 5 4
5
3 1 5 2 4
Output
3
3
1
1
2
1
Note
Each separate test case is depicted in the image below. The colored squares represent the elements of the permutation. For one permutation, each color represents some connected component. The number of distinct colors is the answer.
#include <bits/stdc++.h>
using namespace std;
int main(){
int t ;
cin>>t;
while(t -- ) {
int n ;
cin>> n ;
map<int , int> p ;
int res= 0 , maxx = 1 ;
for(int i = 1 ; i <= n ; i ++ ) {
int k ;
cin>>k ;
p[k] = 1 ;
while(p[maxx]) maxx ++ ;
if(maxx > i ) res ++ ;
}
cout<<res <<"\n" ;
}
return 0 ;
}
边栏推荐
猜你喜欢
Codeforces Round #802(Div. 2)A~D
Kubernetes cluster deployment
分享一个在树莓派运行dash应用的实例。
Pull branch failed, fatal: 'origin/xxx' is not a commit and a branch 'xxx' cannot be created from it
Hbuilder X格式化快捷键设置
解决Intel12代酷睿CPU单线程调度问题(二)
Raspberry pie 4B installation opencv3.4.0
Maximum product (greedy)
QT有关QCobobox控件的样式设置(圆角、下拉框,向上展开、可编辑、内部布局等)
(lightoj - 1369) answering queries (thinking)
随机推荐
生成随机密码/验证码
第 300 场周赛 - 力扣(LeetCode)
Raspberry pie 4B installation opencv3.4.0
Input can only input numbers, limited input
树莓派4B64位系统安装miniconda(折腾了几天终于解决)
Market trend report, technological innovation and market forecast of China's double sided flexible printed circuit board (FPC)
QT有关QCobobox控件的样式设置(圆角、下拉框,向上展开、可编辑、内部布局等)
简单尝试DeepFaceLab(DeepFake)的新AMP模型
Codeforces - 1526C1&&C2 - Potions
input 只能输入数字,限定输入
(POJ - 3685) matrix (two sets and two parts)
Codeforces Round #803 (Div. 2)A~C
Educational Codeforces Round 130 (Rated for Div. 2)A~C
Generate random password / verification code
(lightoj - 1369) answering queries (thinking)
Research Report of desktop clinical chemical analyzer industry - market status analysis and development prospect prediction
提交Spark应用的若干问题记录(sparklauncher with cluster deploy mode)
Effet d'utilisation, déclenché lorsque les composants de la fonction sont montés et déchargés
VMware Tools和open-vm-tools的安装与使用:解决虚拟机不全屏和无法传输文件的问题
409. Longest palindrome