dyc2022's Blog

摘要： 更差的阅读体验 假设树的点数为 \(n\)，询问数量为 \(q\)。 首先考虑一个复杂度和度数有关的做法。 这个是比较简单的。假设一个广义的 \(sz_u\) 表示一次询问的时候 \(u\) 子树在 \([l, r]\) 的点数。那么一次询问的答案就是，\(u\) 子树内的点对数量，减去 \(u\) 阅读全文

摘要： 更差的阅读体验 我们发现一棵树删掉一个点之后会在删掉点的位置形成一个团，这很坏。我们希望还能形成一棵树。 所以我们考虑对这个图建圆方树。 我们以 \(n\) 为根，这样这个点不会被删掉。然后假设方点 \(u\) 的儿子个数为 \(s_u\)。 考虑题目要我们数的三元组 \((a, b, c)\) 的 阅读全文

摘要： 更差的阅读体验 圆方树入门题。听讲了四次才会做。 假设 D 是 \(0\)，d 是 \(1\)。先把问题转化为求不合法的方案数，也就是路径只经过一种边权的方案数。 先考虑起点和终点在同一个点双的情况。假设当前点双的大小为 \(sz\)。如果这个点双只有一种颜色，那么显然在这个点双内部怎么走都是不合法 阅读全文

摘要： 更差的阅读体验 这也太难了，根本不会啊。 首先把贡献为 \(-1\) 的改成 \(0\)，为 \(n\) 的改成 \(n-1\)，这样就不用特判。然后乘上 \(2^n\)，转为求方案数。 我们假设点集 \(S\) 的价值为 \(f(S)\)。那么我们要求的是 \[\sum _S f(S) = \su 阅读全文

摘要： 更差的阅读体验 深刻啊。 这个拓扑序看着很奇怪，我们把它变成一个我们熟悉的东西，dfs 序。注意到把 dfs 序 reverse 一下就可以得到一个剥叶子的序列。所以接下来构造的都是 dfs 序，最后倒着输出就可以。 首先考虑菊花的情况，因为这个情况可能给我们后续的讨论捣乱。假设以 \(1\) 为根 阅读全文

摘要： 更差的阅读体验 首先，我们考虑 \(W(S)\) 怎么求。我们以下称 \(W(S)\) 为路径集合的最大权独立集。 进行树形 dp。假设 \(f_u\) 表示只考虑 \(u\) 子树内的路径集合的最大权独立集，\(g_u\) 表示 \(u\) 子树内，钦定 \(u\) 不被经过的最大权独立集。显然 阅读全文

摘要： 更差的阅读体验 这道题怎么这么像随机字符串，真恶心。 首先有一个观察，就是考虑全局最大值位置 \(p\)，那么 \([1, p)\) 只有前缀最大值，\((p, n]\) 只有后缀最大值。这启发我们分开计算。 假设 \(f_{i, j, k}\) 表示 \(i\) 个数的排列，\(j\) 个前缀最大 阅读全文

摘要： 更差的阅读体验 打 abc 打到的质量最高的一道题，感觉学到了很多东西。 树是一个二分图。考虑 flow。 将 \(\texttt{RGB}\) 映射成数字。我们把树按照深度分成左部点和右部点。 我们考虑把一个点拆成三个，左部点 \(u\) 拆成 \(lp_{u, 0/1/2}\)，右部点 \(u\ 阅读全文

摘要： 更差的阅读体验 写了一大坨，调了一天，也总算是过了。 爬梯子问题应该是一个非常经典的模型。 首先我们知道最后到达梯子底端的时候每个竖杆上人的编号序列 \(p\) 是 \(1 \sim n\) 的一个排列。如果没有横杆，那么最后的序列一定是 \([1, 2, \cdots, n]\)。 定义高度为 \ 阅读全文

摘要： 雪耻之战。 2025/11/29 NOIP 打得依托，可能勉强挂上一等线。下周末还有一场，我需要在一周之内彻底调整心态。这也太难了。 2025/12/01 ~ 2025/12/05 学文化课。 基本上是每天下午去机房，写 \(1.5 \pm 0.5\) 道题，有时候是 vp 去年的百度之星决赛，有时 阅读全文