当前位置:网站首页>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;
}
边栏推荐
- QT creator test
- [recommended by bloggers] background management system of SSM framework (with source code)
- Asp access Shaoxing tourism graduation design website
- 【博主推荐】C# Winform定时发送邮箱(附源码)
- SSM整合笔记通俗易懂版
- AI benchmark V5 ranking
- 连接MySQL数据库出现错误:2059 - authentication plugin ‘caching_sha2_password‘的解决方法
- 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
- Attention apply personal understanding to images
- Software testing - interview question sharing
猜你喜欢
Image recognition - pyteseract TesseractNotFoundError: tesseract is not installed or it‘s not in your path
Detailed reading of stereo r-cnn paper -- Experiment: detailed explanation and result analysis
Machine learning -- census data analysis
【博主推荐】C#生成好看的二维码(附源码)
csdn-Markdown编辑器
02-项目实战之后台员工信息管理
QT creator specify editor settings
[recommended by bloggers] background management system of SSM framework (with source code)
Solution: log4j:warn please initialize the log4j system properly
Learning question 1:127.0.0.1 refused our visit
随机推荐
[Thesis Writing] how to write function description of jsp online examination system
解决安装Failed building wheel for pillow
Principes JDBC
MySQL的一些随笔记录
Machine learning -- census data analysis
How to set up voice recognition on the computer with shortcut keys
[ahoi2009]chess Chinese chess - combination number optimization shape pressure DP
Use dapr to shorten software development cycle and improve production efficiency
Basic use of redis
Swagger、Yapi接口管理服务_SE
AcWing 1294. Cherry Blossom explanation
Number game
One click extraction of tables in PDF
[recommended by bloggers] C MVC list realizes the function of adding, deleting, modifying, checking, importing and exporting curves (with source code)
QT creator uses Valgrind code analysis tool
What does usart1 mean
QT creator design user interface
安全测试涉及的测试对象
Did you forget to register or load this tag
What does BSP mean