Q779’s Blog

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\) 可...

UOJ405 【IOI2018】组合动作 题解 题目链接：#405. 【IOI2018】组合动作 题意： 你在玩一个动作游戏。游戏控制器有 \(4\) 个按键，A、B、X 和 Y。在游戏中，你用组合动作来赚金币。你可以依次按这些按键来完成一个组合动作。 这个游戏有一个隐藏的按键序列，可以表示为由这 \(4\) 个字符组成的串 \(S\)。你并不知道这个串 \(S\)，但是你知道它的长度为 \(N(1\le N \le 2000)\)。 你还知道，\(S\) 的首字符不会在串中重复出现。例如，\(S\) 可以是”ABXYY“或者”XYYAA“，但不能是”AAAAA“或”BXYBX“。 你可以依次按最多 \(4N\) 个按键来完成一个组合动作。串 \(p\) 为你所按的按键序列。你用这个组合动作赚到的金币数量，等于同时为 \(p\) 之子串和 \(S\) 之前缀的最长字符串的长度。串 \(t\) 的子串定义为 \(t\) 中的连续字符序列 (可以为空)。\(t\) 的前缀定义为 \(t\) 的子串，其或者为空，或者包含 \(t\) 的首字符。 例如，如果 \(S\) 是 “ABXY...

洛谷P3291 [SCOI2016]妖怪 题解 题目链接：P3291 [SCOI2016]妖怪 题意： 邱老师是妖怪爱好者，他有 \(n\) 只妖怪，每只妖怪有攻击力 \(\mathtt{atk}\) 和防御力 \(\mathtt{dnf}\) 两种属性。邱老师立志成为妖怪大师，于是他从真新镇出发，踏上未知的旅途，见识不同的风景。 环境对妖怪的战斗力有很大影响，在某种环境中，妖怪可以降低自己 \(ka\) 点攻击力，提升 \(kb\) 点防御力或者，提升自己 \(ka\) 点攻击力，降低 \(kb\) 点防御力。 \(a,b \in \mathbb{R}_{+},~k \in \mathbb{R}\) ，但是 \(\mathtt{atk}\) 和 \(\mathtt{dnf}\) 必须始终非负。 妖怪在环境 \((a,b)\) 中的战斗力为妖怪在该种环境中能达到的最大攻击力和最大防御力之和 \[ \mathtt{strength}(a,b)=\max\{\mathtt{atk}(a,b)\}+\max\{\mathtt{dnf}(a,b)\} \] 环境由 \(a,b\) 两个...

洛谷P3648 [APIO2014] 序列分割 题解 题目链接：P3648 [APIO2014] 序列分割 题意： 你正在玩一个关于长度为 \(n\) 的非负整数序列的游戏。这个游戏中你需要把序列分成 \(k + 1\) 个非空的块。为了得到 \(k + 1\) 块，你需要重复下面的操作 \(k\) 次： 选择一个有超过一个元素的块（初始时你只有一块，即整个序列） 选择两个相邻元素把这个块从中间分开，得到两个非空的块。 每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。 输入格式： 第一行包含两个整数 \(n\) 和 \(k\)。保证 \(k + 1 \leq n\)。 第二行包含 \(n\) 个非负整数 \(a_1, a_2, \cdots, a_n\) \((0 \leq a_i \leq 10^4)\)，表示前文所述的序列。 输出格式： 第一行输出你能获得的最大总得分。 第二行输出 \(k\) 个介于 \(1\) 到 \(n - 1\) 之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第 \(i\) 个整数 \(s_i\)...

洛谷P1397 [NOI2013] 矩阵游戏 题解 题目链接：P1397 [NOI2013] 矩阵游戏 题意： cxy 是个喜欢矩阵的小朋友，有一天她想用电脑生成一个巨大的 \(n\) 行 \(m\) 列的矩阵 (你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质： 若用 \(F_{i, j}\) 来表示矩阵中第 \(i\) 行第 \(j\) 列的元素，则 \(F_{i, j}\) 满足下面的递推式： \[ \begin{cases} F_{1, 1} & = & 1 \\ F_{i, j} & = & a \times F_{i, j-1} + b & j \neq 1 \\ F_{i, 1} & = & c \times F_{i-1, m} + d & i \neq 1 \end{cases} \] 递推式中 \(a, b, c, d\) 都是给定的常数。 现在 cxy 想知道 \(F_{n, m}\) 的值是多少，请你帮助她。由于最终结果可能很大，你只需要输出 \(F_{n, m}\) 除以 \(1...