Z_L_G

分类

总结(19) 训练赛(12) 题解(103)

/ 注册

全部文章（共19篇）

牛客多校04

赛时FB，补GI F 题意有n个宝藏，每个宝藏有自己的val，你能获得前k个同时，你还可以进行一些交换，每次交换消耗价值c 求解你可以获得的最大价值思路考虑将所有宝藏都换到最前面，取最高的k个，然后再加上把k个宝藏从第一个放到前k个的价值代码 #include <bits/...

广度优先搜索深度优先搜索

2025-08-01

0 9

算法入门-[SCOI2012]滑雪与时间胶囊

题意给定n个点，每个点有自己的高度，给定m条边，边总是由高的点指向低的点特别的，两个点一样高，就认为是双向边求出最多能到达的点的个数，以及到达这些点需要的最小距离思路先dfs一遍，确定哪些点能到类似于最小生成树，但是最小生成树需要保证边都是无向边，因为最小生成树加入一条边本质上是两...

最小生成树深度优先搜索

2025-07-13

0 17

算法入门-树学

题意一个树，n个结点，每个结点的深度是到根的距离，整棵树的价值是所有点的深度和求选择哪个点为根时可以使深度和最小思路让每一个点为根跑一遍dfs就可以维护出每个点的深度和整个树的深度和但是让每一个点跑一遍复杂度会爆炸能不能只跑一遍？如果只跑一遍，根变换怎么办对于一个选定根的树，如果...

深度优先搜索 dp

2025-07-09

0 14

算法入门-可爱の星空

题意多组数据每组数据给出一个图中点的个数n，链接任意一条边需要的代价是这个边所连的两个联通块的大小的差值，使这n个点联通所需的最小代价是多少思路贪心的思考，想让价值最小，每一步合并的两个块得大小接近最终都会合成一个联通图，逆序思考深搜即可代码 #include<bit...

深度优先搜索

2025-06-27

0 17

算法入门-树上子链

题意一颗有n个结点的树，每个结点具有权值，求解最长（权值最大）的一条子链思路对于某一个结点来思考，他能构成的最长子链无非下列集中情况之一包含他的最长链+最长的包含他一个儿子的最长链所有结点均为负值，最长子链自身的权值他自己的一条最长链（另一条全负）因此我们维护一个dp数组，...

树形dp dp 深度优先搜索

2025-05-19

0 48

算法入门-二叉苹果树(边权转点权)(补：两种做法)

题意对于一个有n个结点的二叉树，根的编号一定为1，每条边有权值求保留q条边时，最多能获得多少权值 tip:分析样例可以知道，这棵树的根是必须保留的，“剪枝行为”一定是保留根含有根的子树思路（法一）由于输入是无规律的输入每一条边，所以应当先建立起二叉树，从根开始深搜建树由于边权是较难处...

dp 树形dp 深度优先搜索

2025-05-16

0 44

算法入门-(USACO 2008 Jan G)Cell Phone Network(最小支配集)

最小支配集选择一个点，可以覆盖相邻的点，覆盖所有点所需最小选点题意给定一颗n个结点的树，求最小支配集思路考虑每一个点，他可能被支配的方式有：被父亲支配，选自己，被儿子支配，维护一个二维dp数组记录点和状态：自己：父亲：儿子：对于自己和父亲，状态方程很显然可以推出，对于...

dp 树形dp 深度优先搜索最小支配集

2025-05-16

0 39

算法入门-Strategic game(最小点覆盖)

最小点覆盖选择一个点，覆盖所有相邻边，最少选几个点能覆盖所有边题意给定一棵n个结点的树，选定一个结点后即可覆盖他的所有邻边，求覆盖所有邻边的最少选定结点数思路动态规划对于每一个结点，由于覆盖边，所以自己考虑选和不选两种情况，且父亲没选，自己就一定得选，父亲选了，自己就可选可不选...

dp 树形dp 深度优先搜索最小点覆盖

2025-05-15

0 34

算法入门-小G有一个大树

题意对于一棵树，我们希望找到一个点，使得删除这个点之后，最大子树的结点数最小以边的形式输入，输出被删除的点的编号和删除后最大子树的结点数思路考虑用无根树描述，对于树的某一个结点，删掉后，整棵树变为两部分这个结点的父亲所属的树这个结点的若干子树故另表示删除这个点后最大子树结点...

dp 树形dp 深度优先搜索

2025-05-14

0 42

算法入门-没有上司的舞会

题意给定一颗n个结点的树，结点编号1~n，每个结点有权值，一个点选择以后，它的父亲就不可以被选，输出能选出的最大权值思路对于每个点，都有选和不选两种情况，当一个点选的时候，所有的儿子都不能选，当一个点不选的时候，每个儿子取选和不选的最大值即可，维护一个二维dp数组，状态转移方程如下注...

dp 树形dp 深度优先搜索

2025-05-14

0 47