当前位置:网站首页>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;
}
边栏推荐
猜你喜欢
![[Thesis Writing] how to write function description of jsp online examination system](/img/f8/13144e0febf4a576bbcc3290192079.jpg)
[Thesis Writing] how to write function description of jsp online examination system

Dotnet replaces asp Net core's underlying communication is the IPC Library of named pipes
![[number theory] divisor](/img/ec/036d7e76cc566c08d336444f2898e1.jpg)
[number theory] divisor

Request object and response object analysis

Mtcnn face detection

Django running error: error loading mysqldb module solution

图片上色项目 —— Deoldify

Did you forget to register or load this tag

vs2019 使用向导生成一个MFC应用程序

MySQL主從複制、讀寫分離
随机推荐
Use dapr to shorten software development cycle and improve production efficiency
Why can't I use the @test annotation after introducing JUnit
About string immutability
Did you forget to register or load this tag
Software testing and quality learning notes 3 -- white box testing
[number theory] divisor
Machine learning notes week02 convolutional neural network
QT creator specify editor settings
QT creator test
What does usart1 mean
Vs2019 desktop app quick start
Software I2C based on Hal Library
error C4996: ‘strcpy‘: This function or variable may be unsafe. Consider using strcpy_s instead
[蓝桥杯2017初赛]包子凑数
保姆级出题教程
DICOM: Overview
记某公司面试算法题:查找一个有序数组某个数字出现的次数
QT creator specifies dependencies
打开浏览器的同时会在主页外同时打开芒果TV,抖音等网站
软件测试与质量学习笔记3--白盒测试