Q779’s Blog

note[12] 问：试构造一个形如两个整数相除的分数，其值为 \(0.123456789123456789\cdots\) （无限循环小数）。 解： 令 \(k = 0.123456789123456789\cdots\) ，则 \(10^9k = 123456789.123456789\cdots\) 那么 \((10^9 - 1)k = 123456789\) ，即 \(k = \frac{123456789}{10^9 - 1}\) 。 参考文献： [1] https://www.zhihu.com/question/571844688/answer/2797981347

CF431E Chemistry Experiment 题解 题目链接：CF431E Chemistry Experiment 题意： 有 \(n\) 支试管，每支试管装有 \(h_i\ \mathrm{ml}\) 的水银。 \(q\) 次操作，操作有两种： 1 p x：倒掉试管 \(p\) 的水银修改为 \(x\ \mathrm{ml}\)。 2 v：将 \(v\ \mathrm{ml}\) 水任意分配至 \(n\) 支试管里，最小化有水的试管中最大体积，输出这个最小值 误差不超过 \(10^{-4}\) 算作正确（这个操作只是一次假想，不会真的把水倒进试管里）。 输入格式： The first line contains two integers \(n\) and \(q\) ( \(1\le n,q\le 10^{5}\) ) — the number of tubes ans the number of experiment steps. The next line contains \(n\) space-separated integers: \(h_{1},...

洛谷P3771 [CTSC2017]网络 题解 题目链接：P3771 [CTSC2017]网络 题意： 一个一般的网络系统可以被描述成一张无向连通图。图上的每个节点为一个服务器，连接服务器与服务器的数据线则看作图上的一条边，边权为该数据线的长度。两个服务器之间的通讯距离定义为其对应节点之间最短路的长度。 现在，考虑一个当前图结构为树的网络系统。你作为该网络系统的管理员，被要求在这个系统中新加入一条给定长度的数据线。数据线可以连在任意两个服务器上。你的任务是，求出在所有合法的方案中，通讯距离最远的两个服务器之间的最小距离。 输入格式： 输入包含多组数据。对于每组数据，输入的第一行包含二个正整数 \(n,m\) ，其中 \(n\) 表示服务器个数，\(m\) 为新加入数据线的长度。 接下来 \(n − 1\) 行，第 i 行有三个正整数 \(a_i, b_i, l_i\) ，表示有一条长度为 \(l_i\) 的数据线连接服务器 \(a_i, b_i\)。服务器的编号为 \(1 \sim n\) 。 输入的末尾以两个 0 作为结束。 输出格式： 对于每组数据，输出一行一个整数，描述在...

CF187D BRT Contract 题解 题目链接：CF187D BRT Contract 题意： cxy 每天都要通过一条路从家到学校，这条路的起点是 cxy 家，终点则是学校。 这条路中间还有 \(n\) 个路口，从第 \(i - 1\) 个路口走到第 \(i\) 个路口需要 \(d_i\) 秒，每个路口都有一个红绿灯。 更具体地，绿灯持续时间是 \(g\) 秒，红灯持续时间是 \(r\) 秒。每天从第 \(0\) 秒开始，所有灯都是绿灯，持续 \(g\) 秒之后变为红灯，再过 \(r\) 秒变成绿灯，以此类推，并且同一时刻所有灯都是相同状态。 当cxy到达一个路口，若是绿灯则可直接通过，若是红灯则需原地等待至绿灯。 若到达某一路口时灯的状态正好发生改变，则视到达路口时灯的颜色为其改变后的颜色，例如第 \(g\) 秒到达一个路口则视为遇到红灯。 现在 cxy 预计了接下来 \(q\) 天从家出发的时间，第 \(j\) 天将会在第 \(t_j\) 秒从家出发，她希望你告诉她每天到达学校的最早时间。你可以假定一天内 cxy 一定可以到达学校。 输入格式： The firs...

洛谷P6302 [NOI2019] 回家路线 加强版 题解 题目链接：P6302 [NOI2019] 回家路线 加强版 题意： 喵喵国的铁路系统中有 \(n\) 个站点，从 \(1 - n\) 编号。小喵准备从 \(1\) 号站点出发，乘坐列车回到猫窝所在的 \(n\) 号站点。它查询了能够乘坐的列车，这些列车共 \(m\) 班，从 \(1 - m\) 编号。小喵将在 \(0\) 时刻到达 \(1\) 号站点。对于 \(i\) 号列车，它将在时刻 \(p_i\) 从站点 \(x_i\) 出发，在时刻 \(q_i\) 直达站点 \(y_i\)，小喵只能在时刻 \(p_i\) 上 \(i\) 号列车，也只能在时刻 \(q_i\) 下 \(i\) 号列车。小喵可以通过多次换乘到达 \(n\) 号站点。一次换乘是指对于两班列车，假设分别为 \(u\) 号与 \(v\) 号列车，若 \(y_u = x_v\) 并且 \(q_u \leq p_v\)，那么小喵可以乘坐完 \(u\) 号列车后在 \(y_u\) 号站点等待 \(p_v - q_u\) 个时刻，并在时刻 \(p_v\) 乘坐 ...

洛谷P3694 邦邦的大合唱站队 题解 题目链接：P3694 邦邦的大合唱站队 题意： BanG Dream!里的所有偶像乐队要一起大合唱，不过在排队上出了一些问题。 \(n\) 个偶像排成一列，他们来自 \(m\) 个不同的乐队。每个团队至少有一个偶像。 现在要求重新安排队列，使来自同一乐队的偶像连续的站在一起。重新安排的办法是，让若干偶像出列（剩下的偶像不动），然后让出列的偶像一个个归队到原来的空位，归队的位置任意。 请问最少让多少偶像出列？ 输入格式： 第一行 \(2\) 个整数 \(n,m\)。 接下来 \(n\) 行，每行一个整数 \(a_i(1\le a_i \le m)\) ，表示队列中第 \(i\) 个偶像的团队编号。 输出格式： 一个整数，表示答案。 数据范围： \(1\le n\le 10^5,~ m\le 20\) 可以发现，我们并不关心换了哪些人，而在乎换了多少人。 例如一个段应当放满 \(\mathtt{B}\) 的人，结果里面 \(\mathtt{B : C : D} = \mathtt{3 : 2 : 3}\) ，那我们肯定是把剩下那五个换成后面...

OI易错点-图论 一、图论基础 【易错点】 ❗️新建虚拟结点 \(\boldsymbol{0}\) ，会向至多 \(n\) 个结点连边，空间要开 \(\boldsymbol{2}\) 倍 ❗️ 无向图+链式前向星， \(\boldsymbol{2}\) 倍空间 多组数据不要忘了清空 pos 邻接矩阵处理重边 down(g[u][v], w) （无向图别忘了 g[v][u] ） ❗️树的欧拉序长度为 \(3n\) ，因此线段树要开 \(12n\)❗️ 【算法相关】 自环要写 if(u==v)continue; 处理！ ❗️树上dp题获取子节点个数，不可以直接用 vec[u].size() ，因为可能有重边❗️ 二叉树的树高并不是固定 \(\mathcal{O}(\log n)\) 的，链也满足二叉树的定义，概念不要混淆了。 二、最短路算法 【易错点】 \(\text{Dijkstra}\) 不要忘记把起点入队 \(\text{Floyd}\) 相关问题注意 \(\text{INF}\) 值的设置不能过大 如 0x3f3f3f3f3f3f3f3f 在 f[i][j]+g[i...

note[11] 解方程：\(a^2 + a^3 = 392\) 解1： 容易发现 \(a = 7\) 是一个解。考虑因式分解（会用到 多项式除法）： \[ \begin{aligned} & a^2+a^3-392=0 \\[6pt]& (a-7)(a^2+8 a+56)=0 \end{aligned} \] 转化为解方程 \(a^2+8 a+56 = 0\) ，易得原方程解为 \[ a_1 = 7,~a_2 = -4+2\sqrt{10}i,~a_3 = -4-2\sqrt{10}i \] 解2： 朴素的死算方法。 首先用 note 4 讲到过的方法消掉二次项，令 \(b = a + \frac{1}{3}\) 得 \[ b^3-\frac{1}{3} b-\frac{10582}{27}=0 \] 根据卡尔达诺公式(Cardano formula)，得 \[ p = -\frac{1}{3}, ~q =-\frac{10582}{27} \] 则方程的解为 \[ \begin{aligned} & a_1=u+v-\frac{1}{3}=\sqr...

note[10] 问：甲有 \(101\) 个硬币，乙有 \(100\) 个硬币，两人随机撒在地面上，甲比乙正面朝上多的概率是多少 解：答案为 \(\frac{1}{2}\) 证明1： 考虑“甲比乙正面朝上多”和“甲比乙反面朝上多”这两个事件。 因为甲的硬币总数比乙多，这两件事至少发生一个。 然而，这两个事件又不可能同时发生，否则甲至少要比乙多两个硬币才行。 所以，要么甲比乙正面朝上多，要么甲比乙反面朝上多。 根据对称性，这两个事件是等可能的，所以概率各为 \(\frac{1}{2}\)。 证明2： 甲先投 \(100\) 枚，记此时甲乙朝上硬币数量相等概率为 \(p\) ， 则甲此时比乙多的概率为 \(\frac{1}{2}(1-p)\) ， 故甲投下第 \(101\) 枚硬币后朝上硬币比乙多的概率为： \[ \frac{1}{2}(1-p) + \frac{1}{2}p = \frac{1}{2} \] 参考文献： [1] https://www.zhihu.com/question/444606927/answer/1749535576 [2] https://www.z...

洛谷P5094 [USACO04OPEN] MooFest G 加强版 题解 题目链接：P5094 [USACO04OPEN] MooFest G 加强版 题意： 每一年，约翰的 \(n\) 只奶牛参加奶牛狂欢节。这是一个全世界奶牛都参加的大联欢。狂欢节包括很多有趣的活动，比如干草堆叠大赛、跳牛栏大赛，奶牛之间有时还相互扎屁股取乐。当然，她们会排成一列嚎叫，来欢庆她们的节日。奶牛们的叫声实在刺耳，以致于每只奶牛的听力都受到不同程度的损伤。现在告诉你奶牛 \(i\) 的听力为 \(v_i\) ，这表示如果奶牛 \(j\) 想说点什么让她听到，必须用高于 \(v_i \times \mathrm{dis}(i,j)\) 的音量。因此，如果奶牛 \(i\) 和 \(j\) 想相互交谈，她们的音量必须不小于 \(\max (v_i,v_j) \times \mathrm{dis}(i,j)\)。其中 \(\mathrm{dis}(i,j)\) 表示她们间的距离。 现在 \(n\) 只奶牛都站在一条直线上了，每只奶牛还有一个坐标 \(x_i\)。如果每对奶牛都在交谈，并且使用最小音量，那...

洛谷P8867 [NOIP2022] 建造军营 题解 题目链接：P8867 [NOIP2022] 建造军营 题意： A 国与 B 国正在激烈交战中，A 国打算在自己的国土上建造一些军营。 A 国的国土由 \(n\) 座城市组成，\(m\) 条双向道路连接这些城市，使得任意两座城市均可通过道路直接或间接到达。A 国打算选择一座或多座城市（至少一座），并在这些城市上各建造一座军营。 众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B 国将会于不久后袭击 A 国的一条道路，但具体的袭击目标却无从得知。如果 B 国袭击成功，这条道路将被切断，可能会造成 A 国某两个军营无法互相到达，这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路（可以是一条或多条，也可以一条也不看守)，A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。 A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出...

洛谷P5507 机关 题解 题目链接：P5507 机关 题意： cxy 成功脱单后，在npy家里发现了一扇暗门，但是这扇门是锁着的 这扇门上有一个机关，上面一共有 \(12\) 个旋钮，每个旋钮有 \(4\) 个状态，将旋钮的状态用数字 \(1\) 到 \(4\) 表示 每个旋钮只能向一个方向旋转（状态：\(1\to 2\to 3\to 4\to 1\) ），在旋转时，会引起另一个旋钮也旋转一次（方向相同，不会引起连锁反应），同一旋钮在不同状态下，可能会引起不同的旋钮旋转（在输入中给出） 当所有旋钮都旋转到状态 \(1\) 时，机关就打开了 由于旋钮年久失修，旋转一次很困难，而且时间很紧迫（指想和npy去贴贴） 因此她希望用最少的旋转次数打开机关，这个任务就交给你了 输入格式： \(12\) 行，每行 \(5\) 个整数，描述机关的状态 第 \(i\) 行第一个整数 \(s_i\) 表示第 \(i\) 个旋钮的初始状态是 \(s_i\) 接下来 \(4\) 个整数 \(a_{i,j},j=1,2,3,4\) 表示这个旋钮在状态 \(j\) 时旋转，会引起第 \(a_{i,j}\...