牛客练习赛138

目录

A-小s的签到题

无注释版

有注释版

B-行列改写

无注释版

有注释版

C-树上替身追赶游戏

无注释版

有注释版

---

A-小s的签到题

无注释版

#include<bits/stdc++.h>
using namespace std;
struct f{char ch;int x;
}a[110];
bool cmp(f p,f q){if(p.x==q.x) return p.ch<q.ch;return p.x>q.x;
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].ch;}for(int i=1;i<=n;i++){string s;cin>>s;int p=s.find('/');for(int j=0;j<p;j++){a[i].x=a[i].x*10+s[j]-'0';}}sort(a+1,a+n+1,cmp);cout<<a[1].ch;
} 

有注释版

#include<bits/stdc++.h>  // 引入万能头文件，包含所有常用库
using namespace std;// 定义一个结构体 f，用于存储题目的信息
struct f {char ch;  // 题号（大写字母）int x;    // 通过人数
} a[110];     // 定义一个最多存 110 个题目的数组 a（实际上最多只需 26）// 比较函数，用于排序
bool cmp(f p, f q) {if (p.x == q.x) return p.ch < q.ch;  // 如果通过人数相同，按题号字母顺序小的排前return p.x > q.x;  // 否则，按通过人数多的排前
}int main() {int n;  // 题目数量cin >> n;  // 输入题目数量// 输入每道题的题号（大写字母）for (int i = 1; i <= n; i++) {cin >> a[i].ch;}// 输入每道题的通过人数/提交人数字符串for (int i = 1; i <= n; i++) {string s;cin >> s;int p = s.find('/');  // 找到 '/' 的位置，用于分割通过人数和提交人数// 解析 '/' 前面的部分（通过人数），转成整数存入 a[i].xfor (int j = 0; j < p; j++) {a[i].x = a[i].x * 10 + s[j] - '0';  // 把字符串数字一个个读出来转成整数}// 注意：提交人数其实不需要存，因为题目只关心通过人数}// 按比较函数 cmp 对题目数组排序sort(a + 1, a + n + 1, cmp);// 输出排在第一的题号（即通过人数最多，或字母序最小的那个）cout << a[1].ch;
}

B-行列改写

无注释版

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[100010],c[100010];
signed main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>c[i];}sort(a+1,a+n+1,greater<int>());sort(c+1,c+m+1,greater<int>());int ans=0;int l=1,r=1;int nn=n,mm=m;while(l<=n||r<=m){if(l<=n&&(r>m||a[l]>c[r])){ans+=a[l]*mm;nn--;l++;}else{ans+=c[r]*nn;mm--;r++;}}cout<<ans;
}

有注释版

#include<bits/stdc++.h>  // 引入所有标准库函数
using namespace std;
#define int long long  // 定义 int 为 long long，防止数据过大溢出int a[100010], c[100010];  // 定义两个数组，分别用于存储 r 和 c 数组的值signed main() {int n, m;  // n 表示行数，m 表示列数cin >> n >> m;  // 读入 n 和 mfor (int i = 1; i <= n; i++) {cin >> a[i];  // 读入 r 数组（每一行的值）}for (int i = 1; i <= m; i++) {cin >> c[i];  // 读入 c 数组（每一列的值）}// 将 r 数组按降序排列sort(a + 1, a + n + 1, greater<int>());// 将 c 数组按降序排列sort(c + 1, c + m + 1, greater<int>());int ans = 0;  // 最终答案（最大和）int l = 1, r = 1;  // 分别指向 r 和 c 当前处理的位置int nn = n, mm = m;  // nn 表示当前还未覆盖的行数，mm 表示当前还未覆盖的列数// 总共要进行 n+m 次操作while (l <= n || r <= m) {// 如果还剩下行，且列已经没有了，或当前行值更大 → 选择行覆盖if (l <= n && (r > m || a[l] > c[r])) {ans += a[l] * mm;  // 这一行的值将覆盖 mm 个列 → 加上 a[l] * mmnn--;  // 还剩下的行数减 1l++;   // 移动到下一行} else {// 否则选择列覆盖ans += c[r] * nn;  // 这一列的值将覆盖 nn 个行 → 加上 c[r] * nnmm--;  // 剩下的列数减 1r++;   // 移动到下一列}}cout << ans;  // 输出最终最大总和
}

C-树上替身追赶游戏

无注释版

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> e[100010];
int d[100010],ans;
void dfs(int x,int f){d[x]=d[f]+1;for(int i=0;i<e[x].size();i++){int t=e[x][i];if(t!=f){dfs(t,x);}}ans=max(ans,d[x]);
}
signed main(){int n,k;cin>>n>>k;for(int i=1;i<n;i++){int l,r;cin>>l>>r;e[l].push_back(r);e[r].push_back(l);}dfs(k,0);cout<<ans;
} 

有注释版

#include<bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;#define int long long  // 将 int 定义为 long long，防止数据溢出vector<int> e[100010];  // 邻接表，表示树的结构
int d[100010], ans;     // d[i] 表示节点 i 的深度；ans 记录最大深度// 深度优先搜索函数，用于计算每个点到起点的距离
void dfs(int x, int f) {d[x] = d[f] + 1;  // 当前节点的深度等于父节点深度 + 1for (int i = 0; i < e[x].size(); i++) {int t = e[x][i];  // 遍历当前节点的所有相邻节点if (t != f) {     // 避免走回父节点dfs(t, x);    // 递归处理子节点}}ans = max(ans, d[x]);  // 更新最大深度
}signed main() {int n, k;cin >> n >> k;  // n 是节点数，k 是游戏起点（Saki 和 Miku 的起始位置）for (int i = 1; i < n; i++) {int l, r;cin >> l >> r;// 无向图：把两个点互相加入邻接表e[l].push_back(r);e[r].push_back(l);}dfs(k, 0);  // 从起点 k 开始 DFS，0 代表虚拟的父节点cout << ans;  // 输出最大深度（也就是 Saki 最多能坚持的回合数）
}