8.8 竞技世界 笔试真题 个人题解记录

第一题 收大白菜

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int N;
vector<int> val;
// 基于邻接表的有向图
vector<vector<int>> graph;
// 结果数组，能收的最大白菜数量，当前节点，当前收的白菜数量，当前走过的点
void dfs(vector<int>& res, int& iMax, int st, int tem, vector<int>& cur){
    tem += val[st];
    cur.push_back(st);
    //  没有路可走
    if(graph[st].size() == 0){
        if(tem > iMax){
            iMax = tem;
            res = cur;
        } else if(tem == iMax) {
            // 当收的白菜的个数相等时，判断下标的大小，因为数组里面存放的都是下标，直接求和比较即可
            int tot1 = accumulate(res.begin(), res.end(), 0);
            int tot2 = accumulate(cur.begin(), cur.end(), 0);
            if(tot1 > tot2) res = cur;
        }
    }
    // DFS 深搜
    for(int i=0; i<graph[st].size(); i++)
        dfs(res, iMax, graph[st][i], tem, cur);

}
int main(){
    cin >> N;
    // 为了不进行下标的转换，直接多开一维
    val.resize(N+1);
    graph.resize(N+1);
    for(int i=1; i<=N; i++)
        cin >> val[i];
    int tem = 0;
    for(int i=1; i<N; i++)
        for(int j=i+1; j<=N; j++){
            cin >> tem;
            // 如果为 1 代表有一条路，直接存放下标
            if(tem == 1) graph[i].push_back(j);
        }

    vector<int> res;
    vector<int> cur;
    int iMax = 0;
    // dfs 大法好
    dfs(res, iMax, 1, 0, cur);
    cout << iMax << endl;
    for(int i=0; i<res.size()-1; i++)
        cout << res[i] << ' ';
    cout << res.back() << endl;
    return 0;
}

第二题 发工资

大于 50 的部分肯定得优先发 50 100 的，所以先算一下 50 一下的最优解法，后面直接代入即可
想了一下 大于 5 的好像就优先发 大于5的，这块儿还能更加简化一下

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> val(n, 0);
    for(auto &it:val)
        cin >> it;
    int iMax = *max_element(val.begin(), val.end());
    vector<int> coins{1, 2, 5, 10, 20, 50, 100};
    // 大于 50 的部分肯定是得 50 100 的发
    vector<int> dp(51, 51);
    dp[0] = 0;
    for(int i = 1; i<=min(iMax, 50); i++)
        for(int j=0; j<coins.size() && i >= coins[j]; j++)
            dp[i] = min(dp[i], dp[i-coins[j]] + 1);

    int res = 0;
    for(auto &it:val){
        res += it/100;
        it %= 100;
        res += it/50 + dp[it%50];
    }
    cout << res << endl;
    return 0;
}

优化后的代码，应该能过，不太确定

#include <iostream>
using namespace std;
int main(){
    int n, val, res = 0;
    cin >> n;
    vector<int> coins{100, 50, 20, 10, 5, 2, 1};
    for(int i=0; i<n; i++){
        cin >> val;
        // 每次把当前面额的钱发到发不出为止
        for(auto &i:coins){
            res += val/i;
            val %= i;
        }
    }

    cout << res << endl;
    return 0;
}

第三题 扫雷

吐槽一下，这个备注 1 是不是用来迷惑人的
先写一个方法可以快捷算出周围雷的数量，然后根据逻辑更新一下即可

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int getNum(vector<vector<char>>& grid, int x, int y){
    int res = 0;
    // 两层 for 循环，来算出当前方格周围雷的数量
    for(int i = max(0, x-1); i < min(x+2, (int)grid.size()); i++)
        for(int j = max(0, y-1); j < min(y+2, (int)grid[i].size()); j++){
            if(i == x && j == y) continue;
            if(grid[i][j] == 'M') res++;
        }
    return res;
}
void helper(vector<vector<char>>& grid, int x, int y){
    // 判断边界
    if(x < 0 || y < 0 || x >= grid.size() || y >= grid[x].size()) return;
    // 当前为雷，或者已经走过了，退出
    if(grid[x][y] == 'M' || grid[x][y] != 'E') return ;
    int num = getNum(grid, x, y);
    if(num != 0) {
        // 当前周围有雷，只更新当前点，停止递归
        grid[x][y] = '0' + num;
        return ;
    }
    // 当前周围没有雷，更新当前点，继续递归
    grid[x][y] = 'B';
    helper(grid, x+1, y);
    helper(grid, x-1, y);
    helper(grid, x, y+1);
    helper(grid, x, y-1);
}
int main(){
    vector<vector<char>> grid(4,vector<char>(5));
    for(int i=0; i<4; i++)
        for(int j=0; j<5; j++)
            cin >> grid[i][j];
    int x, y;
    cin >> x >> y;
    // 当前是雷， 直接凉
    if(grid[x][y] == 'M') grid[x][y] = 'X';
    else{
        int num = getNum(grid, x, y);
        // 雷的数量为 0 时，才会进入 DFS
        if(num == 0) helper(grid, x, y);
        else grid[x][y] = '0' + num;
    }
    // 打印输出
    for(auto &it:grid){
        for(auto &i:it)
            cout << i;
        cout << endl;
    }
    return 0;
}