幸识部分LCA
前言
最近遇见了两道题是关于LCA的，在此记录一下便于回溯。先是一题 Lowest Common Ancestor 是基于完美二叉树，然后是一题n叉树 LCA On N-ary Tree 。
提示：以下是本篇文章正文内容，下面案例赛时瞎写有点糙，仅供思路回溯。
一、LCA(最低公共祖先)定义
树上两个节点的LCA指的是该节点是这两个节点的祖先，并且与这两个节点之间的距离最短，应注意，该节点本身也被认为是其自己的祖先。链接：
For example, on the 3-ary tree the LCA of node 6 and node 3 is node 1
二、n元树普适代码
构树后发现n的k次对应的是下层改组的右边第二个数即最大为pow(n,k+1)+1;
由此可逆序向根回溯
原题题面
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
The N-ary tree is a tree that each node has exactly n child nodes.
You are given an N-ary tree with infinite nodes, each node is numbered from 1 to infinity according to the level order(from left to right, level by level).
The first 13 nodes on the 3-ary tree.
Given the number x and y of the two nodes, you have to calculate the lowest common ancestors(LCA) of these two nodes.
Definition of the lowest common ancestors(LCA): The LCA of two nodes on the tree refers to the node is the ancestor of these two nodes with the shortest distance to these two nodes, it should be noted that the node itself is also considered its own ancestor. For example, on the 3-ary tree the LCA of node 6 and node 3 is node 1.
输入描述:
The first line contains an integer t(1 <= t <= 10^5) the number of test cases.
Each test case contains three integers n,x,y(1≤n,x,y≤10 9) representing the tree is an n-ary tree and number of two nodes.
输出描述:
For each test case output a positive integer to represent the LCA of the given two nodes.
输入
4
1 2 3
2 4 6
3 6 3
10000 10000 10000
输出
2
1
1
10000
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,x,y,xf;
scanf("%d%d%d",&n,&x,&y);
if(n==1)//特判
{
printf("%d\n",min(x,y));
continue;
}
if(x==y)
{
printf("%d\n",x);
continue;
}
int t=max(x,y);//此处保证x>=y
y=min(x,y);
x=t;
xf=x;//初始化别忘 哭拿 1 WA
while(xf>=y)
{
if(x%n>1)xf=x/n+1;
else xf=x/n;//根据上文提供构建下层逻辑 求父节点
if(xf<=y)break;//找到或当x<y时跳出 以免x更新后<y
x=xf;
}
if(xf==y)
{
printf("%d\n",xf);
continue;
}
//在此只能保证x在y的下层或是同层 故逆序递推时应先更新x
while(x!=y)
{
if(x%n>1)x=x/n+1;
else x=x/n;
if(x==y)break;
if(y%n>1)y=y/n+1;
else y=y/n;
}
printf("%d\n",x);
}
return 0;
} 三、高精度二叉树代码
原题题面
时间限制：C/C++ 10秒，其他语言20秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
Perfect binary trees are one of the coolest structures that computer scientists study. They have a lot of properties that make them very nice to work with. One of the nicest properties is that they can just be described by a single integerngiving the depth of the tree. For instance, the perfect binary tree forn= 3 looks like:
In general, a perfect binary tree with depthnwill have exactly 2n+1 – 1 nodes, and can be numbered by following the pattern seen above (there are of course other ways to number the nodes of the tree, but this is the scheme we will use in this problem).
A common question that arises when dealing with trees is the query of the lowest common ancestor (commonly called LCA) of two nodes in the tree. Formally, the LCA ofxandyis the nodezof greatest depth in the tree such thatzis an ancestor ofxandy. Nodeais an ancestor of nodecifcexists in the sub-tree rooted at nodea. Notice that 1 is trivially a common ancestor of any two nodes in the tree, but is not always thelowestcommon ancestor. For instance, the common ancestors of nodes 7 and 12 are 1 and 3, and 3 is the LCA since it is the node of greatest depth. The LCA of 2 and 13 is node 1, and the LCA of 5 and 11 is node 5. The definition of LCA guarantees that the LCA of any two nodes will always be unique.
The Problem:
Given two nodes in the tree using the numbering scheme shown above, determine the LCA of the two nodes.
输入描述:
Input will begin with apositive integer,T≤ 2∙106,indicating the number of test cases. Thiswill be followed byTtest cases, each on a separate inputline. Each test case will contain twospace separated integers,XandY, represented in hexadecimal.XandYwill each contain at most 1000characters from the set {0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}, where a-frepresent 10-15, respectively. You are todetermine the LCA ofXandY.
Note: The hexadecimal (base 16) numberdndn-1···d1d0 is converted to a decimal number (base 10) by the followingformula:d0·160 +d1·161 + ··· +dn-1·16n-1 +dn·16n.
输出描述:
For each case, output a singleline:
Case#x:y
wherexis the case number beginning with 1, andyis the LCA in hexadecimal with no leading 0’s. Leave a blankline after the output for each testcase.
输入
7
7 c
2 d
b 5
10 11
a020fac a030ccf
12afcdb 12afcdc
100000000 fffffffff
输出
Case #1: 3
Case #2: 1
Case #3: 5
Case #4: 8
Case #5: 501
Case #6: 255f9b
Case #7: 1
这题转成二进制画这棵树能找到规律。前面的n叉树也感觉有些许规律可惜没找到能切入的点。
画成一颗二进制树后发现左子叶为后缀添0，右子叶为后缀添1。故可比较去除前导零后的前缀重合部分得到其 LCA . 亦是因此可转换为字符串处理。
AC代码：
#include<bits/stdc++.h>
using namespace std;
char x[1001],y[1001];
char ex[4001],ey[4001],da[4001],das[1001];
int main()
{
int t;
scanf("%d",&t);
int c=1;
while(t--)
{
scanf(" %s%s",x,y);
memset(da,0,sizeof(da));
memset(ex,0,sizeof(ex));
memset(ey,0,sizeof(ey));
memset(das,0,sizeof(das));
int lenx=strlen(x),leny=strlen(y),k=0;
for(int i=0;i<lenx;++i)
{
for(int t=0;t<4;++t)
{
if(x[i]>='0'&&x[i]<='9')
{
if(x[i]>=pow(2,3-t)+'0')
{
ex[k++]='1';
x[i]-=pow(2,3-t);
}
else ex[k++]='0';
}
else
{
ex[k++]='1';
x[i]=x[i]-'a'+'2';
}
}
}
k=0;
for(int i=0;i<leny;++i)
{
for(int t=0;t<4;++t)
{
if(y[i]>='0'&&y[i]<='9')
{
if(y[i]>=pow(2,3-t)+'0')
{
ey[k++]='1';
y[i]-=pow(2,3-t);
}
else ey[k++]='0';
}
else
{
ey[k++]='1';
y[i]=y[i]-'a'+'2';
}
}
}
int sx=0,sy=0;
int lenex=strlen(ex),leney=strlen(ey);
for(int i=0;i<lenex;++i)
{
if(ex[i]!='0')
{
sx=i;
break;
}
}
for(int i=0;i<leney;++i)
{
if(ey[i]!='0')
{
sy=i;
break;
}
}
int fn=min(lenex-sx,leney-sy);
int f=0;
for(int i=0;i<fn;++i)
{
if(ex[sx+i]!=ey[sy+i])
{
f=i;
break;
}
}
if(f==0)f=fn;
for(int i=0;i<f;++i)da[i]=ex[sx+i];
int lenda=strlen(da);
k=0;
int qd=(4-(lenda-4*(lenda/4)))%4;
for(int i=0;i<lenda;i=i+4)
{
int sum=0;
if(i==4)i=i-qd;
if(i==0)
{
for(int t=0;t<4-qd;++t)
{
if(da[i+t]=='1')sum=sum*2+1;
else sum=sum*2;
}
}
else
{
for(int t=0;t<4;++t)
{
if(da[i+t]=='1')sum=sum*2+1;
else sum=sum*2;
}
}
if(sum>=0&&sum<=9)das[k++]=sum+'0';
else if(sum==10)das[k++]='a';
else if(sum==11)das[k++]='b';
else if(sum==12)das[k++]='c';
else if(sum==13)das[k++]='d';
else if(sum==14)das[k++]='e';
else if(sum==15)das[k++]='f';
}
printf("Case #%d: %s\n\n",c,das);
++c;
}
return 0;
} 最后码的一个模拟时间有点紧有未简化的地方。
投递美团等公司10个岗位