AtCoder Beginner Contest 241

D – Sequence Query

题目描述：

开始有一个空序列，三种操作：

• 1 x， 表示将x插入序列中
• 2 x k，表示询问序列中小于等于x的数中第k大的数是什么
• 3 x k，表示询问序列中大于等于x的数中第k小的数是什么

k小于等于5

思路：

我们可以使用multiset，通过二分来查找，然后暴力计算k即可

对于操作2，找的是<=x的数，lower_bound是找的是大于等于x的所有的数，upper_bound是找的大于x的所有的数，所以我们使用upper_bound,而我们二分的到的点的值是不需要的，所以我们在此基础上进行k次循环，使的迭代器的位置减到所需的位置

对于操作3，找的是 >=x的数，就可以使用lower_bound来处理，而这次找到的迭代器对应的点是符合题意的，所以我们只需要进行k-1次循环，使的迭代器的位置减到所需位置

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
ll op, x, k;
ll tr[MAX];

void work(){
    cin >> m;
    multiset<ll>se;
    multiset<ll>::iterator it;
    while (m--) {
        cin >> op >> x;
        if(op == 1){
            se.insert(x);
        }
        else if(op == 2){
            cin >> k;
            bool p = 1;
            it = se.upper_bound(x);
            while (k--) {
                if(it == se.begin()){
                    p = 0;
                    break;
                }
                --it;
            }
            if(p)cout << *it << endl;
            else cout << -1 << endl;
        }
        else {
            cin >> k;
            bool p = 1;
            it = se.lower_bound(x);
            while (--k) {
                if(it == se.end()){
                    p = 0;
                    break;
                }
                ++it;
            }
            if(it == se.end())p = 0;
            if(p)cout << *it << endl;
            else cout << -1 << endl;
        }
    }
}

int main(){
    work();
    return 0;
}

E – Putting Candies

题目描述：

给你一个下标从0开始的长度为n的数组ar，开始有一个空盘子，你进行k次操作，设盘子中物品的数量为x，则每次操作都会往盘子里放 $ar[x % n]$个物品，问最终盘子的物品的数量

思路：

就是一个找环的过程其实，我开始写的时候以为是这个环一定是从头开始的，但其实可能是中间的某一段产生了循环，所以第二个样例一直没过的去，后来才改的

我是先跑一个bfs，找出出现循环的长度以及发生循环前到每个点的价值dis，并开了一个数组num记录每个点出现的位置，计算答案的时候就先用k和发生循环的那个点的数进行比较，如果小于，就直接输出dis[k]，否则就计算循环前 + 循环 + 循环后这三部分的答案

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, m;
ll tr[MAX];
ll dis[MAX];
ll num[MAX];
ll id, cnt, len, val_xunhuan, p;
void bfs(){
    queue<ll>q;q.push(0);
    while (!q.empty()) {
        ll now = q.front();q.pop();
//        cout << now << ' ';
        if(num[now]){
            p = num[now] - 1;
            len = id - p;
            val_xunhuan = dis[id] - dis[p];
            break;
        }
        num[now] = ++id;
        cnt += tr[now];
        dis[id] = cnt;
        q.push(cnt % n);
    }
}

void work(){
    cin >> n >> m;
    for(int i = 0; i < n; ++i)cin >> tr[i];
    bfs();
    if(id >= m)cout << dis[m] << endl;
    else{
        ll ans = dis[p];
        m -= p;
        ans += val_xunhuan * (m / len) + dis[p + m % len] - dis[p];
        cout << ans << endl;
    }
}

int main(){
    io;
    work();
    return 0;
}

F – Skate

题意：

给一个n * m的矩阵，矩阵上有若干个障碍物，给一个起点和终点，行动的过程中只有遇到障碍物才会停下来，问能不能到达终点，能的话输出碰到的障碍物的数量最少的数量

思路：

样例如下：

首先考虑bfs，值域是1e9，很大，但是不难发现只有k个点的四个方向可以停歇，所以bfs的时候最多遍历4 * k 个点，但是这个题难在如何写代码

我们可以考虑 vector<pair<int, int> > + 二分的写法

开两个vector，一个叫hang存<x, y>, 另一个叫lie存<y, x>,我们bfs的时候，遍历到(x, y)的点时，我们去hang里面二分<x, y>,去列里面二分<y, x>,然后去更新点就可以

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int x, y;
int sx, sy, gx, gy;
vector<pii>hang;
vector<pii>lie;
struct ran{
    int x, y, num;
};
map<pii, bool>vis;
void work(){
    cin >> n >> m >> k;
    cin >> sx >> sy >> gx >> gy;
    for(int i = 1; i <= k; ++i){
        cin >> x >> y;
        hang.push_back(m_p(x, y));
        lie.push_back(m_p(y, x));
    }
    sort(hang.begin(), hang.end());
    sort(lie.begin(), lie.end());
    queue<ran>q;q.push({sx, sy, 0});
    while (!q.empty()) {
        auto [x, y, num] = q.front();q.pop();
        if(x == gx && y == gy){
            cout << num << endl;
            return;
        }
        if(vis[m_p(x, y)])continue;
        vis[m_p(x, y)] = 1;
        
        auto it = lower_bound(hang.begin(), hang.end(),m_p(x, y));
        int xx = it->first;int yy = it->second;
        if(xx == x && yy - 1 != y){
            q.push({xx, yy - 1, num + 1});
        }
        --it;
        xx = it->first; yy = it->second;
        if(xx == x && yy + 1 != y){
            q.push({xx, yy + 1, num + 1});
        }
        
        it = lower_bound(lie.begin(), lie.end(),m_p(y, x));
        xx = it->second; yy = it->first;
        if(y == yy && x != xx - 1){
            q.push({xx - 1, yy, num + 1});
        }
        --it;
        xx = it->second; yy = it->first;
        if(y == yy && x != xx + 1){
            q.push({xx + 1, yy, num + 1});
        }
    }
    cout << -1 << endl;
}


int main(){
    io;
    work();
    return 0;
}