Charles Frazier
A
题目描述:
对于一棵二叉树中任意两个节点 p 和 q, 小蓝鲸希望找到这样一个节点 t, 满足:
- p 和 q 都是 t 的后代 (一个节点可以是自己的后代)
- t 的深度尽可能大
现在请你编写程序帮助小蓝鲸找到满足上述条件的节点 t.
输入格式:
两行, 第一行是一列用空格隔开的整数, 代表二叉树的前序遍历, 其中空节点用-1表示. 第二行是 p 节点和 q 节点的值, 以空格隔开.
输出格式:
一个整数 n, 代表节点 t.
输入样例1:
3 5 6 -1 -1 2 7 -1 -1 4 -1 -1 1 0 -1 -1 8 -1 -1
5 4
输出样例1:
5
解释:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
分析: 5与4都是5的后代；5的深度比3大
尤其理解十一行，十二行。
#include <cstdio>
using namespace std;
bool jud(true);
int num(-1), t(0), p, q, str[100000];
bool find(){
if(jud){
num++;
int tmp = str[num];
if(num==t||tmp==-1)return false;
bool l=find(), r=find();
if((l&&r)||(tmp==p||tmp==q)&&(l||r)) { printf("%d", tmp); jud=false;}
return l||r||tmp==p||tmp==q;
}
return false;
}
int main(){
while(scanf("%d",str+t)!=EOF)t++;
t--;p=str[t];t--;q=str[t];
find();
return 0;
}
B
题目描述:
一天小蓝鲸早晨骑车去上课, 路上见到一个老伯正在摘果树上的果实, 其中有的刚刚成熟, 有的已经腐烂, 顿时想到了一个有关修剪果树的问题, 希望通过修剪果树得到一棵最好的果树. 因此, 他想到了如下的问题: 现有一棵果树, 上面共连有N颗果实, 共有N−1条枝干将果实连在一起, 并且未修剪时每颗果实是通过枝干连在果树上的. 每颗果实都有一个 “成熟指数” , 该数越大说明这颗果实越成熟；也有 “成熟指数” 为负数的, 说明这颗果实已经腐烂. 所谓 “修剪” , 意为: 去掉其中的一条枝条, 这样一棵果树就成了两棵, 扔掉其中一棵 “成熟指数” 小的, 保留 “成熟指数” 大的果树. 经过一系列 “修剪 “之后, 还剩下最后一棵果树 (也可能是只有一个果实) . **注: “修剪” 只能剪掉连接的枝干, 不能只摘下果实. ** 因此, 通过一系列 “修剪” (也可以什么 “修剪” 都不进行) , 使得剩下的那棵果树上所有果实的 “成熟指数” 之和最大, 我们称之为最好的果树.
输入格式:
第一行一个整数N(1≤N≤16000). 表示原始的那棵果树上共N颗果实. 第二行有N个整数, 第i个整数表示第i颗果实的成熟指数. 接下来N−1行每行两个整数a, b, 表示存在一条枝干连接第a颗果实和第b颗果实. **注: 为方便建树, 目前改成所有枝干为父亲指向孩子, 且第三行第一个节点为根节点. ** **注2: 每个节点都可以是根节点, 为了方便, 故将第三行的第一个节点设为根节点. **
输出格式:
一个数, 表示一系列 “修剪” 之后所能得到的 “成熟指数” 之和的最大值. 保证绝对值不超过2147483647.
输入样例:
7
-1 -1 -1 1 1 1 0
1 4
4 7
7 5
7 6
5 2
6 3
输出样例:
3
经典的递归方法！
#include <cstdio>
#define child 400
int ans=-100000000;
int N, x, y, *str, *f, **tree;
void find(int a, int b){
f[a] = str[a];
for(int i=1;i<=tree[a][0];i++){
int tmp = tree[a][i];
if(tmp!=b){
find(tmp,a);
if(f[tmp]>0)
f[a]+=f[tmp];
}
}
}
int main(){
scanf("%d",&N);
str = new int[N+1];
f = new int[N+1];
tree = new int*[N+1];
for(int i=1;i<=N;i++) { scanf("%d", str + i); tree[i]=new int[child]; tree[i][0]=0; f[i]=0;}
for(int i=1;i<N;i++) { scanf("%d%d", &x, &y); tree[x][++tree[x][0]]=y; tree[y][++tree[y][0]]=x;}
find(1,0);
for(int i=1;i<=N;i++)
ans=ans>f[i]?ans:f[i];
printf("%d",ans);
return 0;
}
C
题目描述:
小蓝鲸们得到了一串数字, 这串数字可以唯一的表示一棵二叉树, 其规则如下:
- 从这串数字的开始一直到最后, 依次是水平顺序遍历二叉树的各个节点的值(值不为0), 若二叉树非空节点的某个子节点为空, 则用0表示.
- 同时, 二叉树的各个节点按照在这串数字中出现的顺序编号, (从0开始).
例如[5,7,4,1,0,3,0], 对应如下的二叉树, 每个节点括号内是节点值, 括号外是节点编号.
0(5)
/ \
1(7) 2(4)
/ /
3(1) 4(3)
路径被定义为一条从任意节点出发, 通过边的连接, 到达任意节点的序列. 同一个节点在一条路径序列中至多出现一次. 一条路径至少包含一个节点, 且不一定经过根节点. 路径和是路径中各节点值的总和. 现在,给定这串数字的序列, 小蓝鲸需要构建出这棵二叉树, 并找到其中具有最大路径和, 且长度最短的路径. (题目数据保证符合条件的路径只有一条, 输出时节点编号小的路径端点在前, 如3->2->4和4->2->3代表相同的路径, 只输出3->2->4)
输入格式:
第一行输入一个整数: n, 表示数组的大小. 第二行输入 n 个整数, 为表示二叉树的数组.
输出格式:
输出k个整数, 代表最短的最大和路径.
输入样例1:
7
-10 9 20 0 0 15 7
输出样例1:
3 2 4
解释: 二叉树形为
0(-10)
/ \
1(9) 2(20)
/ \
3(15) 4(7)
最大和为15+20+7=42, 对应最大和路径只有一条, 为3->2->4 困难😓但十分有意义
#include <cstdio>
int N, a, p(0), point(0), ans(-100), ans_stp(10000), ans_type(0), rr[2];
struct node;
struct node *ans_node;
typedef struct node{
int val, num, where_get_help, stp;
node *l, *r;
explicit node():l(nullptr),r(nullptr),val(0),num(0),where_get_help(0),stp(1){}
void set(int v);
}node;
node str[60001];
void node::set(int v){
val=v,num=p;
if(v){p++;l = str+(++point), r = str+(++point);}
}
int find(node* node=str){
if (node->val==0) return 0;
int stp(1);
auto node1 = node->l, node2 = node->r;
auto tpp = node->val, val1 = find(node1), val2 = find(node2);;
if(val1>0) { tpp += val1; stp+=node1->stp;}
if(val2>0) { tpp += val2; stp+=node2->stp;}
if(tpp>ans||(tpp==ans&&stp<ans_stp)){
ans_node = node; ans_stp=stp; ans = tpp;
if((val1>0)&&(val2>0))ans_type=3;
else if(val1>0)ans_type=1;
else if(val2>0)ans_type=2;
else ans_type=0;
}
if(val1>val2&&val1>0) { node->stp+=node1->stp; node->where_get_help=1; return node->val+val1; }
else if(val2>val1&&val2>0) { node->stp+=node2->stp; node->where_get_help=2; return node->val+val2; }
else if(val1==val2&&val1>0) {
int tp1 = node1->stp, tp2 = node2->stp;
if(tp1<=tp2){node->stp+=tp1;node->where_get_help=1;return node->val+val1;}
else{node->stp+=tp2;node->where_get_help=2;return node->val+val2;}
}
else return node->val;
}
void print_1(int num, node* n){
printf("%d ",ans_node->num);
for(int i=0;i<num;i++){
printf("%d ", n->num);
if(n->where_get_help==1)n=n->l;
else if(n->where_get_help==2) n=n->r;
}
}
void print_vers(int num, node* n){
for(int i=0;i<num;i++){
rr[i] = n->num;
if(n->where_get_help==1)n=n->l;
else if(n->where_get_help==2) n=n->r;
}
for(int i=num-1;i>=0;i--)printf("%d ",rr[i]);
}
int main(){
scanf("%d",&N);
for(int i=0;i<N;i++){
scanf("%d",&a);
(str+i)->set(a);
}find();
node* nn = ans_node->l, *mm = ans_node->r;
if(ans_type==1)print_1(ans_stp-1,nn);
else if(ans_type==2)print_1(ans_stp-1,mm);
else if(ans_type==3){
auto t1=nn->stp, t2=mm->stp;
if(t1<=t2){
print_vers(t1,nn);
print_1(t2,mm);
}else{
print_vers(t2,mm);
print_1(t1,nn);
}
}else printf("%d", ans_node->num);
return 0;
}
D
题目描述:
小蓝鲸A和小蓝鲸B在玩捉迷藏的游戏. 他们的移动范围可以抽象成一颗有n个结点的树, 初始小蓝鲸A位于x位置, 小蓝鲸B位于y位置. 小蓝鲸们每个单位时间内都可以选择不动或者向相邻的位置转移, 那么最多经过多少个单位时间后, 小蓝鲸A可以追上小蓝鲸B (显然小蓝鲸A最终肯定可以追上小蓝鲸B的)? 假设小蓝鲸们都足够聪明.
输入格式:
输入第一行包含三个整数n, x, y, 分别表示树上的结点数量, 小蓝鲸A所在的位置和小蓝鲸B所在的位置. 接下来有n−1行, 每行两个整数u, v, 表示u号位置和v号位置之间有一条边, 即u号位置和v号位置彼此相邻.
输出格式:
输出仅包含一个整数, 表示小蓝鲸A追上小蓝鲸B所需的时间.
输入样例1:
5 1 2
2 1
3 1
4 2
5 3
输出样例1:
2
解释:
移动范围:
5
\
3
\
1
\
2
\
4
小蓝鲸B只能移动到4, 然后小蓝鲸A移动2步到4抓住小蓝鲸B
经典的追逐
#include "cstdio"
#define child 20
#define MAX 50001
int n,x,y,u,v,tree[MAX][child],d_x[MAX],d_y[MAX],ans(0);
void findx(int a, int b){
d_x[a] = d_x[b]+1;
int w = tree[a][0];
for(int i=1;i<=w;i++){
int c = tree[a][i];
if(c!=b)findx(c,a);
}
}
void findy(int a, int b){
d_y[a] = d_y[b]+1;
int w = tree[a][0];
for(int i=1;i<=w;i++){
int c = tree[a][i];
if(c!=b)findy(c,a);
}
}
int main(){
scanf("%d%d%d",&n,&x,&y);
d_x[0]=-1,d_y[0]=-1;
for(int i=0;i<n-1;i++){
scanf("%d%d",&u,&v);
tree[u][++tree[u][0]]=v;
tree[v][++tree[v][0]]=u;
}
findx(x,0);
findy(y,0);
for(int i=0;i<=n;i++){
if(d_y[i]<d_x[i])
ans<d_x[i]?ans=d_x[i]:0;
}printf("%d",ans);
}
E
题目描述
在二叉树家族中, 定义“堂兄弟”如下：如果两个节点的深度相同, 但是父节点不同, 则它们是一对堂兄弟. 现有一个二叉树家族, 其中每一个节点的值都不同. 输入小蓝鲸的节点值x和一位家族成员的节点值y, 判断这位家族成员是否为小蓝鲸的堂兄弟. 注意：本题需要使用二叉树数据结构完成.
输入格式
第一行：二叉树节点值的顺序表示, 以完全二叉树的形式给出 (即，空节点也会有子节点, 保证仍是空节点), 节点用空格隔开. 若为空节点, 则为‘#’. 1≤节点数≤100
1 2 3 # 4 # 5
第二行：小蓝鲸的节点值. 第三行：家族成员的节点值.
输出格式
true或false. true表示该家族成员是小蓝鲸的堂兄弟, false表示该家族成员不是小蓝鲸的堂兄弟. 行末无多余空格换行符.
输入样例1:
1 2 3 4
4
3
输出样例1:
false
你了解C++中对元组吗
//题目要求：必须使用树！
#include<iostream>
#include<sstream>
#include<tuple>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(): val(0), left(nullptr), right(nullptr) {}
};
TreeNode tree[101];
int x, y, i(0);
tuple <TreeNode*, int, bool> tx, ty;
string s;
void dfs(TreeNode* node, int depth, TreeNode* parent) {
if (!node) return;
if (node->val == x)
tx = make_tuple(parent, depth, true);
else if (node->val == y)
ty = make_tuple(parent, depth, true);
if (get<2>(tx) && get<2>(ty)) return;
dfs(node->left, depth + 1, node);
if (get<2>(tx) && get<2>(ty)) return;
dfs(node->right, depth + 1, node);
}
int main(){
getline(cin,s);
stringstream ss(s);
cin >> x >> y;
while(ss>>s){
if(s[0]!='#') tree[i].val = stoi(s);
if(i*2+1<101) tree[i].left = &tree[i*2+1];
if(i*2+2<101) tree[i].right = &tree[i*2+2];
i++;
}
dfs(tree, 0, nullptr);
if(get<1>(tx)==get<1>(ty) && get<0>(tx)!=get<0>(ty)) cout<<"true";
else cout<<"false";
}
F
题目描述
圣诞节前夕, 小蓝鲸和室友们决定给寝室的二叉圣诞树挂上灯烛和装饰品, 由于繁重的课业压力导致小蓝鲸没有足够的时间精力对圣诞树进行修剪, 树的枝杈略显杂乱. 以一种n=13个节点的圣诞树结构为例, 节点从1开始按层编号.
小蓝鲸和室友们决定, 只把树的边缘的节点挂上装饰品, 小蓝鲸所认为的边缘是指：从圣诞树的左侧或右侧向另一侧望去, 所能看到的所有未被挡住的节点. 对于图1的圣诞树, 需要装饰的边缘节点即为1、2、3、4、6、7、10、11、13. 小蓝鲸希望你能帮助他找出这些需要挂上装饰品的节点编号.
输入格式
第 1 行一个正整数 n, 表示圣诞树的节点总数. 满足 1≤n≤30. 第 2 到 n+1 行, 每行有两个整数. 第 i+1(1≤i≤n) 行的整数表示第 i 个节点的左右子节点编号, -1 代表该节点没有左节点或右节点.
输出格式
输出仅一行整数, 按照节点编号从小到大的顺序, 输出需要装饰的节点编号.
输入样例:
13
2 3
-1 4
5 6
7 8
9 -1
10 -1
-1 -1
11 -1
-1 -1
12 13
-1 -1
-1 -1
-1 -1
输出样例:
1 2 3 4 6 7 10 11 13
存入的是对应完全二叉树的坐标。关注t的意义以及处理。
#include<cstdio>
int num, a, b, t(2), mini, maxi, tree[31];
bool judge;
int main(){
scanf("%d", &num);
for(int i=1;i<=num;i++){
scanf("%d%d", &a, &b);
if(a+1) tree[a] = tree[i]*2 + 1;
if(b+1) tree[b] = tree[i]*2 + 2;
}
printf("1");
while(true){
mini = 100;
maxi = 0;
judge = false;
for(int i=1;i<=num;i++){
if((tree[i]+1)/t ==1){
if(!judge){mini = i; judge = true;}
maxi = i;
}
}
t <<= 1;
if(judge){
if(mini==maxi) printf(" %d", mini);
else printf(" %d %d", mini, maxi);
}else break;
}
}
G
题目描述
小蓝鲸想放松一下, 于是打算去著名的二叉树公园散步.
二叉树公园有n个景点, 某些景点之间由一条小路连接. 没错, 和你想的一样, 这个公园之所以叫“二叉树”公园, 就是因为这些小路将景点连成了一个二叉树. 所有景点的编号是0到n−1. 0号景点是二叉树公园的根节点. 所有小路的长度为1.
小蓝鲸打算从某一个景点进入公园散步, 散步完成后再从某一个景点离开公园. 她觉得二叉树非常优美, 因此对二叉树公园很好奇, 想每个景点都能散步到. 但是, 她也不想太累, 所以散步的总路程要最短.
她希望聪明的你能告诉她最短的路程是多少.
输入格式
第1行一个正整数n, 表示二叉树公园景点的个数. 第2到第n+1行, 每行有两个整数l和r, 用空格隔开. 第i+2行的l表示景点l是景点i的左儿子, r表示景点r是景点i的右儿子. 当l或者r为−1时, 表示这个儿子不存在.
输出格式
一行, 一个正整数, 表示小蓝鲸最短所需要走的路程.
输入样例
9
1 2
3 4
-1 -1
5 -1
-1 6
7 -1
-1 8
-1 -1
-1 -1
输出样例
10
等价：理解为什么求最长路径
#include<cstdio>
int num, a, b, tree[100001][2], maxi(0);
int find(int x){
if(x){
int l(find(tree[x][0])), r(find(tree[x][1])), stp(1+l+r);
if(stp>maxi) maxi = stp;
return l>r?l+1:r+1;
}else return 0;
}
int main(){
scanf("%d", &num);
for(int i=1;i<=num;i++){
scanf("%d%d", &a, &b);
tree[i][0] = a+1;
tree[i][1] = b+1;
}
find(1);
printf("%d", maxi+(num-maxi)*2-1);
}