当前位置:网站首页>Codeforces Round #771 (Div. 2)
Codeforces Round #771 (Div. 2)
2022-07-06 11:25:00 【%xiao Q】
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 :
- 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
- 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;
}
边栏推荐
- Ansible practical Series II_ Getting started with Playbook
- DICOM: Overview
- [number theory] divisor
- MySQL的一些随笔记录
- AcWing 1294.樱花 题解
- QT creator runs the Valgrind tool on external applications
- 人脸识别 face_recognition
- Number game
- 打开浏览器的同时会在主页外同时打开芒果TV,抖音等网站
- UDS learning notes on fault codes (0x19 and 0x14 services)
猜你喜欢
When you open the browser, you will also open mango TV, Tiktok and other websites outside the home page
[Thesis Writing] how to write function description of jsp online examination system
AcWing 1298. Solution to Cao Chong's pig raising problem
C语言读取BMP文件
MySQL主從複制、讀寫分離
Integration test practice (1) theoretical basis
Rhcsa certification exam exercise (configured on the first host)
QT creator runs the Valgrind tool on external applications
机器学习--人口普查数据分析
软件测试与质量学习笔记3--白盒测试
随机推荐
Swagger, Yapi interface management service_ SE
误删Path变量解决
Software testing - interview question sharing
Ansible practical series I_ introduction
C语言读取BMP文件
人脸识别 face_recognition
QT creator custom build process
vs2019 使用向导生成一个MFC应用程序
Ansible practical Series II_ Getting started with Playbook
基于apache-jena的知识问答
Knowledge Q & A based on Apache Jena
Install mysql5.5 and mysql8.0 under windows at the same time
Number game
使用lambda在循环中传参时,参数总为同一个值
L2-004 这是二叉搜索树吗? (25 分)
[download app for free]ineukernel OCR image data recognition and acquisition principle and product application
Picture coloring project - deoldify
What does usart1 mean
Deoldify project problem - omp:error 15:initializing libiomp5md dll,but found libiomp5md. dll already initialized.
JDBC原理