Codeforces Round ＃771 (Div. 2)

A. Reverse

For this problem, we only need to combine the array and the array arranged in order （1,2,3…n） Just compare , Find the first unequal position l, Then continue to find in the following array l The smallest number that should have been placed in the position （ namely l） The subscript of the number of r, Then flip [l, r], If they are all equal , Then this is the smallest , Direct output
Reference code ：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++) 
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;

const int N = 510;

int a[N], b[N];

int main()
{
    
	int T;
	cin >> T;
	
	while(T--)
	{
    
		int n;
		cin >> n;
		rep(i, 1, n) cin >> a[i], b[i] = i;
		
		int l = -1, r;
		rep(i, 1, n)
			if(a[i] != b[i])
			{
    
				l = i;
				break;
			}
		
		if(l == -1)
		{
    
			rep(i, 1, n) cout << a[i] << ' ';
			cout << endl;
			continue;
		}
		
		rep(i, 1, n) 
			if(a[i] == b[l])
			{
    
				r = i;
				break;
			}
			
		rep(i, 1, l - 1) cout << a[i] << ' ';
		pre(i, l, r) cout << a[i] << ' ';
		rep(i, r + 1, n) cout << a[i] << ' ';
		cout << endl;
	}
	
	return 0;
} 

B. Odd Swap Sort

In this problem, we can divide these numbers into 2 An array , According to the title requirements , Only a[i] + a[i + 1] Only odd numbers can be exchanged , So I want to exchange 2 Adjacent numbers , Then their parity will be different , So we can enumerate in order , Divide these numbers into 2 An array （ Odd and even arrays ）, Then judge this 2 Whether there is an array a[i] > a[i + 1], Because parity is the same and cannot be exchanged , Want to exchange big numbers back , So they 2 The number must be exchanged once , If it doesn't exist , Then it can be arranged in order , On the contrary, we can't .
Reference code ：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++) 
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

int main()
{
    
	int T;
	cin >> T;
	
	while(T--)
	{
    
		int n, n1 = 0, n2 = 0;
		cin >> n;
		rep(i, 1, n)
		{
    
			int x;
			cin >> x;
			if(x & 1) a[n1++] = x;
			else b[n2++] = x;
		}
		
		bool flag = true;
		rep(i, 0, n1 - 2) 
			if(a[i] > a[i + 1]) flag = false;
		rep(i, 0, n2 - 2)
			if(b[i] > b[i + 1]) flag = false;
			
		if(flag) puts("Yes");
		else puts("No");
	}
	
	return 0;
}

C. Inversion Graph

We can use a monotonically increasing stack to solve this problem , Each element in the stack represents the largest element in a connected block ,
So how do we maintain this stack ？
First, traverse the array in sequence ：

1. a[i] > q.top()： Because it's a monotonous stack , So it is larger than all the numbers in the stack , Directly into the stack as a new connected block
2. a[i] < q.top() ： This is a judgment q.top() Whether it can connect with other elements in the stack , That is, the elements in the stack can be combined with a[i] Connected to a （ That is to say q[i] > a[i]）, At this time, we just need to put greater than a[i] All the numbers are out of the stack , But the top of the stack cannot be out of the stack .
   Reference code ：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++) 
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;

int main()
{
    
	int T;
	cin >> T;
	while(T--)
	{
    
		stack<int> a;
		int n;
		cin >> n;
		rep(i, 1, n)
		{
    
			int x;
			cin >> x;
			if(a.empty())
			{
    
				a.push(x);
				continue;
			}
			
			if(x > a.top()) a.push(x);
			else
			{
    
				int t = a.top();
				while(!a.empty() && a.top() > x) a.pop();
				a.push(t);
			}
		}
		
		cout << a.size() << endl;
	}
	
	return 0;
}