本文共 1316 字，大约阅读时间需要 4 分钟。

2020.11.16 周一

今天的体验感极差，希望明天可以改运。 上午考试太困了就睡了一个小时，到九点才开始看题。 于是导致最后一道题拍出差异来了，都没时间修锅，几分钟修好不敢说，但一个小时怎么都能修好了。 分数-100 郁闷

下午 csp 出数据了 PYB 上周说这是我考 OI 以来考得最差的一次。

虽然真的考炸了，但我觉得没有什么比赛可以比上次 NOI 考得更栽了。 死猪不怕开水烫了，希望人没事

---

技术问题解答

问题A：

露娜想找一些好朋友，于是她来到了兰德索尔。她发现这里居然有人和她同名（xcw）。露娜认为，与她名字相同或者高度相似的人都能成为她的朋友。她想知道，她最多能和几个人成为朋友呢？

我们认为，两个人的名字高度相似当且仅当他们的长度差为1，并且较长的名字删除一个字符后会变成较短的名字。

---

问题B：

万圣节到了，镜华和她的小伙伴在一起做准备，想吓唬一下骑士君。已知兰德索尔有n个建筑，由n−1条边连接起来，也就是说他形成了一棵树的形状。骑士君的公会在编号为A的房子，镜华初始在编号为B的房子，有一个储存室X。

她们有1×0×114514×4×1919810个炸弹，每次镜华会把炸弹丢在一个随机的建筑里，然后引爆。每一次引爆炸弹会对X到炸弹所在位置上所有建筑造成一次损伤。 镜华想知道，有多少个位置满足：把储存室丢在该处可以使骑士君所在位置A受到损伤的期望次数最多，同时满足她们所在位置B受到损伤的期望次数最小？（X不能与A、B重合。）

---

问题C：

给定一棵树，有n个节点，其中有m条为标记路径。

进行q次询问，每次询问包含一个点对(u, v)，表示询问路径(u, v)上有多少完整的标记路径。 标记路径对询问点对有贡献时满足以下条件：

当u和v不是父子关系时，点对在u的子树中和在v的子树中；

当u和v是父子关系时，点对在子儿子子树中和不在父亲子节点的子树中。

---

问题D：

求无向带权图中，包括节点1的最小环。

对向1有边的结点进行二进制分组，对两边的点跑最短路。 因为总有一次答案的两个点分在了不同组。

---

技术分析

子树大小分析

当选择一个点作为根时，A和B子树的大小如何？

遍历一遍，求出满足A最大时B最小的点的个数。

期望值计算

在本题中，期望可以理解为在一种方案下可能的各种情况的概率乘损伤次数之和。

标准的二维偏序分治可以用于解决此类问题，但如何将询问点对放入二维平面中呢？ 标记路径可以贡献的是一个或两个二维区间。

标记路径贡献

如何将标记路径转化为二维区间？

这是一个典型的CDQ分治问题，但我在考场上想到了一大半，但最后却没能想到如何将询问点对放入二维平面中。

二维偏序分治

如何拓展CDQ的理解？

在实际应用中，如何将询问点对放入二维平面中？ 这可能需要对CDQ的拓展理解，但目前还没有明确的思路。

---

开发建议

在开发过程中，可以将问题逐步拆解：

先求出dfs序；

然后计算每个点为根时A和B子树的大小；

最后，找出满足条件的点。

对于CDQ问题，可以采用标准的二维偏序分治方法，但需要注意标记路径的贡献方式。

在实际实现中，如何将路径转化为二维区间还需要进一步探索。

---

希望这些内容能为您的开发提供参考！