摘要：
P3629 [APIO2010] 巡逻 大意 给定一棵有 \(n\) 个节点的树，巡警车从 \(1\) 号节点出发遍历所有边后返回，每条边需经过两次，总距离为 \(2*(n-1)\)。现可新建 \(K\) 条边\((k = \{ 1, 2\})\)，要求新建的每条边必须恰好经过一次，求规划新建边的方 阅读全文
posted @ 2025-12-15 21:49
To_Carpe_Diem
阅读(3)
评论(0)
推荐(0)
摘要：
[Atcoder]F - Road of the King 大意 有一个人在 \(1\) 号点要进行 \(m\) 次移动，终点不必是 \(1\) 号点，假设第 \(i\) 次从 \(u\) 移动到 \(v\)，那么在 \(u\) 与 \(v\) 之间连一条有向边。 问有多少种操作序列能满足：最终 \ 阅读全文
posted @ 2025-12-14 21:52
To_Carpe_Diem
阅读(10)
评论(0)
推荐(0)
摘要：
P5666 [CSP-S 2019] 树的重心 大意 删去树中每条边，树分裂为两个子树，求所有边对应的两子树重心值之和的总和。 思路 首先考虑 \(\mathcal{O}(n ^ 2)\) 的解法。 枚举每条边，然后分别统计左右子树的重心，然后想加即可。 然后考虑优化，显然我们的复杂度浪费在了找重心 阅读全文
posted @ 2025-12-13 17:32
To_Carpe_Diem
阅读(8)
评论(0)
推荐(0)
摘要：
[Non]树上乘法 大意 给定若干次操作，每次将 \(u \to v\) 的路径上的点的点权值都乘上 \(k\)，最终求最大的边的编号。 思路 显然，你一直乘法一定会炸，对于加法运算，我们可以转化为加法与减法进行差分，对于乘法，我们是否可以考虑转为加法呢？答案是可以，转化为对数运算不就行了吗，每次加 阅读全文
posted @ 2025-12-12 23:09
To_Carpe_Diem
阅读(5)
评论(0)
推荐(0)
摘要：
P3258 [JLOI2014] 松鼠的新家 大意 给多次修改，\(u, v\)，每次将 \(u \to v\) 的路径上的点权加 \(1\)，求最终每个点的点权值。 思路 显然树上差分。 定义 \(d_i\) 表示从 \(i\) 到根的路径上点权和，那么 \(u \to v\) 就只需要 \(d_ 阅读全文
posted @ 2025-12-12 22:58
To_Carpe_Diem
阅读(3)
评论(0)
推荐(0)
摘要：
[Non]二叉苹果树 大意 给定需要保留的树枝数量，求出最多能留住多少苹 果。苹果长在树枝上。 思路 这个题目和选课最大的不同在于其需要累加的贡献在边上，因此我们依旧设 \(f_{u, j}\)，则有转移方程如下： \[f_{u, j} = \max(f_{u, j}, f_{u, j - k - 阅读全文
posted @ 2025-12-12 22:47
To_Carpe_Diem
阅读(2)
评论(0)
推荐(0)
摘要：
P2014 [CTSC1997] 选课 大意 有些学科 \(i\) 有先修课 \(fa\) 这些课程形成了一个树形结构，问选 \(m\) 门课所能达到的最大的学分。 思路 考虑树上背包。 我们定义 \(f_{u,j}\) 表示在 \(u\) 子树内选 \(j\) 门课的最大学分，类似我们的背包，我们 阅读全文
posted @ 2025-12-12 22:34
To_Carpe_Diem
阅读(6)
评论(0)
推荐(0)
摘要：
CF877E - Danil and a Part-time Job 大意 这个题的要求就是每次将一个子树内的灯，由 \(0\) 变 \(1\)，由 \(1\) 变 \(0\)，查询一个子树内亮着的灯的个数。 思路 首先，如果学过树剖应该很难不忍住把这颗树剖分之后变成序列，将这颗树在序列上维护，但是 阅读全文
posted @ 2025-12-12 22:03
To_Carpe_Diem
阅读(9)
评论(0)
推荐(0)
摘要：
CF482B - Interesting Array 大意 你需要构造一组解，满足给定的不同要求，每次的要求是 \(l, r, x\)，必须保证 \(a_l \& a_{l + 1} \dots \& a_{r - 1} \& a_r = x\)。 思路 考虑用线段树构造。 对于这个题目，我们首先想 阅读全文
posted @ 2025-12-12 21:52
To_Carpe_Diem
阅读(8)
评论(0)
推荐(0)
摘要：
P3740 [HAOI2014] 贴海报 大意 每次用一个新数覆盖一段区间，最后问区间上有几种不同的数字。 思路 首先考虑用线段树做。 发现数据范围很大，但是实则不需要啊，因为我们的海报的数量一定，可以考虑离散化去重，然后用线段树做。 每次更改一段区间的话，采用标记延迟下传的方式，如果在目标区间就先 阅读全文
posted @ 2025-12-12 21:44
To_Carpe_Diem
阅读(3)
评论(0)
推荐(0)
浙公网安备 33010602011771号