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;
}收白菜
发工资
扫雷
