Codeforces Round ＃771 (Div. 2)（A-C）

Problem - A - Codeforces

Array interval inversion , Let me deeply understand the meaning of the minimum order of a wave of dictionaries , The front one is as small as possible , The latter doesn't matter , During the game, always look for the interval with the largest inverse ordinal number before the reversal wa dead , This question only needs to reverse the interval where the reverse order number first appears

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n;
	cin >> n;
	vector<int> a(n + 5);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int x = 0;
	while (x < n && a[x] == x + 1) {
		x++;
	}
	if (x < n) {
		int y = x;
		while (a[y] != x + 1) {
			y++;
		}
		reverse(a.begin() + x, a.begin() + y + 1);
	}
	for (int i = 0; i < n; i++) {
		cout << a[i] << " \n"[i == n - 1];
	}
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

Problem - B - Codeforces

B At first glance, the question seems to be doing bubble sorting, but it only needs the sum of two numbers to be odd in order to exchange , It's not , The question should be T Lost a lot of people , We only need to divide odd numbers and even numbers into two sets , Judge whether the two sets are well ordered , Because if there is a set that is not well ordered , Know odd numbers + Odd number = even numbers , even numbers + even numbers = even numbers , So in any case, two numbers with the same property cannot be exchanged , In the end, it is impossible to put everything in order , In contrast, if the two sets are in order , Exchange the small one forward , The big ones are exchanged back , Odd number + even numbers = Odd number

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n;
	cin >> n;
	vector<int> odd, even;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if (x % 2 == 1) {
			odd.push_back(x);
		}
		else {
			even.push_back(x);
		}
	}
	if (is_sorted(odd.begin(), odd.end()) && is_sorted(even.begin(), even.end())) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

Problem - C - Codeforces

From the meaning of the title, we can know when ai Greater than ai+1 when ai and ai+1 You can connect a path , The point that can be reached through a continuous path is an independent set , Ask how many different sets there are in the end , Because the numbers in the array are 1 To n One of the full permutations of , So we have to deal with it before i Maximum number max, Because when i=max It shows that all the previous numbers can form an independent set, and the numbers in it must be less than or equal to i, And the latter numbers must be greater than i as well as i The number in front , Therefore, it is impossible to form a pathway , Otherwise, there must be more than max Smaller numbers , Then there must be other paths for them to form a connected graph

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int ans = 0;
	int maxx = 0;
	for (int i = 0; i < n; i++) {
		maxx = max(maxx, a[i]);
		if (maxx == i + 1) {
			ans += 1;
		}
	}
	cout << ans << endl;
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/