牛客练习赛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;
}