Z_L_G

分类

总结(9) 训练赛(6) 题解(68)

/ 注册

全部文章（共15篇）

算法入门-树上子链

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

树形dp dp 深度优先搜索

2025-05-19

0 23

算法入门-二叉苹果树(边权转点权)

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

dp 树形dp 深度优先搜索

2025-05-16

0 23

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

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

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

2025-05-16

0 19

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

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

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

2025-05-15

0 19

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

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

dp 树形dp 深度优先搜索

2025-05-14

0 18

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

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

dp 树形dp 深度优先搜索

2025-05-14

0 21

算法入门-宝藏猎人

题意共有0~30000编号的岛，有n个宝藏，你每次只能往编号大的方向走，走的步长只能是上一次走的步长+p（p=-1,0,1），第一步走了d，求最多能拿到多少宝藏思路本题应该使用dfs+剪枝是更好写的 dp 对于0~30000这个范围，从1开始走，最大的偏移量不超过300 即相较于第一步...

dp 深度优先搜索

2025-05-10

0 22

算法入门-Tree Decoration

题意以p(父亲),c(需要挂的最少装饰物个数),t(挂一个装饰物需要的时间)的形式输入每一个树上的节点。问满足每一个节点的装饰物需求最少需要多少时间思路对于叶子节点i，他上面至少悬挂c[i]个装饰物对于其它节点j，如果他的子节点累计挂的装饰物已经大于等于c[j]，则什么都不用做，如果...

深度优先搜索树

2025-04-14

0 28

算法入门-[SCOI2009]生日快乐

题意 x*y蛋糕，切成n块等面积的，要求最大块的(长边/短边)最小思路对于每一块，切的时候切的位置总为当前块长度或者宽度/当前块要切成的块数，这样才能保证每一块面积相等你也就是对于(x,y,n)横着切切的一定是x/n的倍数，并且若倍数为i，则一边应该且成i块，另一边应该切成n-i块于是...

深度优先搜索

2025-04-13

0 18

算法入门-[CQOI2007]矩形RECT

题意把一个a*b个小正方形组成的大正方形切成两块有多少种切法？思路爆搜，对于正方形a*b转化为点阵图坐标为[0,a][0,b] 其中(0,0)(a,0)(0,b)不能作为起点，对于每个起点，找可能的终点即可由于对称性，两条对边方案重合，所以只搜索一组邻边即可 DFS要从不在边上的点开始...

深度优先搜索

2025-04-13

0 25