AtCoder Beginner Contest 348

A - Penalty Kick

依照题意输出即可

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

void solve(){
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        cout << (i % 3 == 0? 'x': 'o');
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

B - Farthest Point

依照题意计算欧式距离即可

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

void solve(){
    int n;
    cin >> n;
    vector<array<double,2>> points(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> points[i][0] >> points[i][1];
    }

    for(int i = 1; i <= n; i++){
        double mx = 0;
        int res = 1;
        for(int j = 1; j <= n; j++){
            double dis = sqrt(pow(points[i][0] - points[j][0], 2) + pow(points[i][1] - points[j][1], 2));
            if (dis > mx){
                res = j;
                mx = dis;
            }
        }
        cout << res << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

C - Colorful Beans

维护每种颜色的最小值，最后答案取维护后的结果的最大值即可

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

void solve(){
    int n;
    cin >> n;
    vector<array<int,2>> beans(n);
    for(int i = 0; i < n; i++){
        cin >> beans[i][0] >> beans[i][1];
    }

    map<int,int> mp;
    for(int i = 0; i < n; i++){
        auto [d, c] = beans[i];
        if(mp.count(c)){
            mp[c] = min(mp[c], d);
        }
        else{
            mp[c] = d;
        }
    }

    int ans = 0;
    for(auto [c, d]: mp){
        ans = max(ans, d);
    }
    cout << ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

D - Medicines on Grid

TLE闹麻了，最后默写了一边别人的代码，9ms，更麻了

懒得改了，似乎是剪枝错了，以及递归调用花了太多时间。

正解使用了优先队列，然后是循环搜索，优先使用可用步数更大状态，就有更大的可能更快搜索到终点，并且如果在当前位置有一个可用步数更大的状态，那么当前状态就没有必要继续下去了，可以直接剪枝剪掉。

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

void solve(){
    int h, w;
    cin >> h >> w;
    vector<vector<char>> grid(h + 1, vector<char>(w + 1));
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> grid[i][j];
        }
    }
    int n;
    cin >> n;
    vector<vector<int>> energy(h + 1, vector<int>(w + 1, -1));
    for(int i = 1; i <= n; i++){
        int r, c, e;
        cin >> r >> c >> e;
        energy[r][c] = e;
    }

    int x = 0, y = 0;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if(grid[i][j] == 'S'){
                x = i;
                y = j;
                break;
            }
        }
        if(x != 0){
            break;
        }
    }

    priority_queue<array<int,3>> pque;
    pque.push({0, x, y});
    vector<vector<int>> mx(h + 1, vector<int>(w + 1, -1));
    mx[x][y] = 0;
    int dxy[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
    while(!pque.empty()){
        auto [val, x, y] = pque.top();
        pque.pop();

        val = max(val, energy[x][y]);
        energy[x][y] = -1;
        if(val <= mx[x][y] || val <= 0){
            continue;
        }
        else{
            mx[x][y] = val;
            for(int i = 0; i < 4; i++){
                int nx = x + dxy[i][0];
                int ny = y + dxy[i][1];

                if(1 <= nx && nx <= h && 1 <= ny && ny <= w && grid[nx][ny] != '#' && max(val - 1, energy[nx][ny]) > mx[nx][ny]){
                    if(grid[nx][ny] == 'T'){
                        cout << "Yes";
                        return;
                    }
                    pque.push({max(val - 1, energy[nx][ny]), nx, ny});
                    energy[nx][ny] = -1;
                }
            }
        }
    }
    cout << "No";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}