2023-04-10 14:54 已编辑 中国科学院大学 C++
关注
小红书 4.9 实习笔试第一题
笔试第一题一看就不会输入输出了，到现在都没用树把这题实现，晚上采用哈希和深度优先搜寻实现了，大佬知道怎么用树实现可以发给我看看
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<int,vector<int>> map;
int dfs(int n)
{
if(map[n].size()==0) return 1;
else
{
if(map[n].size()==1)
{
return 1+dfs(map[n][0]);
}
if(map[n].size()==2)
{
return 1+dfs(map[n][0])+dfs(map[n][1]);
}
}
return 0;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
map[b].push_back(a);
}
vector<int> res(n+1,0);
for(int i=1;i<n+1;i++)
{
cout<<dfs(i)<<' ';
int a=dfs(i);
int b=n-dfs(i);
int cha;
if(a-b>0)
{
cha=a-b;
}
else
{
cha=b-a;
}
res[cha]++;
}
cout<<endl;
for(int i=0;i<n;i++)
{
if(res[i]!=0)
{
cout<<i<<' '<<res[i];
}
}
return 0;
}
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<int,vector<int>> map;
int dfs(int n)
{
if(map[n].size()==0) return 1;
else
{
if(map[n].size()==1)
{
return 1+dfs(map[n][0]);
}
if(map[n].size()==2)
{
return 1+dfs(map[n][0])+dfs(map[n][1]);
}
}
return 0;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
map[b].push_back(a);
}
vector<int> res(n+1,0);
for(int i=1;i<n+1;i++)
{
cout<<dfs(i)<<' ';
int a=dfs(i);
int b=n-dfs(i);
int cha;
if(a-b>0)
{
cha=a-b;
}
else
{
cha=b-a;
}
res[cha]++;
}
cout<<endl;
for(int i=0;i<n;i++)
{
if(res[i]!=0)
{
cout<<i<<' '<<res[i];
}
}
return 0;
}
全部评论
STX5
电子科技大学 golang
谁说这是二叉树了。。。
牛客973607955号 楼主
楼主 中国科学院大学 C++
题目描述：
输入一棵树 T，你需要删除一条边，这棵树会被分成A 和 B 两棵树。你需要让两部分的节点数的差的绝对值| |A|-|B| |尽可能小。输出最小的| |A|-|B| |和最优方案的数量。
输入描述
第一行一个整数 n表示节点的数量，节点从1 到 n编号。
接下来n-1行每行两个正整数 s t，表示s的父亲是t。
输入保证是一棵树。
对于所有数据 1<=n<=100000。
输出描述
输出一行，两个整数，用空格分开，分别表示最优解和最优方案数。
样例输入
3
2 1
3 1
样例输出
1 2
*/
cs1033
门头沟学院 数据库工程师
从根节点开始递归求出每个子树的节点个数，然后就好做了。
相关推荐
Lorn的意义：1.你这根本就不会写简历呀，了解太少了
2.你这些项目经历感觉真的没啥亮点啊，描述的不行，重写书写一下让人看到核心，就继续海投
注意七八月份ofer还是比较多的，越往后机会越少，抓住时机，抓紧检查疏漏，加油
查看图片 点赞 评论 收藏
分享
查看30道真题和解析