AtCoder Beginner Contest 217 个人题解

比赛链接：AtCoder Beginner Contest 217

每篇一图：

A题 Lexicographic Order

题目大意：

判断 $A,B$ 字符串的大小

思路解析：

$string$ 直接判断

AC代码：

#include<bits/stdc++.h>
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)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

}

B题 AtCoder Quiz

题目大意：

ABC,ARC,AHC,AGC,给出其三，输出哪个未出现

思路解析：

直接判断即可

AC代码：

#include<bits/stdc++.h>
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<<a[i]<<endl;

}

C题 Inverse of Permutation

题目大意：

给出 $pos[i]$ ,还原数组

思路解析：

模拟即可

AC代码：

#include<bits/stdc++.h>
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<<ans[i]<<" ";

}

D题 Cutting Woods

题目大意：

有一根长 $L$ 的木头，每一次有两个操作：
将木头从 $x_i$ 切开
询问 $x_i$ 所在木头的长度

思路解析：

用set存储切开木头的位置，询问时只需要找到大于 $x_i$ 的切点和小于 $x_i$ 的切点，两点之差即为所在木头长度
我们可以用set自带的lower_bound来二分处理

AC代码：

#include<bits/stdc++.h>
using namespace std;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int n,m;
    cin>>n>>m;

    set<int>st{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)<<endl;
        }
    }

}

E题 Sorting Queries

题目大意：

给你一个空序列 $A$ ，有以下三种操作：
在序列后面加入一个数 $x$
输出 $A$ 的第一个元素并删除它
* 对 $A$ 排序

思路解析：

我们可以用priority_queue和queue来维护（用multiset和vector也可以）
这样我们就把三个操作转化成了：
在 queue 加入 $x$
如果 prioity_queue 非空就输出并弹出队头，否则输出并弹出 queue 队头
* 把 queue 的元素压入 priority_queue

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=1e5+5;

queue<int>q;
priority_queue<int ,vector<int>,greater<int> >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<<Q.top()<<endl;
                Q.pop();
            }
            else{
                cout<<q.front()<<endl;
                q.pop();
            }
        }
        else {
            while(q.size()){
                Q.push(q.front());
                q.pop();
            }
        }
    }

}

推广一波小飞龙博客：戳这里@不会飞的小飞龙