UOJ Logo pink_rabbit的博客

博客

洛谷讨论区关闭打卡

2025-02-08 20:09:42 By pink_rabbit

谷民以后转战 UOJ 进行交流讨论吧!


发博客教程:点进个人主页,然后点“访问 <你的用户名> 的博客”,然后点上面的“日志”,左边有“写新博客”按钮

再换句话说就是访问 https://pink-rabbit.blog.uoj.ac/archive ← 这个链接(把 pink-rabbit 改成你自己的用户名)。


请大家报名 UOJ Round #29!!!


为了防止被管理员隐藏,我来推一个题:【MX-X8-T4】「TAOI-3」Warmth of the Eternity

题意简述:对于一棵 $n$ 个结点的有标号无根树,给出它每个点 $i$ 的度数 $d_i$ 以及删除该点后得到的 $d_i$ 个连通块的大小,问满足条件的原树有多少棵。答案对 $998244353$ 取模。保证至少存在一棵树满足条件,即取模前的答案非零。

数据范围:$2 \le n \le 3 \times 10^5$。


大家可以不用刷回复了,来想想这题咋做。


2025-02-09 更新:下面是该题出题人 251Sec 给出的做法。

删除某点后得到的连通块大小,其实就是以该点为根时的各孩子方向的子树大小。

回顾树的重心的定义,可以发现有了这些信息,就可以唯一确定该树的重心(可能是一个点,也可能是通过一条边相连的两个点)。

我们以重心为根,将无根树转化为有根树,并希望通过这种方式可以对树的可能结构有一个更清晰的把握。

现在我们可以获知每个点的子树大小,以及它所有孩子方向的子树大小。

  • Gorenstein 的问题:什么是“每个点的子树大小”?
    这里指以重心为根时的子树大小,即去掉最大的那侧连通块后剩下的点数(熟知重心的性质是重心所在的那侧是最大的子树)。

现在我们考虑一个点 $u$,假设它有一个孩子方向的子树大小为 $\mathit{siz}$,且存在另一个点 $v$,它自身的子树大小恰好也是 $\mathit{siz}$。考虑这个问题:是否总是能将 $v$ 接在 $u$ 的下方,形成一个合法方案?

答案是肯定的。因为考虑另一个合法方案,并假设在该方案中,$v$ 没有接在 $u$ 的下方。则该方案中必然有另一个点 $v'$ 接在 $u$ 的下方,且 $v'$ 自身的子树大小恰好也是 $\mathit{siz}$。考虑进行调整:互换 $v$ 与 $v'$ 的位置(包括它们的整个子树),则形成的新方案必然也合法。为什么呢?考虑 $u$ 的孩子的限制,去掉了一个 $v'$ 又加入了一个 $v$,而这两点的子树大小是相同的,所以不会破坏 $u$ 的孩子的限制的合法性。对于 $v$ 的父节点(记作 $u'$)也是同理,去掉了一个 $v$ 又加入了一个 $v'$,也不会破坏合法性。

故结论是:任意的 $(u, v)$ 配对都能导出合法方案,只需满足 $u$ 的一个孩子方向的子树大小恰好等于 $v$ 的子树大小。在这个配对完成后,$u$ 的那一孩子方向的子树就被占用了,不能在后续配对中使用。

下面考虑整体的方案数:

  • 对一个大小 $\mathit{siz} = k$,假设有 $a$ 个结点拥有孩子方向的子树大小恰好为 $k$ 的限制,且它们的这样的孩子方向个数分别为 $c_1, \ldots, c_a$,然后又有 $b$ 个结点的自身的子树大小恰好为 $k$。
  • 显然,应满足 $c_1 + \cdots + c_a = b$,因为完整的配对方案中,必须恰好一一匹配。
  • 不同的结点以任意顺序与同一个结点配对(接在同一个结点下方),产生的方案是相同的,故不能重复计入这些方案。
  • 可以发现,每个方案就相当于为 $b$ 个结点染上 $a$ 种颜色之一,且满足染第 $i$ 种颜色的点数恰好为 $c_i$。
  • 不难看出这就是多重组合数的组合意义,即 $\dbinom{b}{c_1, \ldots, c_a}$。
  • 不同的 $k$ 是互相独立的,用乘法原理乘在一起即可。

最终的答案为 $\displaystyle \prod_k \binom{b}{c_1, \ldots, c_a}$。

只需预处理组合数,就可在 $O(n)$ 的时空复杂度内解决该题。

同时感谢 Luke_limyeenewfiles 参与该题的讨论!(不难发现 myee 给出的做法等价于忽略“定重心为根”后的步骤。)你们为所有从洛谷前来 UOJ 的新用户开了个好头!希望大家友善讨论,减少对新用户的攻击,并引导他们改掉坏习惯,向善参与交流讨论。

我衷心相信,在所有热爱 UOJ 的用户的共同努力下,UOJ 的博客区可以从以往的死气沉沉,真正变成一个“多元、开放与包容”的学术讨论社区。一起努力吧!

#394. 【NOI2018】冒泡排序 的 UOJ 目前数据是怎么样的?

2022-09-21 10:30:52 By pink_rabbit

据我们所知,官方数据有 #16 出现 $n = 0$,并且特殊性质数据忘记造了的问题。UOJ 中是否对这题官方数据有所改动?

Codeforces OIer List 宣传及反馈帖(UniversalOJ)

2020-09-23 19:18:37 By pink_rabbit

准入要求:

  1. 是中国大陆 OIer 且能在 OIerDb 上搜得到,且参加过至少一次 CSP-S 复赛或 NOIP 提高组复赛并获得过二等奖及以上奖项。
  2. 在 2021 年各省省队选拔结束前,理论上有机会以 A/B/C/D/E 类选手身份参加 NOI2021。即应在 2020 年 9 月入学后成为高二年级及以下学生。
  3. 此 Codeforces 账号需满足以下三条要求中的至少一条:(i.) 当前 Rating 达到 1600 及以上(Expert 级别);(ii.) 最高 Rating 达到 1900 及以上(Candidate Master 级别);(iii.) 在 rated 的 Div. 2 或 Educational 比赛中取得过正式选手排名前 50。
  4. 能够证明此 Codeforces 账号由本人完全控制或本人能够取得账号的主要控制权。且本人无意愿让此账号不在此名单中出现。

如果您认为您的 Codeforces 账号或常用小号应该/不应该在其中,请联系我,我将及时更改。

如果您在 List 中发现错误,即违背上述四条要求中的任何一条的,也请联系我,我将及时更改。

pink_rabbit Avatar