在刷题的单身狗很开心

题解

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2)

/ 注册

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

题解 | #[CQOI2007]矩形RECT#

本题需要去到矩阵里面进行dfs来求出所有的情况。当在矩阵里面走到边界的时候就是剪切结束的时候。那么剪切开始的时候就是在边界上。简单的来看就是从上下左右四个边上的点都走一遍且将走过的排除掉就是答案（定点当然不算）。这种简单粗暴地方式确实可以解，我也确实写了一遍。。。。。但是会超时。我们垃圾代码...

C++ 深度优先搜索

2023-10-23

1 296

题解 | #树上子链#

本题的树上子链的说法是我第一次见，树上子链指的是树上的任意一条链，换句话说就是树上任意两点中最长的那一个。但这题不是以长度定的，每个节点都有权值，要的是权值和最长的子链。所以我们对于某一个节点，选取儿子中最长和次长。然后加上节点本身就是答案了。但在这里面寻找最长和次长的方式很巧妙，先...

C++ 动态规划树形dp

2023-10-22

1 415

题解 | #二叉苹果树#

本题中很大不同点在于他给的是边的数值，而正常的树的问题是在节点上给值。那么我们采用边值下放点的做法，这样就是正常的树问题了。那么对于某一个节点来说它保留j个节点所得到的最大苹果树取决于这j个节点来自于左边子树多少，来自右边子树多少。又因为他自身就有一个节点所以状态转移方程为： &nbs...

C++ 动态规划树形dp

2023-10-22

1 382

题解 | #[USACO 2008 Jan G]Cell Phone Network#

本题是点的最小覆盖集问题，是一个树形dp问题。对于某一个节点来说他能通信来自于他父亲以及他儿子节点以及他自身。那么dp[n][3]表示某个节点三这种情况下的最小值。 0：靠父亲。 1：靠自己。 2：靠儿子。那么对于靠自己和靠父亲来说很简单的能写出状态转移方程： ...

C++ 动态规划数形dp

2023-10-20

2 356

题解 | #Strategic game#

本题翻译过来：在一棵书上每条边都必须有一个或多个士兵节点，求最少的士兵节点的个数。那么对于每一个节点来说有选与不选两种情况：dp[i][0/1]; 如果选的话儿子节点选与不选都行：dp[i][1] = 1 + (儿子节点累加和)min(dp[u][0], dp[u][1]); 如果不选的话儿子...

C++ 树状dp

2023-10-20

1 271

题解 | #没有上司的舞会#

题目中的意思翻译过来其实是在一颗数上相邻的节点只能选择一个，那么最大的和为多少。那么对于每一个节点来说就有选与不选两种状态：dp[i][0/1] 如果选的话那么以这个节点为根的子树最大和为：dp[i][1] = (f[i]+(所有子树和)dp[u][0]); 如果不选的话那么对于子树来说就有选...

C++ 动态规划树状dp

2023-10-19

1 288

题解 | #小G有一个大树#

对于某个节点来说，如果该节点删除那么就会形成他儿子节点全部独立成一棵树和他父亲节点的那棵树。那么状态转移方程：dp[i] = (total-f[i], (所有儿子节点最大的那个)f[u]) 对于求某个节点下有多少节点来说是一个简答树状dp问题。 f[i] = 1+(所有儿子节点)f[u]; ...

C++ 动态规划树状dp

2023-10-19

1 366

题解 | #大魔法师牛可乐#

本题得知道一个结论，如果序列里面的数的最大公约数为1的话就一定可以到达任意一个魔法阵。那么就对最大公约数进行动态规划。以每个数为外层循环。每一次都与前面有的或产生的数进行最大公约数的计算，然后更新某个数作为最大公约数所需要的花费即可。 //对于某一个数它的加入对原来产生的...

C++ 动态规划

2023-10-18

1 352

题解 | #宝藏猎人#

本题直接使用dfs，然后配合剪枝去接最好。直接dfs的去进行每一步当递归到最大的拥有宝藏的岛屿的下一个就可以宣布结束返回了。如何剪枝：本题中dfs是从前向后的传参形的记录当前的宝藏数量，那么如果某个岛屿第二遍被递归到的时候如果当前的宝藏数还没有之前的大。那么再递归下去就没有意义了。这...

C++ 动态规划深度优先搜索

2023-10-18

0 331

题解 | #货船#

使用二进制运算去优化01背包的循环过程可以。可以使用二进制去优化01背包的循环过程原因：在背包循环里面其实是针对于某一个物品判断如果他自身不取或者取能不能有一种是可以满足条件的。那么不取显而易见就是上一层循环的结果直接继承下来，取呢？取就得减去这个物品本身的重量，那么这个过程其实和序列整体左...

C++ 动态规划二进制优化01背包

2023-10-17

1 308