Q779’s Blog

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 的化学系统比...

UOJ278 【UTR #2】题目排列顺序 题解 题目链接：#278. 【UTR #2】题目排列顺序 题意： “又要出题了。” 宇宙出题中心主任 —— cxy ，坐在办公桌前策划即将到来的 UOI。 这场比赛有 \(n\) 道题， cxy 需要决定这些题目的难度，然后再在汪洋大海中寻找符合该难度的题目。 题目的难度可以用一个 \(1\) 到 \(n\) 的排列 \(a_1, \dots, a_n\) 表示，其中 \(a_i\) 表示第 \(i\) 道题目在这 \(n\) 道题目中是第 \(a_i\) 简单的题目，即恰有 \(a_i - 1\) 道题目比第 \(i\) 道题目简单。 经验丰富的 cxy 早就悟出了一种科学地决定难度顺序的方法。首先， cxy 定义了难度递增子序列为序列 \(a_{p_1}, a_{p_2}, \dots, a_{p_k}\) （\(1 \le p_1 < p_2 < \dots < p_k \le n\)） 满足 \(a_{p_1} < a_{p_2} < \dots < a_{p_k}\) 。然后， cxy 决...

CF398B Painting The Wall 题解 题目链接：CF398B Painting The Wall 题意： cxy 打算漆一堵墙。这个墙由 \(n^2\) 块瓷砖构成，它们构成 \(n \times n\) 的表。有些瓷砖是被涂上颜色的，还有些则没有。她想要将这堵墙漆得漂亮，她会按照以下四个步骤进行： 首先，cxy 会检查这堵墙，如果每行、每列均有涂上颜色的瓷砖，则停止刷墙，否则跳转到步骤 2。 cxy 从这 \(n^2\) 块瓷砖中均匀随机地选择一块瓷砖。 如果该瓷砖没有被涂色，则她将那块瓷砖涂色，否则，她什么都不用干。 然后，她休息 \(1\) 分钟，然后回到步骤 1。 cxy 觉得，她会花费太多时间在砌墙上。所以，她想知道，她按照上面的方法砌墙所需的时间的期望。你可以假设涂一块瓷砖不用花费任何时间。 输入格式： 第一行包含两个正整数 \(n, m~(1 \leq n \leq 2000,~0 \leq m \leq \min \{n^2, 20000\})\)，表示墙的大小和已经涂色的瓷砖的个数。 接下来的 \(m\) 行，每行包含两个正整数 \(r,...

CF464D World of Darkraft - 2 题解 题目链接：CF464D World of Darkraft - 2 题意： cxy 在玩 “World of Dardraft - 2” 游戏，有 \(k\) 种不同的装备，初始状态下所有的装备都是 \(1\) 级的。 每当打败一个怪物，她就能获得一个新的装备，新的装备由如下规则生成： 先从 \(k\) 种装备中等概率随机选择一种装备，记作 \(i\)。 设当前类型为 \(i\) 的装备的等级为 \(t_i\)，则会从 \([1, t_i + 1]\) 中等概率随机一个作为新的装备的等级。 cxy 会从新的装备和原来 (对应类型) 的装备中选择一个级别更高的，将它装备上，并出售剩下的一个装备，等级为 \(x\) 的装备的售价为 \(x\) (个硬币)。 请帮助 cxy 决定打败 \(n\) 个怪物后获得的硬币数的期望。 输入格式： 共一行，包含两个正整数 \(n, k\) 。 输出格式： 输出一行一个实数，表示打败 \(n\) 个怪物后获得硬币数的期望。答案被认为正确当且仅当相对或绝对误差不超过 \(10^{-...

洛谷P1399 [NOI2013] 快餐店 题解 题目链接：P1399 [NOI2013] 快餐店 题意： cxy 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，cxy 希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市 C 的 \(N\) 个建筑中，这 \(N\) 个建筑通过恰好 \(N\) 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。cxy 的快餐店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。 现给定城市 C 的地图（道路分布及其长度），请找出最佳的快餐店选址，输出其与最远的顾客之间的距离。 输入格式： 第一行包含一个整数 \(N\)，表示城市 C 中的建筑和道路数目。 接下来 \(N\) 行，每行 \(3\) 个整数，\(A_i,B_i,L_i\)（\(1\leq i\leq N\)，\(L_i>0\)），表示一条道路连接了建筑 \(A_i\) 与 \(B_i\...

洛谷P3770 [CTSC2017]密钥 题解 题目链接：P3770 [CTSC2017]密钥 题意： 一个密钥是一个长度为 \(n = 2k + 1\) 的字符串，它包含 \(1\) 个字母 \(\tt{X}\)、k 个字母 \(\tt{A}\) 和k 个字母 \(\tt{B}\)。例如 \(k = 3\) 时，\(\tt{BAXABAB}\) 就是一个密钥。 如下图所示，可以按顺时针顺序把这 \(2k+1\) 个字母排成一个圈： 在 \(k\) 个字母 \(\tt{A}\) 中，有一部分可以定义为 “强的”。具体来说，从 \(\tt{X}\) 出发顺时针走到某个 \(\tt{A}\) 时，如果途中 \(\tt{A}\) 的数目严格多于\(\tt{B}\)的数目，则称此字母 \(\tt{A}\) 为强的。 对于上面的例子来说，顺时针方向从字母 \(\tt{X}\) 数起第 \(1\) 个和第 \(2\) 个字母 \(\tt{A}\) 是强的，而第 \(3\) 个字母 \(\tt{A}\) 不是强的。 一个密钥的特征值就是其中包含的强的字母 \(\tt{A}\) 的个数。 天...

BZOJ4242 水壶 题解 题目链接：#4242. 水壶 题意： cxy 所居住的 IOI 市以一年四季都十分炎热著称。 IOI 市是一个被分成纵 \(H\) \(\times\) 横 \(W\) 块区域的长方形，每个区域都是建筑物、原野、墙壁之一。建筑物的区域有 \(P\) 个，编号为 \(1,2,\cdots ,P\)。 cxy 只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。 cxy 因为各种各样的事情，必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好，但原野上的日光十分强烈，因此在原野上每走过一个区域都需要 \(1\) 单位的水。此外，原野上没有诸如自动售货机、饮水处之类的东西，因此 IOI 市的市民一般都携带水壶出行。大小为 \(x\) 的水壶最多可以装 \(x\) 单位的水，建筑物里有自来水可以将水壶装满。 由于携带大水壶是一件很困难的事情，因此 cxy 决定携带尽量小的水壶移动。因此，为了随时能在建筑物之间移动，请你帮他写一个程序来计算最少需要多大的水壶。 现在给出 IOI 市的地图和 \(Q\) 个询问，第 \(i\) 个询问 \(...

导数&不定积分 学习笔记 这是一篇整合&小总结文章。 众所周知，微分和积分是对应可逆的。所以就有了这篇文章 相关文章：导数的基本公式推导 | 不定积分基本公式 基本定义 导数是微积分学中的一个概念。函数在某一点的导数是指这个函数在这一点附近的变化率。 \[ f^{\prime}(x) = \lim_{\Delta x \to 0}\frac{f(x+\Delta x)-f(x)}{\Delta x} \] \(f\) 在 \(x_0\) 处的导数，记作 \(f^{\prime}(x_0)\) 或 \(\frac{df}{dx}(x_0)\) 或 \(\left.\frac{df}{dx}\right|_{x=x_0}\) 。 不定积分是所有原函数的集合。也就是说，如果 \(F^{\prime}(x) = f(x)\) ，则 \[ \int f(x)\,dx = F(x) + C \tag{1} \] 其中 \(C\) 为常数，原因在于 \((C)^{\prime} = 0\)。 线性运算 导数： \[ {[f(x) \pm g(x)]}^{\prime} = ...

小蓝书 16.3 本文写于较早时候，所以可能存在一些问题。 小蓝书上讲的母函数就是普通生成函数。传送门：生成函数 学习笔记 对于一个数列 \(\{f_n\}\) ，定义它的普通生成函数 \(F(x)\) 为以 \(x\) 为未定元的一个形式幂级数，则 \[ F(x) = \sum_{n \ge 0} f_nx^n \\f_n = [x^n]F(x) \] 另一种易于理解的写法是这样的（数列为 \(\{a_n\}\) ） \[ F(x) = \sum_{i=0}^{\infty}a_ix^i = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots \] 一些常用的公式&技巧： 更多详见 泰勒级数&麦克劳林级数 公式I \(\forall x : |x| < 1\) \[ \dfrac{1}{1-x} = \sum_{n=0}^{\infty} x^n = 1+x+x^2 + \cdots + x^n + \cdots \] 公式II \(\forall x : |x| < 1,~ k \in \mathbb{Z...