Q779’s Blog

\(k\) 阶前缀和公式 前缀和 对于序列 \(a\) ，它的前缀和定义为满足以下条件的序列 \(S\) 。 \[ S_n = \sum_{1\le i \le n}a_i \] 特别地，我们通常定义 \(S_0=0\) ，但是在本文中不考虑。 \(k\) 阶前缀和 定义函数 \(f : a \to S\) 为序列 \(a\) 到它的前缀和 \(S\) 的映射。 则序列 \(a\) 的 \(k\) 阶前缀和为 \(f^k(a)~(k \ge 1)\) 。通俗地说，就是对 \(a\) 做了 \(k\) 次前缀和。 \(k\) 阶前缀和公式 记序列 \(a\) 的 \(k\) 阶前缀和为 \(S_k\) ，\(S_k\) 的第 \(i\) 项为 \(S_{k,i}\) ，则 \[ S_{k,i} = \sum_{1 \le j \le i} \binom{k + i - j - 1}{k-1}a_j \] 证明： 考虑一个元素 \(x\) 在位置 \(1\) 时对第 \(i\) 次前缀和的贡献。 设 \(f_{i,j}\) 表示第 \(i\) 次前缀和的第 \(j\) 项的系数，...

洛谷P8563 Magenta Potion 题解 题目链接：P8563 Magenta Potion 题意： 给定一个长为 \(n\) 的整数序列 \(a\)，其中所有数的绝对值均大于等于 \(2\)。有 \(q\) 次操作，格式如下： 1 i k 表示将 \(a_i\) 修改为 \(k\)。保证 $k $ 的绝对值大于等于 \(2\)。 2 l r 考虑 \([l,r]\) 的子区间（包括本身）中乘积最大的的区间乘积 \(M\)。如果 \(M>2^{30}\)，输出 Too large，否则输出 \(M\)。特别地，空区间的元素乘积定义为 \(1\)。 输入格式： 第一行两个正整数表示 \(n,q\)。 第二行输入 \(n\) 个整数表示 \(a_i\)。 接下来 \(q\) 行，每行三个整数表示一次询问，格式见上。 输出格式： 对于每次操作2，输出一行表示询问的答案。 数据范围： 对于所有的数据，\(2\le |a_i|,|k| \le 10^9\)，\(1 \le n,q \le 2\times 10^5\)，\(1 \le l \le r \le n\)。 ...

洛谷P1232 [NOI2013] 树的计数 题解 题目链接：P1232 [NOI2013] 树的计数 题意： 我们知道一棵有根树可以进行深度优先遍历（DFS）以及广度优先遍历（BFS）来生成这棵树的 DFS 序以及 BFS 序。两棵不同的树的 DFS 序有可能相同，并且它们的 BFS 序也有可能相同，例如下面两棵树的 DFS 序都是 1 2 4 5 3，BFS 序都是 1 2 3 4 5。 现给定一个 DFS 序和 BFS 序，我们想要知道，符合条件的有根树中，树的高度的平均值。即，假如共有 \(K\) 棵不同的有根树具有这组 DFS 序和 BFS 序，且他们的高度分别是 \(h_1, h_2, \ldots, h_K\)，那么请你输出： \[ \frac{h_1+h_2+\ldots+h_K}K \] 输入格式： 第一行包含 \(1\) 个正整数 \(n\)，表示树的节点个数。 第二行包含 \(n\) 个正整数，是一个 \(1 \ldots n\) 的排列，表示树的 DFS 序。 第三行包含 \(n\) 个正整数，是一个 \(1 \ldots n\) 的排列，表示树的 B...

note[7] 自己瞎推了一个式子，然后打表发现前几项是 \(2^{n-1}\) 。 然后改了一改得到这样的式子。 \[ f_0 = 1, ~f_n = \sum_{0 \le i < n} f_i \] 通项为 \(f_n = 2^n\) 。然后就试图找到这个式子的意义。 实际上这个东西的一种意义是 \(n\) 元集的子集个数 证明：这个递推式就是在枚举每个集合的最大元素。\(\square\) （QAQ.jpg

