Q779’s Blog

洛谷P5838 [USACO19DEC]Milk Visits G 题解 题目链接：P5838 [USACO19DEC]Milk Visits G 题意： Farmer John 计划建造 \(N\) 个农场，用 \(N-1\) 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为 \(1\) 到 \(N\) 之间的一个整数 \(T_i\) 。 Farmer John 的 \(M\) 个朋友经常前来拜访他。在朋友 \(i\) 拜访之时，Farmer John 会与他的朋友沿着从农场 \(A_i\) 到农场 \(B_i\) 之间的唯一路径行走（可能有 \(A_i = B_i\)）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的每个朋友都只喝某种特定品种的奶牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。 请求出每个朋友在拜访过后是否会高兴。 输入格式： 输入的第一行包含两个整数 \(N\)...

Tarjan算法求LCA 这是求一种 LCA 的离线算法，用的不多但是思想很有趣，并且有着美妙的 \(\mathcal{O}(n+q)\) 复杂度。 其实这个算法很简单，不像网上那些瞎七搭八的文章讲的那么复杂 首先考虑将所有问题离线，每个节点记录通过询问相关联的节点，然后从根开始 dfs 。 对于每个节点，遍历它的每个子节点，并把子节点与其合并。这个合并操作我们可以用并查集来维护。 然后我们遍历所有通过询问相关联的节点。如果那个节点被访问过 \(1\) 次了，那么答案就是 \(\mathrm{find}(v)\) 对应的节点。 结合代码来感受一下： void Tarjan(int u) { vis[u] = 1; pre[u] = u; // pre[u] 表示 u 合并到哪里了 for(int i = head[u]; i; i = e[i].next) { int v = e[i].v; if(!vis[v]) { Tarjan(v); merge(u,v); pre[find(u)] = u; } }...

洛谷P1505 [国家集训队]旅游 题解 题目链接：P1505 [国家集训队]旅游 题意： 给定一棵 \(n\) 个节点的树，边带权，编号 \(0 \sim n-1\)，需要支持五种操作： C i w 将输入的第 \(i\) 条边权值改为 \(w\) N u v 将 \(u,v\) 节点之间的边权都变为相反数 SUM u v 询问 \(u,v\) 节点之间边权和 MAX u v 询问 \(u,v\) 节点之间边权最大值 MIN u v 询问 \(u,v\) 节点之间边权最小值 保证任意时刻所有边的权值都在 \([-1000,1000]\) 内。 输入格式： 第一行一个正整数 \(n\)，表示节点个数。 接下来 \(n-1\) 行，每行三个整数 \(u,v,w\)，表示 \(u,v\) 之间有一条权值为 \(w\) 的边，描述这棵树。 然后一行一个正整数 \(m\)，表示操作数。 接下来 \(m\) 行，每行表示一个操作。 输出格式： 对于每一个询问操作，输出一行一个整数表示答案。 数据范围： 对于 \(100\%\) 的数据，\(1\le n,m \le 2\times 1...

洛谷P4092 [HEOI2016/TJOI2016]树 题解 题目链接：P4092 [HEOI2016/TJOI2016]树 题意： 在 1919 年，cxy 刚刚学习了树，非常开心。现在她想解决这样一个问题：给定一颗有根树，根为 \(1\) ，有以下两种操作： 标记操作：对某个结点打上标记。（在最开始，只有结点 \(1\) 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。） 询问操作：询问某个结点最近的一个打了标记的祖先。（这个结点本身也算自己的祖先） 你能帮帮她吗？ 输入格式： 第一行两个正整数 \(N\) 和 \(Q\) 分别表示节点个数和操作次数。 接下来 \(N-1\) 行，每行两个正整数 \(u,v\ (1 \le u,v \le n)\) 表示 \(u\) 到 \(v\) 有一条有向边。 接下来 \(Q\) 行，形如 oper num ，oper 为 C 时表示这是一个标记操作， oper 为 Q 时表示这是一个询问操作。 输出格式： 输出一个正整数，表示结果. 数据范围： \(1 \le N, Q \le 10^5\) 。 注意到一个节点被...

洛谷P3976 [TJOI2015]旅游 题解 题目链接：P3976 [TJOI2015]旅游 题意： 为了提高智商， cxy 准备去往一个新世界去旅游。这个世界的城市布局像一棵树，每两座城市之间只有一条路径可以互达。 每座城市都有一种宝石,有一定的价格。 cxy 为了赚取最高利益,她会选择从 A 城市买入再转手卖到 B 城市。 由于 cxy 买宝石时经常卖萌，因而凡是 cxy 路过的城市，这座城市的宝石价格会上涨。让我们来算算 cxy 旅游完之后能够赚取的最大利润。(如 A 城市宝石价格为 \(v\)，则 cxy 出售价格也为 \(v\)) 输入格式： 第一行输入一个正整数 \(n\) 表示城市个数 接下来一行输入 \(n\) 个正整数表示每座城市宝石的最初价格 \(p\),每个宝石的初始价格不超过 \(100\)。 第三行开始连续输入 \(n-1\) 行,每行有两个数字 \(x\) 和 \(y\)。表示 \(x\) 城市和 \(y\) 城市有一条路径。城市编号从\(1\)开始。 下一行输入一个正整数 \(q\) 表示询问次数。 接下来 \(q\) 行每行输入三个正整数 \(...

洛谷P3950 部落冲突 题解 题目链接：P3950 部落冲突 题意： 在一个叫做 Travian 的世界里，生活着各个大大小小的部落。其中最为强大的是罗马、高卢和日耳曼。他们之间为了争夺资源和土地，进行了无数次的战斗。期间诞生了众多家喻户晓的英雄人物，也留下了许多可歌可泣的动人故事。 其中，在大大小小的部落之间，会有一些道路相连，这些道路是 Travian 世界里的重要枢纽，简单起见，你可以把这些部落与部落之间相连的道路看作一颗树，可见每条道路对于 Travian 世界的重要程度。有了这些道路，建筑工人就可以通过这些道路进行友好外交啦。 然而，事情并不会像想象的那样美好，由于资源的匮乏，相邻的部落（由一条道路相连的部落）之间经常会发生大大小小的冲突事件，更有甚者，会升级为部落之间的大型战争。 为了避免误伤，每当两个相邻的部落之间发生大型战争之时，这两个部落间的道路是不允许通行的，对于一些强大的部落，甚至能与多个相邻的部落同时开战，同样的，这些战争地带的道路十分危险，是不可通行的。 天下之势，分久必合，当两个部落经历了不打不相识的苦战之后，他们可以签订停战协议（暂时停战，以后依...

洛谷P4374 [USACO18OPEN]Disruption P 题解 题目链接：P4374 [USACO18OPEN]Disruption P 题意： Farmer John自豪于他所经营的交通发达的的农场。这个农场是由 \(N\) 块牧场（\(2 \leq N \leq 50,000\)）组成的，\(N-1\) 条双向道路将它们连接起来，每一条道路的都为一单位长度。Farmer John注意到，从任何一块牧场到另一块牧场，都能通过一组合适的道路到达。 尽管FJ的农场现在是连通的，他担心如果有一条道路被阻断会发生什么，因为这事实上会将他的农场分为两个不相交的牧场集合，奶牛们只能够在每一个集合内移动但不能在集合间移动。于是FJ又建造了 \(M\) 条额外的双向道路（\(1 \leq M \leq 50,000\)），每一条的长度都是一个至多为 \(10^9\) 的正整数。奶牛们仍然可以使用原有的道路进行移动，除非其中的某些被阻断了。 如果某条原有的道路被阻断了，农场就会被分为两块不相交的区域，那么FJ就会从他的额外修建的道路中选择一条能够重建这两块区域的连通性的，取代原来那条...

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\) 乘坐 ...