本周学习总结22.4.25-5.8：二叉树、并查集、和拓扑排序

5月5日晚的Codeforces Round #787 (Div. 3)打的不好，B题是挺简单的题，但一直卡在测试点2过不去。

A. Food for Animalshttps://codeforces.com/contest/1675/problem/A这个签到题挺简单，对我这种日语语种的都能一下子读懂题意。意思是有a袋狗粮，b袋猫粮，c袋都能吃的粮食，一共x只狗，y只猫。问每只小动物能否都吃到粮食，我直接用“穷举法”14个if把每个条件都列举了一遍，几分钟就提交上ac了。

#include
using namespace std;
int main() {
	//cout << "Hello World" << endl;
	int a, b, c, x, y, t;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		cin >> a >> b >> c >> x >> y;
		if (a + b + c < x + y) {
			cout << "NO" << endl;
			continue;
		}
		if (a >= x && b >= y) {
			cout << "YES" << endl;
			continue;
		}
		else if (c >= x + y) {
			cout << "YES" << endl;
			continue;
		}
		else if (a >= x && c >= y) {
			cout << "YES" << endl;
			continue;
		}
		else if (c >= x && b >= y) {
			cout << "YES" << endl;
			continue;
		}
		else if (a < x && b >= y) {
			if (a + c >= x) {
				cout << "YES" << endl;
				continue;
			}
		}
		else if (a >= x && b < y) {
			if (b + c >= y) {
				cout << "YES" << endl;
				continue;
			}
			
		}
		else if (a < x && b < y) {
			int aa = c + a - x;
			int bb = c + b - y;
			if (a+c >= x) {
				int cc = c - aa;
				if (cc + b >= y) {
					cout << "YES" << endl;
					continue;
				}
			}
			if (b+c >= y) {
				int cc = c - bb;
				if (cc + a >= x) {
					cout << "YES" << endl;
					continue;
				}
			}
		}
		cout << "NO" << endl;
	}
	
	return 0;
}

B. Make It Increasinghttps://codeforces.com/contest/1675/problem/B这个题就一下子把我卡住了，题意是：给一个数组，通过将数组中的元素除以二并且向下取整，直至数组严格从小到大递增为止，求变化的步数。其中给出一个【3，6，5】这个数组，步骤是：从第一个开始判断，到‘6’时，6比5大，就把6/2=3，此时数组为【3，3，5】，然后重新从头开始判断，发现第一个元素3等于第二个元素3，就把第一个元素3/2=1向下取整（由于是int类型，就不用对向下取整过多操作了），此时数组为【1，3，5】，严格递增，输出步骤次数2 。

我是这样实现的：用两个for循环（由于题中给出元素一共30个，循环多了也不会超时）当a[i]>=a[i+1]时，把a[i]/2，步骤计数器加一，然后重新从头判断，直至全部严格递增跳出循环输出步骤次数，此时还要判断，处理完的数组，如果有两个及以上的元素==0，应该输出-1，因为并没有严格递增，也就是说无法实现。

我觉得这样的思路应该不错，给出的也能跑对，就是总卡住在第二个测试点上，这一卡，就是一个多小时，后面的题还没做完时间就到了。

具体实现代码如下：

#include
using namespace std;
long long a[20000];
int t,n,num=0,m=0;
void chu(int x) {
	a[x] = a[x] / 2;
	num++;
}
int main() {
	cin >> t;
	for (int p = 1; p <= t; p++) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		if (n == 1) {
			cout << 0 << endl;
			num = 0;
			continue;
		}
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j < n; j++) {
					if (a[j] >= a[j + 1] && a[j] >= 1) {
						if (a[2] == 0) {
							cout << "-1" << endl;
							num = 0;
							goto fuck;
						}
						chu(j);
						j = 1;
						i = 1;
						k = 1;
					}
				}
			}
		}
		
		m = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i] == 0)m++;
		}
		if (m>=n-1&&n!=1) {
			cout << -1 << endl;
			fuck:
			num = 0;
			continue;
		}
		for (int i = 1; i < n; i++) {
			if (a[i] == a[i + 1]) {
				cout << -1 << endl;
				num = 0;
				continue;
			}
		}
		cout << num << endl;
		num = 0;
	}
}

这段代码是我第四次提交时的代码（一共提交了五次），我直接套了三层的for循环，我当时以为是循环的次数太少没有让它完全绝对严格递增，我的想法应该是错的。

P2256 一中校运会之百米跑https://www.luogu.com.cn/problem/P2256这个题是经典的并查集经典题目，给出一些人物的姓名，以及两个人在同一组的线索，其实将同一组的设同一个祖宗就行，然后问两个人是否在同一组的时候，就看看是否是同一个祖宗就可以了。就是有一个问题是最后只能得40分。

局域网 - 洛谷https://www.luogu.com.cn/problem/P2820看完最小生成树之后先做了这个题，题意是有n台计算机，计算机之间互相连接，求当网络中没有回路时，求此时的最小生成树的”畅通程度“，并与此前互相连接时的“畅通程度”求差。

这个题我也是看了好几篇题解才有思路的，首先把每段路按照畅通程度的大小排序，然后开始判断，如果起点和重点不是一个祖宗，就把这两个计算机连起来，计数器记上这两个计算机的畅通程度，然后将这两个计算机设为一个祖宗，然后继续判断，直至道路数量等于计算机数量为止，跳出循环。此时计数器的数就是最小生成树的“畅通程度”，把最初始的畅通程度减去计数器的畅通程度就是所求的答案了。

这个题我本来的思路是这样的：用结构体把道路的起点，终点，长度存储起来，再定义一个并查集，存储计算机的祖宗，把不是祖宗的长度最低的连接起来求总路程。思路是正确的，但是在代码实现的过程中一直卡在无法保证这个连接起来的是最小生成树。

#include
#include
#include
using namespace std;
struct lol{
    int from,to,money;
}l[20000];//存储起点终点和路程
int fuck[200002],n,k,i,j,m,ans=0,sum=0,x=0;
int findfuck(int x){
    if(fuck[x]!=x) return fuck[x]=findfuck(fuck[x]);
    else return x;
}//求祖宗
bool cmp(lol x,lol y){
    return x.money>n>>k;
    for(int i=1;i<=n;i++){
        fuck[i]=i;
    }
    for(int q=1;q<=k;q++){
        cin>>i>>j>>m;
        l[q].from=i;
        l[q].to=j;
        l[q].money=m;
        ans+=m;
    }
    int a,b;
    sort(l+1,l+1+k,cmp);
    for(int i=1;i<=k;i++){
        a=findfuck(l[i].from);
        b=findfuck(l[i].to);
        if(a==b)continue;
        sum+=l[i].money;
        fuck[a]=b;
        x++;
        if(x==n)break;
    }
    //Kuskal();
    cout<

本周做的主要都是并查集和拓扑排序的基础题，模板题，因为难题我也做不出来，P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)的解题思路让我对并查集有豁然开朗的了解，只要也就是查询祖宗，查询两个是不是同一个祖宗，让两个变成同一个祖宗，其实并查集的很多题都是这种思路，P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)找是否是亲戚的题，中心思想就是找两个人的祖宗是不是同一个人，其解题思路和模板并查集几乎一致。