生成树计数问题 咕咕咕… upd 好家伙，原来有个叫矩阵树定理的东西 QAQ 有空学吧（ 随手记一下这些奇奇怪怪的东西，说不定会派上用场。 以下默认为无向图。 \(n\) 个不同的点构成的完全图，其生成树个数为 \(n^{n-2}\) 。注意生成树没有根节点。 另一种说法为：一个带标号的 \(n\) 个结点的完全图的生成树个数有 \(n^{n−2}\) 个。 证明：Cayley公式，见浅谈 Prüfer 序列 \(n\) 个不同的点构成的完全图，其有根生成树的个数为 \(n^{n-1}\) 。 见上一条，枚举哪个点是根，即可得到。 \(n\) 个无区别点构成的完全图，其不相交生成树的个数为 \(\left\lfloor\frac{n}{2}\right\rfloor\) 。 见 UOJ460 新年的拯救计划 题解

UOJ460 新年的拯救计划 题解 题目链接：#460. 新年的拯救计划 题意： 给定一个 \(n\) 阶完全图 \(K_n\) ，你需要构造 \(K_n\) 的 \(m\) 棵不相交的生成树，求 \(m\) 的最大值并给出方案。 输入格式： 共一行，包含一个正整数 \(n (3\le n\le 2000)\)，表示图的阶数。 输出格式： 输出的第一行是一个正整数 \(m\)，表示生成树的个数。 接下来 \(m\) 行，每行 \(2(n−1)\) 个数，描述一棵生成树，其中第 \(2i−1\) 和第 \(2i\) 个数表示树中的 一条边。 你需要保证你输出的 \(m\) 个子图为 \(K_n\) 的 \(m\) 棵不相交生成树。 如果有多组解，输出任意一组均可。 还在咕咕咕，因为不是很懂。。 口糊了一下dp然后发现方案数是可以 \(\mathcal{O}(1)\) 的，结果不会构造（悲。然后瞄了眼题解发现dp是错的（悲*2 直接说正解吧，方案数为 \(\left\lfloor\frac{n}{2}\right\rfloor\) 。 证明：首先 \(n\) 阶完全图有 \(\...

