5 条题解
-
21
这道题的解决思路如下:
- 构建树的数据结构:首先创建一个包含 n+1 个元素的向量,每个元素都是一个空的向量,用于表示树的结构。然后按照输入的父子节点关系,将每个子节点添加到对应父节点的向量中。
- 遍历树并统计孙子节点数量:从根节点开始,依次遍历树的每个节点。对于每个节点,迭代它的所有子节点,并统计每个子节点的孩子节点数量。累加所有子节点的孩子节点数量,即得到当前节点的孙子节点数量。
- 寻找孙子节点最多的节点:在遍历过程中记录当前最大的孙子节点数量和对应的节点编号。如果找到了孙子节点数量更大的节点,则更新最大数量和对应的节点编号。
- 输出结果:输出最大孙子节点数量和对应的节点编号。
示例代码已经给出,以下是对代码的解析:
- 首先读取输入的树的节点数量 n。
- 创建一个二维向量 tree,大小为 n+1,用于存储树的结构。
- 循环读取 n-1 条边的信息,将每个子节点添加到对应父节点的向量中。
- 初始化最大孙子节点数量为 0,最大孙子节点对应的节点编号为 1。
- 遍历整个树,对于每个节点,计算其孙子节点数量:
- 迭代当前节点的所有子节点,在子节点的向量中统计孩子节点的数量,并累加到当前节点的孙子节点数量上。
- 如果当前节点的孙子节点数量大于最大孙子节点数量,则更新最大孙子节点数量和对应的节点编号。
- 输出最大孙子节点数量和对应的节点编号。
#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<vector<int> > tree(n + 1); for (int i = 2; i <= n; i++) { int u, v; cin >> u >> v; tree[u].push_back(v); } int max_grandchildren_count = 0; int max_node = 1; for (int i = 1; i <= n; i++) { int grandchildren_count = 0; for (size_t j = 0; j < tree[i].size(); j++) { int child = tree[i][j]; grandchildren_count += tree[child].size(); } if (grandchildren_count > max_grandchildren_count) { max_grandchildren_count = grandchildren_count; max_node = i; } } cout << max_node << " " << max_grandchildren_count << endl; return 0; }
-
8
本题较为基础,只需要正常对该有根树进行存储,存储完每个节点后,按照节点编号循环枚举统计每个节点的孙子节点,找到孙子节点最多的节点编号及孙子节点的个数即可。
参考代码
//cnt统计孙子节点数量,ans记录最多的孙子节点数量,xh记录孙子节点最多的节点编号 int cnt = 0, ans = 0, xh; for (int i = 1; i <= n; i++) { cnt = 0; for (int j = 0; j < e[i].size(); j++) cnt += e[e[i][j]].size(); if (cnt > ans) { ans = cnt; xh = i; } }
-
1
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; //我还是这么写了,虽然感觉没啥用,但毕竟课上这么写 vector <int> e[MAXN];//只存子节点即可 int sum; int ans; int pos_ans = -1;//编号 void dfs(int u);//函数声明,如果把函数写前面就不用写 int main() { int n; cin >> n; for (int i = 1;i <= n - 1;i++) { int U,V; cin >> U >> V; e[U].push_back(V); } dfs(1); cout << pos_ans << " " << ans << "\n"; return 0; } void dfs(int u) { sum = 0; for (int i = 0;i < (int)e[u].size();i++) { sum += (int)e[e[u][i]].size();//这里必须强制转换 } if (sum > ans)//如果找到更优方案 { ans = sum; pos_ans = u; } else if (sum == ans)//如果两方案一样优 { pos_ans = min(pos_ans,u);//取更小一个的序号 } for (int i = 0;i < (int)e[u].size();i++)//呜呜,这里当时把0不小心打成了1,只有50分,害我检查了将近一个点 { dfs(e[u][i]);//遍历 } return; }
的的确确已经AC—–c++14(O2)
-
-28
题解没有完整的,我来替补^__^(背地十分无语) 感谢王浩冉的解题思路 下面正片开始 这道题的解决思路如下:
- 构建树的数据结构:首先创建一个包含 n+1 个元素的向量,每个元素都是一个空的向量,用于表示树的结构。然后按照输入的父子节点关系,将每个子节点添加到对应父节点的向量中。
- 遍历树并统计孙子节点数量:从根节点开始,依次遍历树的每个节点。对于每个节点,迭代它的所有子节点,并统计每个子节点的孩子节点数量。累加所有子节点的孩子节点数量,即得到当前节点的孙子节点数量。
- 寻找孙子节点最多的节点:在遍历过程中记录当前最大的孙子节点数量和对应的节点编号。如果找到了孙子节点数量更大的节点,则更新最大数量和对应的节点编号。
- 输出结果:输出最大孙子节点数量和对应的节点编号。 ok,正片结束,上代码!
#include <iostream> #include <vector> /*思路.1、构建树的数据结构:首先创建一个包含 n+1 个元素的向量,每个元素都是一个空的向量,用 于表示树的结构.然后按照输入的父子节点关系,将每个子节点添加到对应父节点的向量中. 2、遍历树并统计孙子节点数量: 从根节点开始,依次遍历树的每个节点.对于每个节点,迭代它的所有 子节点,共统计每个子节点的孩子节点数量.累加所有子节点的孩子节点数量,即得到当前节点的孙子节 点数量. 3、寻找孙子节点最多的节点:在遍历过程中记录当前最大的孙子节点数量和对应的节点编号.如果找到 了孙子节点数量更大的节点,则更新最大数量和对应的节点编号. 4、输出结果: 输出最大孙子节点数量和对应的节点编号. */ using namespace std; const int MAXN = 1005; int n, m; vector<int> e[MAXN];//创建一个二维向量 e,用于存储树的结构 int fa[MAXN]; int main() { cin >> n;//输入的树的节点数量n for (int i = 1; i<= n - 1; i++)//环 n1 条边的信息,将每个节点添加到对应父节点的向量中 { int u, v; cin >> u >> v; fa[v] = u; e[u].push_back(v); } int cnt = 0,ans = 0,xh;//初始化最大孙子节点数量为 0,最大孙子节点对应的节点编号为 0 //遍历整个树,对于每个节点,计算其孙子节点数量 for (int i = 1; i <= n; i++) { //选代当前节点的所有子节点,在子节点的向量中统计孩子节点的数量,并累加到当前节点的孙子 节点数量上 cnt = 0; for (int j = 0; j < e[i].size(); j++) cnt += e[e[i][j]].size(); //如果当前节点的孙子节点数量大于最大孙子节点数量,则更新最大孙子节点数量和对应的节点编 号 if (cnt > ans) { ans = cnt; xh = i; } } cout<< xh << " " << ans; }
- 1
信息
- ID
- 327
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- (无)
- 递交数
- 656
- 已通过
- 334
- 上传者