当前位置：首页 > ai >正文

牛客练习赛138-题解

ai 2025/5/14 10:19:01

牛客练习赛138-题解

https://ac.nowcoder.com/acm/contest/109081#question

A-小s的签到题

题目描述

给定一个比赛榜单：

第一行是 n 个不同的大写字母，代表题号
第二行是 n 个形如a/b的字符串，表示每道题的通过人数和提交人数

找到通过人数最多的题目作为签到题。如果有多个，输出字母顺序最小的那个。

输入示例：

11
A B C D E F G H I J K
116/212 3/12 117/282 15/35 90/419 7/44 83/446 48/150 35/229 25/116 5/10

输出示例：

解题思路

读取题目编号和通过数据
解析每个题目的通过人数
找出通过人数最多的题目
如果有多个最大值，选择字母顺序最小的

算法讲解

使用模拟法直接处理：

遍历所有题目，提取a/b中的a值
维护当前最大通过人数和对应题目索引
遇到更大值更新，相同值则比较字母顺序

代码实现

#include <bits/stdc++.h>
using namespace std;
int n;
char ch[30];
void solve()
{cin >> n;int mmax = 0, idx = -1;for (int i = 0; i < n; i ++ ) cin >> ch[i]; // 读取题号for (int i = 0; i < n; i ++ ){string s;cin >> s;string s1;for (int i = 0 ; i < s.size(); i ++) // 提取通过人数{if (s[i] == '/') break;s1 += s[i];}int x = stoi(s1); // 转换为整数if (mmax < x) {    // 更新最大值mmax = x;idx = i;}}cout << ch[idx]; // 输出结果
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

B-行列改写

题目描述

给定两个数组：

长度为n的数组r
长度为m的数组c

初始一个全0的n×m矩阵，通过n+m次操作（每次选择一行或一列覆盖）使得最终矩阵元素和最大。每次操作：

行覆盖：选择未被选过的行i，将该行所有元素设为rᵢ
列覆盖：选择未被选过的列j，将该列所有元素设为cⱼ

输入示例：

3 3
1 2 3
1 2 3

输出：

题目分析

我们需要确定行覆盖和列覆盖的最优顺序，使得最终矩阵和最大。关键在于理解后覆盖的操作会覆盖之前操作的值。

解题思路

贪心策略：对于每个位置(i,j)，它的最终值由最后一次覆盖决定（行或列）
最优选择：对于行i，如果rᵢ > cⱼ，则应该最后执行行覆盖；否则最后执行列覆盖
数学推导：对每行i，计算有多少列cⱼ < rᵢ，这些列应该被行覆盖覆盖

算法讲解

排序：将列数组c排序，便于二分查找
前缀和：预处理列数组的前缀和，用于快速计算区间和
贪心计算：
- 对每行rᵢ，使用二分查找确定有多少列cⱼ < rᵢ
- 这些列贡献k×rᵢ（行覆盖）
- 剩余列贡献它们自身的和（列覆盖）

代码实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<i64> r(n), c(m);for (int i = 0; i < n; i++)cin >> r[i];for (int j = 0; j < m; j++)cin >> c[j];// 对列数组排序以便二分查找sort(c.begin(), c.end());// 计算列数组前缀和vector<i64> S(m + 1, 0);for (int j = 1; j <= m; j++) {S[j] = S[j - 1] + c[j - 1];}i64 totC = S[m]; // 所有列的和i64 ans = 0;for (int i = 0; i < n; i++) {i64 x = r[i];// 找到第一个大于x的列的位置int k = upper_bound(c.begin(), c.end(), x) - c.begin();// 前k列用行覆盖贡献k*x，剩余列用列覆盖贡献它们的和ans += (i64)k * x;ans += totC - S[k];}cout << ans;return 0;
}

C-树上替身追赶游戏

题目描述

给定一棵由 n 个节点和 n-1 条边组成的树，节点编号为 1∼n。Saki 和 Miku 初始都在节点 k。游戏分回合进行：

Saki 从当前节点 a 移动到相邻节点 b
Saki 在 b 的相邻节点中选择一个 c 放置替身
Miku 根据替身位置 c 移动

游戏在两者重合时结束。求 Saki 最多能进行多少回合。

输入示例：

输出示例：

题目分析

题目本质是求在树上，从起点 k 出发的最长路径长度。因为每回合Saki必须移动，且Miku会向替身位置移动，最优策略是Saki沿着最长路径移动。

解题思路

将树结构存储为邻接表
从起点 k 出发进行DFS/BFS遍历
记录从 k 出发的最长路径长度

算法讲解

DFS算法：

从起点开始递归遍历每个子节点
维护当前路径长度
遇到访问过的节点则回溯
最终得到最长路径长度

本题应用：

树的最长路径即树的直径
本题中最大回合数等于从起点出发的最长路径长度

代码实现

#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 1e5 + 10, M = N << 1;
int e[M], ne[M], idx, h[N];
int n, k, ans;
bool st[N];
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}// 从顶点k出发，最远能够到达的距离
void dfs(int u, int fa, int stp)
{for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (j == fa) continue;if (!st[j]) {st[j ] = 1;dfs(j, u, stp + 1);st[j ] = 0;}}ans = max(ans, stp);
}void solve()
{memset(h, -1, sizeof h);cin >> n >> k;for (int i = 0; i < n - 1; i ++){int a, b;cin >> a >> b;add(a, b);add(b, a);}dfs(k, -1, 1);cout << ans;
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}