y_din

题解

/ 注册

全部文章 / 题解（共6篇）

【树形dp】没有上司的舞会

这是一道经典的树形dp的题，转移状态实际上就两个1.2.其中v为x的儿子，然后就可以如下写代码了 #include <iostream> #include<stdio.h> #include<string> #include<string.h> #in...

2020-08-26

0 557

求一棵树的重心

思路：求平衡点，实际就是求一棵树的重心，我们只需要从上往下递归求出每一颗树的孩子的子树大小，模拟一个换根的过程，先把1当做根，记录下每一个节点的子树大小，在模拟换根的过程中，假设x为根，那么只需要记录一下它所有儿子的子树和以及n-其子树和中最大的值，然后取一个最小的最大值即可 #include &l...

2020-08-19

0 596

牛客算法周周练13 D 铺地毯

题意：有n张地毯，后铺的在最上面，给你一个点，问这个点最上面的地毯的编号是什么贪心方法：因为在最上面的地毯肯定在后面，所以我们只需要倒着找就可以了代码： #include<cstdio> #include<iostream> #include<algorithm>...

2020-07-01

0 712

牛客算法周周练13 C Shopping

题意：n件物品，里面有一些凳子，有m个购物车，每个物品有一个权值a[i]和b[i],分别表示价值大小和是否为凳子，若一个购物车里有凳子，则这个购物车里的价格最高的物品半价贪心方法：我们可以发现有凳子除了影响半价没有其他影响了，所以我们只需要考虑一下有几个可以半价就可以了，于是我们就可以只计算一下购物...

2020-07-01

0 654

牛客算法周周练13 A最小生成树

题意：有n个点的完全无向图，每个点i有一个点权a[i],每两个点之间之间的边权大小为这两个点的点权和贪心方法：找到一个最小的点，要使得最后的结果最小，只需要把这个点和其他所有点连接的边权和求出即可代码： #include <iostream> #include<cmath> ...

2020-07-01

0 637

港口

C:港口思路这个题是从差分数组的角度思考的。1.从差分数组的角度来看，每次对于区间[l,r]进行加操作就是对于差分数组cf[l]++,对cf[r+1]--;那么反过来思考，如果对原数组进行了区间[l,r]的加减操作，那么必然其差分数组一左一右分别进行了+1和-1的操作2.要使得原数组每个元素的大...

2020-05-26

0 724