当前位置:网站首页>Codeforces Round #771 (Div. 2)
Codeforces Round #771 (Div. 2)
2022-07-06 09:14:00 【%xiao Q】
A. Reverse
这题我们只需要把数组和按顺序排的数组(1,2,3…n)比较即可,找到第一个不相等的位置 l,然后继续在后面数组找到 l 位置原本应该放的最小的数字(即 l)的数的下标 r,然后翻转[l, r],如果都相等,那么这个就是最小的,直接输出
参考代码:
#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
这题我们可以按照奇偶性来将这些数划分为2个数组,根据题目要求,只有a[i] + a[i + 1]为奇数才可以交换,所以想要交换2个相邻的数,那么他们的奇偶性快点不同,所以我们可以按顺序枚举,将这些数分为2个数组(奇数和偶数数组),然后判断这2个数组里面是否存在a[i] > a[i + 1],因为奇偶性相同是不能交换的,想要把大的数往后面交换,那么他们2个数肯定要交换一次,如果不存在,那么就可以排成有序,反之不能。
参考代码:
#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
这题我们可以利用一个单调递增的栈来做,栈内每个元素代表一个连通块中最大的元素,
那么我们如何来维护这个栈呢?
首先安顺序遍历这个数组:
- a[i] > q.top():因为是单调栈,所以大于栈内所有的数,直接入栈为一个新的连通块
- a[i] < q.top() :这时一个判断q.top()是否可以和栈内其它元素连通,即栈内元素可以和a[i]相连(也就是q[i] > a[i]),这时我们只要把大于a[i]的数全部出栈即可,但是栈顶不能出栈。
参考代码:
#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;
}
边栏推荐
- MySQL完全卸载(Windows、Mac、Linux)
- CSDN markdown editor
- 连接MySQL数据库出现错误:2059 - authentication plugin ‘caching_sha2_password‘的解决方法
- AcWing 1294. Cherry Blossom explanation
- Are you monitored by the company for sending resumes and logging in to job search websites? Deeply convinced that the product of "behavior awareness system ba" has not been retrieved on the official w
- What does BSP mean
- 机器学习笔记-Week02-卷积神经网络
- SSM整合笔记通俗易懂版
- Error connecting to MySQL database: 2059 - authentication plugin 'caching_ sha2_ The solution of 'password'
- 打开浏览器的同时会在主页外同时打开芒果TV,抖音等网站
猜你喜欢
[recommended by bloggers] background management system of SSM framework (with source code)
打开浏览器的同时会在主页外同时打开芒果TV,抖音等网站
Why is MySQL still slow to query when indexing is used?
Deoldify project problem - omp:error 15:initializing libiomp5md dll,but found libiomp5md. dll already initialized.
neo4j安装教程
Learning question 1:127.0.0.1 refused our visit
自动机器学习框架介绍与使用(flaml、h2o)
引入了junit为什么还是用不了@Test注解
解决安装Failed building wheel for pillow
CSDN markdown editor
随机推荐
AcWing 1298. Solution to Cao Chong's pig raising problem
Basic use of redis
Rhcsa certification exam exercise (configured on the first host)
Ansible practical Series II_ Getting started with Playbook
Remember a company interview question: merge ordered arrays
QT creator test
[C language foundation] 04 judgment and circulation
Swagger、Yapi接口管理服务_SE
Software testing and quality learning notes 3 -- white box testing
Solution: log4j:warn please initialize the log4j system properly
Julia 1.6 1.7 common problem solving
How to configure flymcu (STM32 serial port download software) is shown in super detail
neo4j安装教程
Deoldify项目问题——OMP:Error#15:Initializing libiomp5md.dll,but found libiomp5md.dll already initialized.
01项目需求分析 (点餐系统)
[ahoi2009]chess Chinese chess - combination number optimization shape pressure DP
Record a problem of raspberry pie DNS resolution failure
Image recognition - pyteseract TesseractNotFoundError: tesseract is not installed or it‘s not in your path
Did you forget to register or load this tag
Test objects involved in safety test