嗯，今日更加努力！

---

题目描述

给出每个节点的两个儿子节点，建立一棵二叉树（根节点为 1），如果是叶子节点，则输入0 0。建好树后希望知道这棵二叉树的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。

最多有 10^6 个结点。

输入格式

无

输出格式

无

输入输出样例

输入 #1复制

7
2 7
3 6
4 5
0 0
0 0
0 0
0 0

输出 #1复制

4

这道题我题目看了挺久，才发现他是什么意思。

就是输入n，代表有接下来有n行输入，代表n个节点的左右子树节点，比如第2行的"2 7"就代表第1个节点的左节点右节点分别为"2"和"7"，第3行的"3 6"就代表第2个节点有左节点和右节点分别为"3 6"... ...于是到最后上面这个输入会形成这么一个树:

 因为题目要求要查询深度，那么我们只要遍历这棵树就行了，只要按照前序遍历的方法就可以遍历整颗树，最后令maxdepth = max(maxdepth, depth)就行了，具体详见代码。

#include <bits/stdc++.h>using namespace std;typedef long long ll;struct Tree {int L;int R;
} tree[1000002];int maxdepth = 1; //最大深度，包含第一层，默认为1void Fdepth(int node, int depth) //node表示node号节点，depth表示当前深度
{
//	cout << "Goto " << node << ", its depth is " << depth << ", its L and R is: " << tree[node].L << "、" << tree[node].R << endl;if(tree[node].L != 0) Fdepth(tree[node].L, depth + 1); //向左加深if(tree[node].R != 0) Fdepth(tree[node].R, depth + 1); //向右加深maxdepth = max(maxdepth, depth); //获得树的最大深度return;
}int main()
{ll n;cin >> n;for(ll i = 1;i <= n;i ++){cin >> tree[i].L >> tree[i].R;}Fdepth(1, 1);cout << maxdepth;return 0;
}

---

题目描述

我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：

所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。

输入格式

输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。

输出格式

输出可能的中序遍历序列的总数，结果不超过长整型数。

输入输出样例

输入 #1复制

abc                           
cba

输出 #1复制

4

说明/提示

无提示

这道题问中序遍历实际上就是问这棵树有多少种可能的组成方式，要先找规律。下面假设有这么一个树。

 

这棵树，它的前序遍历是 abdefc

后序遍历是efdbca

那么它有多少种情况呢？如果在不知道树长什么样的情况下的话，以上前序和后序遍历可以组成2种树，如下图：

可以发现，它们仅仅是"b"和"d"节点的关系发生了变化，因为"b"节点只有1个子节点"d"，所以有2种可能。这么推过来，我们还可以发现，如果一棵树有n个节点都是只有1个子节点的，那么这棵树在只知道前序后序遍历的情况下就有2^n种可能的组成方式。

有这个结论后，我们再来看看前序输入和后序输入:

abdefc

efdbca

这两对字符顺序刚好相反，而且两整串字符只有它们两对相反。

我们再来看看样例的输入输出:

abc abc 

cba cba 

4

根据我们的结论，答案是4, 与样例答案相同。

最后我们只要在推敲一下，就可以发现两对字符相反的，意味着其中一个节点只有一个子节点，根据我们上面的结论，我们就可以解出答案了。详见代码。

#include <bits/stdc++.h>using namespace std;int main()
{string a, b; //前序、后序cin >> a >> b;int lena = a.size();int lenb = b.size();long long poss = 1; //结果不超过长整型，这里定义long long就好了for(int i = 0;i < lena - 1;i ++){string cmpa = a.substr(i, 2); //在前序第i位提取2位
//		cout << "cmpa: " << cmpa << endl;for(int j = 0;j < lenb - 1;j ++){string cmpb = b.substr(j, 2); //在后序第j位提取2位
//			cout << "cmpb: " << cmpb << endl;if(cmpa[0] == cmpb[1] && cmpa[1] == cmpb[0]) //如果它们刚好相反{poss *= 2; //结果乘以2}}}cout << poss;return 0;
}

---

题目背景

