AtCoder Beginner Contest 241 A-D

发布于 2022-02-26  1.23k 次阅读


内容纲要

A - Digit Machine

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

int a[15]; 

int main(){
    for(int i = 0; i < 10; i++) cin>>a[i];
    int ds = 0;
    for(int i = 0; i < 3; i++){
        ds = a[ds];
    }
    printf("%d", ds);
}

B - Pasta

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

map<int, int> p;

int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        int k;
        cin>>k;
        p[k]++;
    }
    for(int i = 1; i <= m; i++){
        int k;
        cin>>k;
        p[k]--;
        if(p[k] < 0){
            printf("No");
            return 0;
        }
    }
    printf("Yes");
}

C - Connect 6

题解:

队列遍历每个'#'的点,判断一下附加符合条件的位置是否有3个以及以上(加上自己4个,然后还能补两个就是6个了)就行了

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

const int N = 1100;
char mp[N][N];
int dx[] = {0,0,-1,1,-1,-1,1,1};
int dy[] = {-1,1,0,0,-1,1,-1,1};

queue<pair<int, int> > q; 

int main(){
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        char k;scanf("%c", &k);
        for(int j = 1; j <= n; j++){
            scanf("%c", &mp[i][j]);
            if(mp[i][j] == '#') q.push(pair<int, int>(i, j));
        }
    }
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop();
        for(int k = 0; k < 8; k++){
            int u = x, v = y, ct = 1, flag = 1;
            for(int i = 0; i < 5; i++){
                u+=dx[k],v+=dy[k];
                if(u < 1 || v < 1 || u > n || v > n){
                    flag = 0;
                    break;
                };
                if(mp[u][v] == '#') ct++;
            }
            if(ct >= 4 && flag){
                printf("Yes");
                return 0;
            }
        }
    }
    printf("No");
}

D - Sequence Query

题解:

一开始是用的vector + 二分,题没看清没开long long,WA6个点,改过来之后又是TEL最后三个点

结束了才知道vector的insert操作是O(N)的,应该就挂在这了

正解是用multiset,确实是个以前没接触过的数据结构

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

multiset<long long> s; 

int main(){
    int t;
    scanf("%d", &t);
    int ct = 0;
    while(t--){
        long long op;
        scanf("%lld", &op);
        if(op == 1){
            long long x;
            scanf("%lld", &x);
            s.insert(x);
        }
        if(op == 2){
            long long x,k;
            scanf("%lld%lld", &x, &k);
            auto it = s.upper_bound(x);
            while(it != s.begin() && k > 0) k--, it--;
            if(k > 0){
                printf("-1\n");
            } else {
                printf("%lld\n", *it);
            }
        }
        if(op == 3){
            long long x,k;
            scanf("%lld%lld", &x, &k);
            auto it = s.lower_bound(x);
            while(it != s.end() && k > 1){
                k--, it++;
            }
            if(it == s.end()){
                printf("-1\n");
            } else {
                printf("%lld\n", *it);
            }
        }
    }
}

不爱嘉然小姐十年了。十年里,爱过的每个人都像她。