洛谷P4180 [BJWC2010] 严格次小生成树 题解 题目链接：P4180 [BJWC2010] 严格次小生成树 题意： 给定一张无向连通图，求出它的严格次小生成树。 如果最小生成树选择的边集是 \(E_M\)，严格次小生成树选择的边集是 \(E_S\)，那么需要满足： \[ \sum_{(u,v) \in E_M}w(u,v)<\sum_{(u,v) \in E_S}w(u,v) \] 输入格式： 第一行包含两个整数 \(N\) 和 \(M\)，表示无向图的点数与边数。 接下来 \(M\) 行，每行 \(3\) 个数 \(x,y,z\) 表示，点 \(x\) 和点 \(y\) 之间有一条边，边的权值为 \(z\)。 输出格式： 包含一行，仅一个数，表示严格次小生成树的边权和。 数据中无向图不保证无自环 对于 \(100\%\) 的数据， \(N\le 10^5\)，\(M\le 3\times10^5\)，边权 \(\in [0,10^9]\)，数据保证必定存在严格次小生成树。 欠了快一年的题，现在来写好像挺适合的。 注意，「\(\Sigma\) 次小 ≤ \(...

洛谷P2478 [SDOI2010]城市规划 题解 题目链接：P2478 [SDOI2010]城市规划 题意： 给定一个带点权沙漠（多棵仙人掌），求最大权独立集。 此处独立集的定义为集合中任意两个结点的最短路径长度不小于 \(3\) （就是隔两个结点） 独立集的权值定义为独立集中所有的点的权值的和。 数据范围： \(n\le 10^6,m\le 2\times 10^6\)，且点权 \(0\le h_i \le 1000\)。 提示： 原题给出的是点仙人掌组成的沙漠。 点仙人掌的定义为：每个点至多存在于一个简单环内的无向连通图。 边仙人掌的定义为：每条边至多存在于一个简单环内的无向连通图。 考虑这样一张图 (1,2) (1,3) (2,3) (3,4) (3,5) (4,5) 。它就是边仙人掌，而不是点仙人掌。 仙人掌dp套dp神题，想了我大概 \(5\) 个小时（其实是沙漠） 我们可以用 \(\mathtt{Tarjan}\) 找环，然后分别考虑树上dp和环上dp。 设 \(f_{i,0/1/2}\) ，则 \(f_{i,0}\) 表示选了 \(i\) ， \(i\) 所...

CF825G Tree Queries 题解 题目链接：CF825G Tree Queries 题意： 题目描述： 给定一棵包含 \(n\) 个节点的树（从 1 到 \(n\) 编号），初始所有节点都是白色的。 你需要处理以下两种类型的 \(n\) 个询问: 1 x 将节点 \(x\) 的颜色变成黑色。保证第一个询问为这种类型。 2 x 对于顶点 \(x\) ，找到最小的下标 \(y\) ，使得顶点 \(y\) 在一条从 \(x\) 到某个黑点的简单路径上。 对于每个第 \(2\) 种类型的询问，输出对应的下标 \(y\) 。注意询问是强制在线的。 输入格式： 第一行包含两个正整数 \(n, q(3 \leq n, q \leq 10^6)\) 。 接下来的 \(n-1\) 行，每行包含两个正整数 \(x_i, y_i\left(1 \leq x_i<y_i \leq n\right)\)，表示有一条边连接顶点 \(x_i\) 和 顶点 \(y_i\) 。 保证给出的图是一棵树。 保证第一个询问为类型 \(1\left(t_1=1\right)\) ，且至少有一个询问...

距离 欧式距离（欧几里得距离） 平面直角坐标系中，设点 \(A,B\) 的坐标分别为 \(A(x_1,y_1),B(x_2,y_2)\) ，则两点的欧几里得距离为 \[ |\overrightarrow{AB}| = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \] 设点 \(P(x,y)\) ，则其到原点 \(O\) 的距离为 \[ |\overrightarrow{OP}| = \sqrt{x^2 + y^2} \] 推广至 \(n\) 维空间中，对于 \(A(a_1,a_2,\cdots,a_n),B(b_1,b_2,\cdots,b_n)\) ，有 \[ \|\overrightarrow{AB}\| = \sqrt{\sum_{i=1}^{n}(a_i-b_i)^2} = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\cdots+(a_n-b_n)^2} \] 点 \(P(x_1,x_2,\cdots,x_n)\) 到原点 \(O\) 的距离为 \[ \|\overrightarrow{OP}\| = \sqrt{x_1^...

洛谷P7912 [CSP-J 2021] 小熊的果篮 题解 题目链接：P7912 [CSP-J 2021] 小熊的果篮 题意： 小熊的水果店里摆放着一排 \(n\) 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 \(1, 2, \ldots, n\) 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。 输入格式： 第一行，包含一个正整数 \(n\)，表示水果的数量。 第二行，包含 \(n\) 个空格分隔的整数，其中第 \(i\) 个数表示编号为 \(i\) 的水果的种类，\(1\) 代表苹果，\(0\) 代表桔子。 输出格式： 输出若干行。 第 \(i\) 行表示第 \(i\) 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。 数据范围：...

CF846E Chemistry in Berland 题解 题目链接：CF846E Chemistry in Berland 题意： cxy 是 Berland 大学化学系的研究生。她需要进行一个复杂的实验来撰写她的论文，但是 Berland 的实验室并没有包含这个实验所需要的所有材料。 幸运的是，化学法则允许物质之间的转化（不过 Berland 的化学与我们的不同），但是物质转化的规则有点奇怪。 Berland 化学家知道 \(n\) 种材料，按照某种顺序编号为 \(1, 2, \cdots, n\)。每种材料都可以与其它一种材料互相转化。正式地，对任意 \(2 \leq i \leq n\)，都存在两个正整数 \(x_i, k_i\) 表示一种合理的转化：\(k_i \, \mathrm{kg}\) 的材料 \(x_i\) 可以转化成 \(1 \, \mathrm{kg}\) 的材料 \(i\)，而 \(1 \, \mathrm{kg}\) 的材料 \(i\) 只能变成 \(1 \, \mathrm{kg}\) 的材料 \(x_i\)。 由于 Berland 的化学系统比...