小明在 A 公司工作，小红在 B 公司工作。

题目描述

这两个公司的员工有一个特点：一个公司的员工都是同性。

A 公司有 N 名员工，其中有 P 对朋友关系。B 公司有 M 名员工，其中有 Q 对朋友关系。朋友的朋友一定还是朋友。

每对朋友关系用两个整数 (Xi​,Yi​) 组成，表示朋友的编号分别为 Xi​,Yi​。男人的编号是正数，女人的编号是负数。小明的编号是 1，小红的编号是 −1。

大家都知道，小明和小红是朋友，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。

输入格式

输入的第一行，包含 4 个空格隔开的正整数 N,M,P,Q。

之后 P 行，每行两个正整数 Xi​,Yi​。

之后 Q 行，每行两个负整数 Xi​,Yi​。

输出格式

输出一行一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。

输入输出样例

输入 #1复制

4 3 4 2
1 1
1 2
2 3
1 3
-1 -2
-3 -3

输出 #1复制

2

说明/提示

对于 30% 的数据，N,M≤100，P,Q≤200；

对于 80% 的数据，N,M≤4×10^3，P,Q≤10^4；

对于 100% 的数据，N,M≤10^4，P,Q≤2×10^4。

这道题原本是比较难处理的，不过既然一个公司的都是同性，那么我们就不必要开两个父节点存储数组了，直接开1个就行，简便些。因为存在P、Q≤2×10^4，所以我们只要令1~20000为男性，20001~40000为女性就可以了。

因为是一夫一妻制，所以男性和女性能够组成的情侣数目就是其中是朋友的男性和女性数量的最小值。同样是并查集的方法去处理这道题，只要是朋友的，把它们的父节点都设置成一个就行了。

当合并操作完成后，最后遍历一下男性和女性的父节点数组，如果它们的父节点是1或20001的父节点（即是不是小明或小红的朋友），就把男性朋友或女性朋友的数量+1，最后取min(男性朋友数量，女性朋友数量)就行了。

不过这题也有特判，因为它的数据输入会有"1 1"、"-3 -3"这种自己是自己朋友的情况以及"1 2"、"2 1"、"-1 -2"、"-2 -1"这种已经是朋友关系却重复出现的情况，为了节省算力以及防止"未知错误"的发生，我们把它们特判掉。

详见代码。

