摘要：
原题链接：https://www.luogu.com.cn/problem/P4316 题意解读：有向图中，从一个点有k条出边，则从这k条边走的概率是1/k，求从起点到终点路径长度的数学期望。 解题思路： 1、数学期望 所谓数学期望，是一种均值，它是一个随机变量取值的加权平均，权重由该随机变量的概率 阅读全文
posted @ 2025-06-23 14:50
hackerchef
阅读(37)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P6772 题意解读：图中边权表示天数，点权表示受益，另外在不同的时间不同的点举办美食节，使得经过该点获得额外收益，求从1点T天后回到1点的最大收益。 解题思路： 由于T取值10^9，常规的DP即便O(n)级别也是不可行的， 阅读全文
posted @ 2025-06-21 23:42
hackerchef
阅读(51)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P1613 题意解读：求从1到n的路径最少包含多少个2^k。 解题思路： 如果对于从所有点经过2^k的路径能到达的点，都标记为可达且距离为1 那么从1到n最少包含多少个2^k，就是一个求最短路径的问题，数据量不大，可以用Fl 阅读全文
posted @ 2025-06-18 11:41
hackerchef
阅读(22)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P2014 题意解读：课程之间有的有依赖，有的可以直接选，问选不超过m个课程的最大学分和。 解题思路： 对于没有依赖的课程，假定一个课程0，设依赖课程0，课程0必选，且学分为0。 这样一来，要选择不超过m个课程则变成选m + 阅读全文
posted @ 2025-06-17 17:23
hackerchef
阅读(33)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P2015 题意解读：一棵树，边有权值，求从树中选择不超过q条边的最大权值和。 解题思路： 一、三维解法： 利用分组背包的思想，将一个节点的所有子树看做一组物品，枚举背包体积，再枚举某一组中所有的物品 1、状态表示 设f[i 阅读全文
posted @ 2025-06-17 14:48
hackerchef
阅读(54)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P1352 题意解读：在一棵树中选择一些点，使得拥有最大的权值和，限制条件是选择一个点时不能选择其父节点。 解题思路： 如果由于所选择节点的最大权值和是一个状态，而这个状态可以由所有子树的状态推导出来，因此可以从树形DP的角 阅读全文
posted @ 2025-06-16 16:36
hackerchef
阅读(47)
评论(0)
推荐(0)
浙公网安备 33010602011771号