get到新知識，心情愉悅。
先看先序排列
P1030 [NOIP2001 普及組] 求先序排列https://www.luogu.com.cn/problem/P1030題目描述
給出一棵二叉樹的中序與后序排列。求出它的先序排列。（約定樹結(jié)點用不同的大寫字母表示，且二叉樹的節(jié)點個數(shù) ≤8）。
輸入格式
共兩行，均為大寫字母組成的字符串，表示一棵二叉樹的中序與后序排列。
輸出格式
共一行一個字符串，表示一棵二叉樹的先序。
輸入輸出樣例
輸入 #1復制
重慶分公司
重慶分公司
BADC
BDCA輸出 #1復制
ABCD【題目來源】
NOIP 2001 普及組第三題
思路：在草稿紙上多次手工遍歷，找出由中后序排列->先序排列的規(guī)律，先從后序最后一個字母（這就是根）開始A，在中序知道對應的字母，將中序分成倆部分，依據(jù)中序的倆部分，將后序分成倆部分，左邊一部分是A的左子樹，右邊一部分是A的右子樹。以此類推。。。先序為根左右，所以先把根輸出，然后遞歸左半然后右半。
代碼實現(xiàn)：
#includeusing namespace std;
void DLR(char *m,char *b,int l,int r,int i,int j)
{
if(i==j)
{
printf("%c",b[j]);
return;
}
for(int k=l;k<=r;k++)
{
if(m[k]==b[j])
{
printf("%c",b[j]);
if(k-1>=l) DLR(m,b,l,k-1,i,i+(k-1-l));
if(k+1<=r) DLR(m,b,k+1,r,j+k-r,j-1);
break;
}
}
}
int main()
{
char m[30];
char b[30];
cin>>m>>b;
int len=strlen(m);
DLR(m,b,0,len-1,0,len-1);
return 0;
}
//ABEDFCHG
//AEFDBHGC 新知識:并查集P3367 【模板】并查集https://www.luogu.com.cn/problem/P3367
并查集，合并與查詢，是一種樹結(jié)構(gòu)。原來判斷兩個對象之間的關(guān)系，有關(guān)系和沒關(guān)系。無法得出具體關(guān)系。
通過數(shù)組parent[x]=x_father來模擬兩個元素之間的結(jié)點與孩子的關(guān)系，x的結(jié)點是x_father。
比如如果要合并1和2所在的集合，就要把1和2所在的那棵樹的根找出來（find），然后將一個根接在(connect)另一個根上面，一個為結(jié)點，一個為子樹。
題目描述
如題，現(xiàn)在有一個并查集，你需要完成合并和查詢操作。
輸入格式第一行包含兩個整數(shù)N,M?,表示共有?N?個元素和?M?個操作。
接下來?MM?行，每行包含三個整數(shù)?Zi,Xi,Yi??。
當?Zi=1 時，將Xi??與Yi??所在的集合合并。
當 Zi?=2?時，輸出 Xi??與Yi??是否在同一集合內(nèi)，是的輸出?Y；否則輸出?N。
對于每一個 Zi?=2?的操作，都有一行輸出，每行包含一個大寫字母，為?Y或者?N。
輸入 #1復制
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4輸出 #1復制
N
Y
N
Y對于30%?的數(shù)據(jù)，N≤10，M≤20。
對于 70%?的數(shù)據(jù)，N≤100，M≤103。
對于 100%?的數(shù)據(jù)，1≤N≤104，1≤M≤2×105，1≤Xi?,Yi?≤N，Zi?∈{1,2}。
代碼實現(xiàn)：
#includeusing namespace std;
int find_root(int x,int *parent)
{
int x_root=x;
while(parent[x_root]!=0)
{
x_root=parent[x_root];
}
return x_root;
}
int connect(int x,int y,int *parent)
{
int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
if(x_root==y_root)
{
return 0;
}
else
{
parent[x_root]=y_root;
return 1;
}
}
int main()
{
int parent[10000+5]={0};
int Z,M,N;
cin>>N>>M;
int x,y;
while(M--)
{
cin>>Z>>x>>y;
if(Z==1) connect(x,y,parent);
else
{
if(find_root(x,parent)==find_root(y,parent)&&find_root(x,parent)!=0)
{
printf("Y\n");
}
else
{
printf("N\n");
}
}
}
return 0;
} 由于這里在合并的時候總是，左邊那個集合連上右邊那個集合，會導致樹的深度過長，在find的時候會花費額外的時間，以至于提交結(jié)果時間超限
所以要將深度小的接在深度長的上面，就需要多定義一個數(shù)組deep?來存儲深度
#includeusing namespace std;
int find_root(int x,int *parent)
{
int x_root=x;
while(parent[x_root]!=0)
{
x_root=parent[x_root];
}
return x_root;
}
int connect(int x,int y,int *parent,int *deep)
{
int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
if(x_root==y_root)
{
return 0;
}
else
{
if(deep[x_root]>deep[y_root])
{
parent[y_root]=x_root;
}
else if(deep[y_root]>deep[x_root])
{
parent[x_root]=y_root;
}
else
{
parent[y_root]=x_root;
deep[x_root]++;
}
return 1;
}
}
int main()
{
int parent[10000+5]={0};
int deep[10000+5]={0};
int Z,M,N;
cin>>N>>M;
int x,y;
while(M--)
{
cin>>Z>>x>>y;
if(Z==1) connect(x,y,parent,deep);
else
{
if(find_root(x,parent)==find_root(y,parent)&&find_root(x,parent)!=0)
{
printf("Y\n");
}
else
{
printf("N\n");
}
}
}
return 0;
} AC，不過誰能告訴我這個N有什么用？？？？滿臉疑惑
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
