AtCoder Beginner Contest 217 个人题解
AtCoder Beginner Contest 217 个人题解
比赛链接:AtCoder Beginner Contest 217
每篇一图:
A题 Lexicographic Order
题目大意:
判断 \(A,B\) 字符串的大小
思路解析:
\(string\) 直接判断
AC代码:
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string a,b;
cin>>a>>b;
if(a
B题 AtCoder Quiz
题目大意:
ABC,ARC,AHC,AGC
,给出其三,输出哪个未出现
思路解析:
直接判断即可
AC代码:
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
string a[5]={"0","ABC","ARC","AHC","AGC"};
int vis[5];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string op;
for(int i=1;i<=3;i++){
cin>>op;
for(int j=1;j<=4;j++){
if(op==a[j])vis[j]=1;
}
}
for(int i=1;i<=4;i++)if(vis[i]==0)cout<
C题 Inverse of Permutation
题目大意:
给出 \(pos[i]\) ,还原数组
思路解析:
模拟即可
AC代码:
#include
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int ans[maxn],x;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
ans[x]=i;
}
for(int i=1;i<=n;i++)cout<
D题 Cutting Woods
题目大意:
有一根长 \(L\) 的木头,每一次有两个操作:
- 将木头从 \(x_i\) 切开
- 询问 \(x_i\) 所在木头的长度
思路解析:
用set
存储切开木头的位置,询问时只需要找到大于 \(x_i\) 的切点和小于 \(x_i\) 的切点,两点之差即为所在木头长度
我们可以用set
自带的lower_bound
来二分处理
AC代码:
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
setst{0,n};
while(m--){
int op,x;
cin>>op>>x;
if(op==1)st.insert(x);
else {
auto itr=st.lower_bound(x);
cout<<*itr-*prev(itr)<
E题 Sorting Queries
题目大意:
给你一个空序列 \(A\) ,有以下三种操作:
- 在序列后面加入一个数 \(x\)
- 输出 \(A\) 的第一个元素并删除它
- 对 \(A\) 排序
思路解析:
我们可以用priority_queue
和queue
来维护(用multiset
和vector
也可以)
这样我们就把三个操作转化成了:
- 在
queue
加入 \(x\) - 如果
prioity_queue
非空就输出并弹出队头,否则输出并弹出queue
队头 - 把
queue
的元素压入priority\_queue
AC代码:
#include
using namespace std;
typedef pair pii;
typedef long long ll;
const int maxn=1e5+5;
queueq;
priority_queue,greater >Q;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
while(n--){
int op,x;
cin>>op;
if(op==1){
cin>>x;
q.push(x);
}
else if(op==2){
if(Q.size()){
cout<