Q779’s Blog

洛谷P1196 [NOI2002] 银河英雄传说 题解 题目链接：P1196 [NOI2002] 银河英雄传说 题意： 一共有 \(n=30000\) 个人，给定 \(Q ~(1\le Q \le 5\times 10^5)\) 次操作 M i j 表示将 \(i\) 所在队伍拼接到 \(j\) 所在队伍队尾。 C i j 表示询问 \(i,j\) 在队伍中相差多少个人（ \(i,j\) 不算在内） 如果他们不在一个队伍中，请输出 \(-1\) 。 带权并查集模板题，欠了快大半年才去研究 说实话，以前怎么看都看不懂，现在看就很显然，不知道为什么。 第一个操作显然是可以用并查集维护的（难不成你用左偏树？） 考虑如何维护第二个操作。注意到并查集其实维护了一个森林。 而带权并查集，实际上就是把普通并查集维护的森林带上了边权。 我们记录两个数组 \(d_i\) 和 \(s_i\) （代码里是 d[] 和 sz[]） \(d_i\) 表示当前结点到根的距离 \(s_i\) 表示它所在的树的结点个数 void init(int n) { for(int i=1;...

洛谷P2515 [HAOI2010]软件安装 题解 题目链接：P2515 [HAOI2010]软件安装 题意： 现在我们的手头有 \(N\) 个软件，对于一个软件 \(i\) ，它要占用 \(W_i\) 的磁盘空间，它的价值为 \(V_i\) 。我们希望从中选择一些软件安装到一台磁盘容量为 \(M\) 计算机上，使得这些软件的价值尽可能大（即 \(V_i\) 的和最大）。 但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件 \(j\) （包括软件 \(j\) 的直接或间接依赖）的情况下才能正确工作（软件 \(i\) 依赖软件 \(j\) )。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为 \(0\) 。 我们现在知道了软件之间的依赖关系：软件 \(i\) 依赖软件 \(D_i\) 。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则\(D_i=0\)，这时只要这个软件安装了，它就能正常工作。 输入格式： 第1行：\(N,M(0\leq N\leq 100, 0\leq M\leq ...

UOJ246 【UER #7】套路 题解 题目链接：#246. 【UER #7】套路 题意： 反攻正在进行中，按照套路，跳蚤国将会很快获得最终的胜利。跳蚤国的情报局也没闲下来，他们正打算派遣一批 “菲克蚤” 前往跳晚国窃取有关三星 note7 的资料。 cxy 是这批 “菲克蚤” 的教练，他教会他们各种 Fake 的技术，以便更好混入敌方内部。共 \(n\) 只菲克蚤，由 \(1\) 到 \(n\) 编号。cxy 给每个菲克蚤都算了特征值 \(a_1, \dots, a_n\)，两个菲克蚤的相似度定义成这两个菲克蚤的特征值的差的绝对值，即第 \(i\) 只菲克蚤与第 \(j\) 只菲克蚤的相似度为 \(\lvert a_i - a_j \rvert\)。 现在这批菲克蚤排成一列在 cxy 面前，cxy 需要在其中选出一些菲克蚤合成一个行动小队。按照套路，他会选取连续一整段的菲克蚤 \(a_l, a_{l + 1}, \dots, a_r\)。很显然，这个行动小队越大越好，但是按照套路，小队内的跳蚤最好都各不相同，假如有两只跳蚤长得很像的话很可能会引起跳晚们的怀疑。为此 cxy ...

洛谷P1963 [NOI2009] 变换序列 题解 题目链接：P1963 [NOI2009] 变换序列 题意： 对于 \(N\) 个整数 \(0, 1, \cdots, N-1\) ，一个变换序列 \(T\) 为这 \(N\) 个整数的一个置换。 定义 \(x\) 和 \(y\) 之间的距离（\(x,y = 0,1,\cdots,n-1\)） \[ D(x,y)=\min\{|x-y|,N-|x-y|\} \] 给定每个 \(i\) 和 \(T_i\) 之间的距离 \(D(i,T_i)\) 你需要求出一个满足要求的且字典序最小的变换序列 \(T\) 。 说明：对于两个变换序列 \(S\) 和 \(T\) ，如果存在 \(p<N\) ，满足对于\(i=0,1,\cdots,p-1\)， \(S_i=T_i\) 且 \(S_p<T_p\) ，我们称 \(S\) 比 \(T\) 字典序小。 原题真的废话连篇还特别丑，已经删减过了。 输入格式： 第一行包含一个整数 \(N\) ，表示序列的长度。接下来的一行包含 \(N\) 个整数 \(D_i\) ，其中 \(D_i\) 表...

洛谷P2272 [ZJOI2007]最大半连通子图 题解 题目链接：P2272 [ZJOI2007]最大半连通子图 题意： 一个有向图 \(G=\left(V,E\right)\) 称为半连通的，如果满足：\(\forall u,v\in V\)，满足 \(u\to v\) 或 \(v\to u\)，即对于图中任意两点 \(u,v\)，存在一条 \(u\) 到 \(v\) 的有向路径或者从 \(v\) 到 \(u\) 的有向路径。 若 \(G'=\left(V',E'\right)\) 满足 \(V'\subseteq V\)，\(E'\) 是 \(E\) 中所有跟 \(V'\) 有关的边，则称 \(G'\) 是 \(G\) 的一个导出子图。若 \(G'\) 是 \(G\) 的导出子图，且 \(G'\) 半连通，则称 \(G'\) 为 \(G\) 的半连通子图。若 \(G'\) 是 \(G\) 所有半连通子图中包含节点数最多的，则称 \(G'\) 是 \(G\) 的最大半连通子图。 ...

洛谷P4981 父子 题解 题目链接：P4981 父子 题意： 对于全国各大大学的男生寝室，总是有各种混乱的父子关系。 那么假设现在我们一个男生寝室有不同的 \(n\) 个人，每个人都至多有一个“爸爸”，可以有多个“儿子”，且有且只有一个人没有“爸爸”(毕竟是室长，还是要给点面子，当然了，室长人人当嘛)。 那么现在问题来了，对于一个有 \(n\) 个人的寝室，最多可能存在多少种父子关系，当然每个人之间都必须要有直接或间接的父子关系。 输入格式： 第一行一个 正整数 \(t\)，表示有组数据。 接下来 \(t\) 行，每行一个整数 \(n\)，表示有 \(n\) 个人。 输出格式： 共 \(t\) 行，每行一个整数，求关系个数。 由于答案可能较大，则我们需要输出答案对 \(10^9+9\) 取模的值。 数据范围： 对于 \(100\%\) 的数据，\(t≤10^4\)，\(n≤10^9\)。 \(n\) 个不同结点的有根树数量 显然等于「 \(n\) 个不同结点的无根树的数量」 乘以 \(n\) 根据 Cayley 公式，前者就是 \(n^{n-2}\) （不知道戳这里） \[...

洛谷P2532 [AHOI2012]树屋阶梯 题解 题目链接：P2532 [AHOI2012]树屋阶梯 题意： 有点搞笑的是，我刚刚写的 浅谈卡特兰数 （Catalan数） 恰好提到了这个。 所以它就是卡特兰数。当然观察样例手推也可以发现，1,1,2,5,14嘛。 当然这个题也是有理论依据的。 考虑证明它是一个 Catalan number。先去搬几张图（逃 设 \(f_i\) 表示 \(i\) 层高的阶梯的方案数，边界：\(f_0=1,f_1=1\) 考虑 \(n=5\) 的情况，下图中红色的部分表示我们将要填充的块 可以发现它的方案数为 \(f_0 \times f_{4}\) 。 考虑填充第二块 可以发现它的方案数为 \(f_1 \times f_3\) 。 还没看出来吗？那再来一个。 可以发现它的方案数为 \(f_2 \times f_2\) 。 根据卡特兰数的某常用公式，不难发现这是卡特兰数（？ \[ C_n =\sum_{i=1}^{n}C_{i-1}C_{n-i} \] 只不过这里换成了 \(f\) 。然后我们就做完这题了 代码：（又是高精度。。） n...

浅谈卡特兰数 （Catalan数） 卡特兰数的定义 卡特兰数是组合数学中一个常在各种计数问题中出现的数列。 卡特兰数的一般项公式为 \[ C_n = \frac{1}{n+1} \dbinom{2n}{n} = \frac{(2n)!}{n!(n+1)!}\quad (n\in \mathbb{N}) \tag{1} \] 还有以下常见公式 \((n \in \mathbb{N})\) \[ C_0=1,~C_1=1\\ C_n = \sum_{i=1}^{n} C_{i-1}C_{n-i},\quad n \ge 2\tag{2} \] \[ C_n = \frac{(4n-2)C_{n-1}}{n+1} \tag{3} \] \[ C_n = \dbinom{2n}{n}-\dbinom{2n}{n-1} \tag{4} \] OEIS A000108 这张表很重要。因为有时候想不出来可以手推前几项猜卡特兰数。 \(n\) 0 1 2 3 4 5 6 \(\cdots\) \(C_n\) 1 1 2 5 14 42 132 \(\cdots\) 我们可以用...

洛谷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\)，...