#include <bits/stdc++.h>using namespace std;const int SUMNODES = 500000 + 1;int N, M, P;
int ParentNode[SUMNODES];
int Appeard[SUMNODES] = {0};
int mensum = 0, womensum = 0;void initialize() //初始化集合，各个人关系独立
{for(int i = 0;i <= 40000;i ++) //1~20000为男性，20001~40000为女性{ParentNode[i] = i; //设置他们的父节点为自己}
}int findparent(int num) //找到num号元素的父节点
{return num == ParentNode[num] ? num : (ParentNode[num] = findparent(ParentNode[num]));//如果父节点为自己，那么就返回自己//如果父节点不是自己，那么就找到它的上层父节点，直到找到最终父节点。
}void merge(int a, int b) //合并
{if(a == b) return; //防止1 1，-3 -3的情况int A, B;if(a < 0) A = -a + 20000;else A = a;if(b < 0) B = -b + 20000;else B = b;if(Appeard[A] && Appeard[B]){
//		cout << A << " and " << B << " are friends already!" << endl;return; //已经出现过的朋友搭配就不再继续了	} int x = findparent(A); //获得a号元素的父节点
//	cout << a << "的父节点为" << x << endl;int y = findparent(B); //获得b号元素的父节点
//	cout << b << "的父节点为" << y << endl;ParentNode[y] = x;if(a < 0 && x == findparent(1 + 20000)){
//		cout << a << " and " << b << " are friends" << endl; Appeard[A] = 1;Appeard[B] = 1;} else if(x == findparent(1)) {
//		cout << a << " and " << b << " are friends" << endl; Appeard[A] = 1;Appeard[B] = 1;	}}int main()
{initialize();int N, M, P, Q;cin >> N >> M >> P >> Q;for(int i = 0;i < P + Q;i ++){int a, b;cin >> a >> b;merge(a, b);}int MP = findparent(1);for(int i = 1;i <= 20000;i ++){if(findparent(i) == MP) mensum ++;}int WP = findparent(20001);for(int i = 20001;i <= 40000;i ++){if(findparent(i) == WP) womensum ++;}cout << min(mensum, womensum);return 0;
}

---

题目背景

A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述

给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）

输入格式

第1行两个正整数N,M

下面M行，每行3个正整数x,y,t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。

输出格式

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出−1，否则输出最早什么时候任意两个村庄能够通车。

输入输出样例

输入 #1复制

4 4
1 2 6
1 3 4
1 4 5
4 2 3

输出 #1复制

5

说明/提示

N≤1000,M≤100000

x≤N,y≤N,t≤100000

并查集。因为题目要求最小时间通车，那么我们就需要将输入的道路连接村庄以及修建时间建立结构体进行排序，令时间少的在前。

然后用变量标记已经连接的村庄数，但是注意，有N个村庄，那么连接数是N-1。在遍历过程中，只需要把未连接的村庄连起来即可，即把父节点不同的节点合并，使得它们的父节点相同。

最后遍历完成后，需要的时间就是最后修建的那一条路（排序过了）所需要的时间。如果最后的连接数不等于N-1（N个村庄），那么就意味着村庄之间还有没有连接的，就输出-1。

详见代码。

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int SUMNODES = 100000 + 1;ll N, M;
int ParentNode[SUMNODES];struct Roads {int v1, v2;int t;
} road[SUMNODES];void initialize(int N) //初始化集合，各个数字独立
{for(int i = 1;i <= N;i ++){ParentNode[i] = i; //设置它们的父节点为自己}
}int findparent(int num) //找到num号元素的父节点
{return num == ParentNode[num] ? num : (ParentNode[num] = findparent(ParentNode[num]));//如果父节点为自己，那么就返回自己//如果父节点不是自己，那么就找到它的上层父节点，直到找到最终父节点。
}void merge(int a, int b) //合并
{int x = findparent(a); //获得a号元素的父节点int y = findparent(b); //获得b号元素的父节点
//	cout << x << ", " << y << endl;ParentNode[x] = y;
}bool check(int a, int b) //检查是否再一个集合里
{int x = findparent(a);int y = findparent(b);if(x == y){return true;}else{return false;}
}bool cmp(Roads a, Roads b)
{return a.t < b.t;
}int main()
{cin >> N >> M;initialize(N);for(ll i = 1;i <= M;i ++){cin >> road[i].v1 >> road[i].v2 >> road[i].t;}sort(road + 1, road + M + 1, cmp);ll k = 0;int t;for(ll i = 1;i <= M;i ++){if(!check(road[i].v1, road[i].v2)) //如果道路不连通，就建这条路，令已链接村庄数+1{
//			cout << "Now build road " << i << " between " << road[i].v1 << " and " << road[i].v2 << endl;merge(road[i].v1, road[i].v2);k ++;t = road[i].t;}}if(k == N - 1) cout << t; //所有村庄连通else cout << "-1";return 0;
}

---

题目描述

在JSOI2005夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，又来不及去买了，怎么办呢？！

组委会把这个难题交给了LHC，LHC分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人拿到光盘后，其他人可以带着U盘之类的东西去拷贝啊！

可是，LHC调查后发现，由于种种原因，有些营员并不是那么的合作，他们愿意某一些人到他那儿拷贝资料，当然也可能不愿意让另外一些人到他那儿拷贝资料，这与我们JSOI宣扬的团队合作精神格格不入！！！

现在假设总共有N个营员（2<=N<=200），每个营员的编号为1~N。LHC给每个人发了一张调查表，让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然，如果A愿意把资料拷贝给B，而B又愿意把资料拷贝给C，则一旦A获得了资料，则B，C都会获得资料。

现在，请你编写一个程序，根据回收上来的调查表，帮助LHC计算出组委会至少要刻录多少张光盘，才能保证所有营员回去后都能得到夏令营资料？

输入格式

先是一个数N，接下来的N行，分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第i+1行表示第i个营员愿意把资料拷贝给那些营员的编号，以一个0结束。如果一个营员不愿意拷贝资料给任何人，则相应的行只有1个0，一行中的若干数之间用一个空格隔开。

输出格式

一个正整数，表示最少要刻录的光盘数。

输入输出样例

输入 #1复制

5
2 3 4 0
4 5 0
0
0
1 0

输出 #1复制

1

这道题看上去很简单。就是并查集嘛，只要把i号营员愿意给的人给合并就行了，最后只要找父节点是自己的节点计数就行。嗯，第一遍我是按照这个思路交上去了，发现WA了。

为什么呢？

我下载了测试点2的输入输出，发现我的答案是1，而标准答案是2。

为什么呢？

我仔细看了看它的输入，并且测试了几个自己的输入，终于发现了问题所在。如下面这段输入。

4
2 3 0
0
0
3 0

按照一般并查集的方法来说，最后会形成这么一个树:

但是它实际上的结构是这样的:

 

这是一种单向关系而非一般并查集的双向关系。

意思是：1号营员愿意给2号营员和3号营员资料，4号营员愿意给3号营员资料。

一般并查集下，答案为1，因为只有1棵树，但是实际上这棵树（最后实际上是有2棵树，前序遍历为12,43，不过这里这样理解我感觉好一点)是有多个根的，这里我称它们为源资料，而最后我们需要计数的就是源资料点个数，也就是父节点是它本身的个数。

那么如何做到这一点呢？

我去网上看了看关于并查集的资料，关于单向问题，有人给出了Floyed算法解决了单向问题，我们只需要一个二维数组，就叫它Permission[i][j]吧，意思是i给j的资料分享许可。那么在输入的时候，我们只要记下i号营员愿意给j号营员分享资料就行了。 最后可以通过遍历Permission数组，完成父节点归属设置，如果i愿意给j分享资料，那么我们就要把j的父节点设置为i，即j的资料源于i，i成为了j的源资料。最后我们把源资料点计数就行了。详见代码。

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int SUMNODES = 200 + 1;ll N;int ParentNode[SUMNODES];
int Permission[SUMNODES][SUMNODES];void initialize(int N) //初始化集合，各个数字独立
{for(int i = 1;i <= N;i ++){ParentNode[i] = i; //设置它们的父节点为自己}
}int findparent(int num) //找到num号元素的父节点
{return num == ParentNode[num] ? num : (ParentNode[num] = findparent(ParentNode[num]));//如果父节点为自己，那么就返回自己//如果父节点不是自己，那么就找到它的上层父节点，直到找到最终父节点。
}void merge(int a, int b) //合并
{//注意！这里不能再取它们的最高父节点，会造成错误！ParentNode[b] = ParentNode[a]; //b的父节点为a的父节点
}bool check(int a, int b) //检查是否再一个集合里
{int x = findparent(a);int y = findparent(b);if(x == y){return true;}else{return false;}
}
int main()
{cin >> N;initialize(N);for(int i = 1;i <= N;i ++){int a = 0;while(1){cin >> a;if(a == 0) break;Permission[i][a] = 1; //表示i愿意分享给a}}for(int i = 1;i <= N;i ++){for(int j = 1;j <= N;j ++){for(int k = 1;k <= N;k ++){if(Permission[i][j] && Permission[j][k]) //表示i营员愿意给j营员而j营员愿意给k营员{Permission[i][k] = 1;}}}}for(int i = 1;i <= N;i ++){for(int j = 1;j <= N;j ++){if(Permission[i][j]) merge(i, j); //k的父节点变为i的父节点，表示资源同源。}}int sum = 0;for(int i = 1;i <= N;i ++) //找到所有的源资料，并计数{if(findparent(i) == i){sum ++;}}cout << sum;return 0;
}

---

晚上在看《大话数据结构》只能说几乎又没有什么独到的理解... ...

---

今日份的题目完成了，明日一样！4道及以上！然后做更多的练习！