Q779’s Blog

洛谷P2290 [HNOI2004]树的计数 题解 题目链接：P2290 [HNOI2004]树的计数 题意： 一个有 \(n\) 个节点的树，设它的节点分别为 \(v_1,v_2,\ldots,v_n\)，已知第 \(i\) 个节点 \(v_i\) 的度数为 \(d_i\)，问满足这样的条件的不同的树有多少棵。 输入格式： 输入文件第一行是一个正整数 \(n\) ，表示树有 \(n\) 个结点。第二行有 \(n\) 个数，第 \(i\) 个数表示 \(d_i\)，即树的第 \(i\) 个结点的度数。 输出格式： 输出满足条件的树有多少棵。 数据范围： \(1\le n\le 150\)，保证满足条件的树不超过 \(10^{17}\) 个。 Prüfer 序列简单题。详见浅谈 Prüfer 序列 则对于给定度数 \(d_{1\sim n}\) 的一棵无根树一共有 \(\dbinom{n-2}{d_1,d_2,\cdots,d_k}=\dfrac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}\) 种情况。 本题需要高精度。因此我使用 \(\mathtt{Pyth...

浅谈 Prüfer 序列 Prüfer 序列的定义 Prüfer 序列常用于组合计数。 板子题：P6086 【模板】Prüfer 序列 Prüfer 序列可以将一个带标号的 \(n\) 个节点的数用 \([1,n]\) 中的 \(n-2\) 个整数表示 或者可以认为 Prüfer 序列是「完全图的生成树」与「数列」的双射。 注意，Prüfer 序列的长度为 \(n-2\) ！ 例如，下图的带标号无根树的 Prüfer 序列为 \(\{4,4,4,5\}\) 。 Prüfer 序列与无根树的相互转化 无根树的 Prüfer 序列的构造方法如下： 每次选择一个编号最小的叶子节点并删除它，然后记录它连接到的那个节点 重复 \(n-2\) 次后就只剩下两个节点，算法结束。 其实这个过程就是把外面一层一层的删掉，最后剩下两个节点 我们可以用一个指针 \(p\) 来寻找维护「编号最小的叶子节点」 具体地，我们可以先把无根树随便找个节点 \(\mathtt{dfs}\) 后转成有根树 注：板子题里直接默认 \(n\) 为转化后的根节点，并给出了每个节点的父亲。（挺良心的） 我们...

C++ double类型用法总结 下文均采用double。 施工中，咕咕咕… // 1.1 声明变量的方法 double x; double x{3.1'415'926}; // double x{3.1415926}; double x(3.1415926); double x{2}; double x=2; // 1.2 浮点字面量 // 可以用 typeid(x).name() 来输出x的类型 float x{2f}; auto x{1.112} // double x auto x{ 1.0L }; // long double x; auto x{ 1L }; // int x; // 1.3 数据类型属性： numeric_limits<double>::max(); //可储存的最大正数 1.79769e+308 numeric_limits<double>::min(); ...

UOJ161 【清华集训2015】园子里 题解 题目链接：#161. 【清华集训2015】园子里 题意： cxy 在园子里过着快乐而充实的生活。突然有一天，从天而降 \(n\) 根柱子，这 \(n\) 根柱子在学堂路上排成一排，第 \(i\) 根柱子高度为 \(h_i\)（即\(h_i\) 为原始高度）米，然而，当有人站在第 \(i\) 根柱子上的时候，第 \(i\) 根柱子的高度会下降 \(t_i\)（即当有人在上面时候 \(h_i-t_i\) 就是当前高度）米，离开之后又会恢复。cxy 对这些柱子非常感兴趣，他可以从一根柱子跳到任意一个（包括他原本站着的柱子）原始高度不超过他所在柱子当前高度的柱子上，如果有多个柱子都满足，他会随机等概率地跳到一个满足条件的柱子上，如果没有柱子满足，他就会跳到地上。 cxy 想知道，如果他从第 \(i\) 个柱子开始，期望跳多少次可以跳到地上。 输入格式： 第一行一个整数 \(n\)，表示柱子的数量。 第二行 \(n\) 个空格隔开的整数 \(h_i\)，表示每根柱子的高度（单位：米）。 第三行 \(n\) 个空格隔开的整数 \(t_i\)，...

UOJ152 【UR #10】汉诺塔 题解 题目链接：#152. 【UR #10】汉诺塔 题意： cxy 是魔仙女王。 cxy 现在使用巴拉拉能量造了三根柱子（编号分别为 \(1\) 到 \(3\)）以及 \(n\) 块颜色不同的圆盘（编号为 \(1\) 到 \(n\)）。最开始 cxy 给定一个 \(1\) 到 \(n\) 的排列 \(A\)，她会用巴拉拉能量把这些圆盘放到编号为 \(1\) 的柱子上，使得从上到下第 \(i\) 块圆盘的编号是 \(A_i\)。 接着你可以进行若干次操作，每一次操作用两个整数 \(a,b\) （\(1 \leq a,b \leq 3,a \neq b\)） 来描述，表示这次操作你将会把地 \(a\) 根柱子最上面的圆盘取出，并放到第 \(b\) 根柱子上去（如果当前第 \(a\) 根柱子上不存在圆盘，这次操作将会被小魔仙们忽略）。最终你要使得这 \(n\) 块圆盘在同一根柱子上，且从上到下编号依次递增（最终状态下所有圆盘可以在任意一根柱子上）。 小魔仙们虽然善良，但是他们的耐心并不是无限的，所以你必须在 \(10^6\) 次操作内完成任务。 ...

洛谷P3352 [ZJOI2016]线段树 题解 题目链接：P3352 [ZJOI2016]线段树 题意： cxy 遇到了一个题目：有一个序列 \(a_1,a_2,\ldots,a_n\)，\(m\) 次操作。每次操作把一个区间内的数改成区间内的最大值，问最后每个数是多少。 cxy 很快地就使用了线段树解决了这个问题。 于是充满智慧的 cxy 想，如果操作是随机的，即在这 \(m\) 次操作中每次等概率随机地选择一个区间 \([l,r]\)（\(1 \leq l \leq r \leq n\)），然后将这个区间内的数改成区间内最大值（注意这样的区间共有 \(\frac{n(n+1)}{2}\) 个），最后每个数的期望大小是多少呢？ cxy 非常热爱随机，所以她给出的输入序列也是随机的（随机方式见数据规模和约定）。 对于每个数，输出它的期望乘 \(\left(\frac{n(n+1)}{2} \right)^m\) 再对 \(10^9+7\) 取模的值。 输入格式： 第一行包含两个正整数 \(n,m\)，表示序列里数的个数和操作的个数。 接下来一行，包含 \(n\) 个非负整数 ...

note[2] sum((n-i)*i,{i,1,n})/(1/2*n*(n-1)) (*ans = (n + 1)/3*) Limit[1/(n-1)*(n+1)/3,n->+∞] (*ans = 1/3*) 例：单位线段上随机选两个点，两点距离的期望？ 选自某年的初赛题。 解： 据说这个思路是从分布律的角度出发的。 不急，我们先证明几个小结论。 引理1：对于 \(n \in \mathbb{N}\) ，有 \[ \sum_{i=1}^{n} i (n-i) = \frac{1}{6}n(n-1)(n+1) = \frac{n^3}{6} - \frac{n}{6} \] 证明：根据note1的思路拆项套公式易得。\(\square\) 引理2：对于 \(n \in \mathbb{N}\) ，有 \[ \frac{\sum_{i=1}^{n}i(n-i)}{\frac{1}{2} n(n-1)} = \frac{n+1}{3} \] 证明：根据引理1计算可得。\(\square\) 现在来考虑这道题。 把线段看作 \(n\) 个点，则相邻两点的距离为...

note[1] simplify Sum[(n-i+1)*i,{i,1,n}] 第一次写这个类型的文章。主要记录平时看到的数学小知识 例：化简下列式子 link \[ \sum_{i=1}^{n} (n-i+1)\times i \] 解： \[ \begin{aligned} &\quad\sum_{i=1}^{n} (n-i+1)\times i \\&=\sum_{i=1}^{n} ni - \sum_{i=1}^{n}i^2 + \sum_{i=1}^{n}i \\&=\frac{n^2(n+1)}{2} - \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} \\&=\frac{(3n+3-2n-1)\times n(n+1)}{6} \\&=\frac{1}{6}n(n+1)(n+2) \end{aligned} \] 注：用到了以下常用公式 \[ \sum\limits_{i=1}^{n}i = \dfrac{n(n+1)}{2} \\\sum\limits_{i=1}^{...

UOJ244 【UER #7】短路 题解 题目链接：#244. 【UER #7】短路 题意： “第七套广播体操，原地踏步——走！” 众所周知，跳蚤们最喜欢每天早起做早操，经常天还没亮就齐刷刷地站在操场做着反复纵跳热热身。跳晚国在研制三星 note7 的时候注意到了这点，于是他们打算让炸弹更快地引爆，这样就可以消灭更多早起的跳蚤。 三星 note7 的主板可以看作是由 \((2n + 1) \times (2n + 1)\) 个中继器构成的，某些中继器会有导线连在一起，左上角和右下角的中继器分别连着电源的正负极。 电流流过一根导线的时间可忽略不计，但当电流经过中继器时，会延缓一段时间再从中继器流出。这个时间只跟该中继器本身有关，我们把这段时间的长度称为中继器的延时值。 这些中继器由导线连接围成一个一个的层，同个层的中继器的种类都一样，而不同层的种类都不一样，可以发现总共有 \(n + 1\) 层。当 \(n = 4\) 时，主板大概长这样： 跳晚们打算再加几根导线将某些中继器连接起来. 凭借发达的重工业，他们能生产出无数条导线。但由于主板的限制，他们的导线只能和主板四周的边平行...

洛谷P3350 [ZJOI2016]旅行者 题解 题目链接：P3350 [ZJOI2016]旅行者 题意： cxy 来到了一个新的城市旅行。她发现了这个城市的布局是网格状的，也就是有 \(n\) 条从东到西的道路和 \(m\) 条从南到北的道路，这些道路两两相交形成 \(n\times m\) 个路口 \((i,j)\)， \((1\leq i\leq n,1\leq j\leq m)\) 她发现不同的道路路况不同，所以通过不同的路口需要不同的时间。通过调查发现，从路口 \((i,j)\) 到路口 \((i,j+1)\) 需要时间 \(r(i,j)\) ，从路口 \((i,j)\) 到路口 \((i+1,j)\) 需要时间 \(c(i,j)\) 。注意这里的道路是双向的。cxy 有 \(q\) 个询问，她想知道从路口 \((x_1,y_1)\) 到路口 \((x_2,y_2)\) 最少需要花多少时间。 输入格式 第一行包含 2 个正整数 \(n,m\) 表示城市的大小。 接下来 \(n\) 行，每行包含 \(m-1\) 个整数，第 \(i\) 行第 \(j\) 个正整数表示从一...

UOJ235 【IOI2016】molecules 题解 题目链接：#235. 【IOI2016】molecules 题意： cxy 在一家公司工作，这家公司已经制造了一台检测分子的机器。每个分子的重量都是正整数。这台机器的检测范围是 \([l, u]\)，这里 \(l\) 和 \(u\) 都是正整数。这台机器能够检测一个分子集合当且仅当这个集合包含了一个子集，这个子集的分子的重量属于机器的检测范围。 考虑 \(n\) 个分子，重量记为 \(w_0, \ldots, w_{n - 1}\)。如果存在一个下标的集合（并且该集合中的下标都不相同）\(I = \{i_1, \ldots, i_m\}\) 使得 \(l \le w_{i_1} + \cdots + w_{i_m} \le u\)，那么检测就会成功。 由于机器的细节，\(l\) 和 \(u\) 之间的差距要保证会大于等于最重分子和最轻分子之间的差距，即 \(u - l \ge w_{\max} - w_{\min}\)，其中 \(w_{\max} = \max(w_0, \ldots, w_{n - 1})\)，\(w_...

UOJ69 新年的QAQ 题解 题目链接：#69. 新年的QAQ 题意： 春节期间， cxy 订购了一台高端电脑。结果买回来一看，果然高端：每秒能进行 \(10^{20}\) 次计算，从此腰也不酸了腿也不疼了。 在这台电脑上有一种编程语言名叫 QAQ，它的代码由 \(N\) 行组成，这台电脑会从第 \(1\) 行开始，从上到下依次执行。 这种编程语言有 \(26\) 个 32 位整数型变量，分别叫做 \(a, \dots, z\)。 有这样几种语句： input c 从标准输入读入一个整数并存储在 \(c\) 中。\(c\) 可以是 \(a\) 到 \(z\) 的任意变量。 output c 输出一个整数 \(c\)。\(c\) 可以是 \(a\) 到 \(z\) 的任意变量。 c = b 把 \(b\) 的值赋给 \(c\)。\(b\) 可以是 32 位整数或 \(a\) 到 \(z\) 的任意变量，\(c\) 可以是 \(a\) 到 \(z\) 的任意变量。 c = a op b 把 \(a\) 和 \(b\) 进行 op 运算并把值赋给 \(c\)。\(a, b\) 可...