Q779’s Blog

CF477D Dreamoon and Binary 题解 题目链接：CF477D Dreamoon and Binary 题意： 一天，cxy 在地上发现一个巨大的整数 \(x\) ，然后想把它写成二进制形式。 cxy 凭借她娴熟的技巧，将整数 \(x\) 变成了它的二进制形式。现在, 她想要用下列方式来打印这个数： 一开始, 她有一个整数 \(n=0\) ，然后, 她可以以任何顺序、次数没有限制地执行如下两种操作: 将 \(n\) 打印到已经打印的字符串的右边，如果 \(n>0\), 则不打印前导 \(0\) 。 将 \(n\) 自增 \(1\ (n \leftarrow n+1)\) 。 cxy 认为，如果一串操作序列可以成功地打印出（没有前导 0 的）\(x\) 且以操作1结束，则这串操作序列是理想的。cxy 想知道一共有多少种理想操作序列，以及最短的理想操作序列的长度。 由于答案可能很大，请模 \(10^9+7\) 输出。 输入格式： 输入共一行，包含一个二进制形式表达的正整数 \(x(x < 2^{5000})\) 。 输出格式： 第一行输出理想操作...

证明一个数是无理数 例1：证明 \(\sqrt{2}\) 是无理数。 证明：若 \(\sqrt{2}\) 是有理数，则设它等于 \(\frac{m}{n}~(m,n \in \mathbb{N}_+\land \gcd(m,n) = 1)\) 则 \((\frac{m}{n})^2=\sqrt{2}^2=2\) ，即 \(\frac{m^2}{n^2}=2\) ，可知 \(m^2=2n^2\) ，因此 \(m\) 是偶数。 设 \(m=2k(k \in \mathbb{Z})\) ，则 \(m^2=4k^2=2n^2\) ，可知 \(n^2=2k^2\) ，因此 \(n\) 是偶数。 因为 \(m,n\) 互质，矛盾，所以 \(\sqrt{2}\) 不是有理数，它是无理数。\(\square\) 例2：证明 \(\mathrm{e}\) 是无理数。 证明：由麦克劳林级数可知： \(e = \sum_{i = 0}^{+\infty} \frac{1}{i!}\) ，不知道可以看这篇 假设 \(\mathrm{e} = \frac{a}{b} (a,b \in \mathbb{N...

CF797F Mice and Holes 题解 题目链接：CF797F Mice and Holes 题意： 走廊可以看作是一个一个数轴，上面有 \(n\) 个老鼠和 \(m\) 个洞，第 \(i\) 个老鼠的坐标是 \(x_i\) ，第 \(j\) 个洞的坐标是 \(p_j\) ，可以容纳 \(c_j\) 个老鼠。 如果第 \(i\) 个老鼠去洞 \(j\) ，当然，它需要走 \(\left|x_i-p_j\right|\) 的距离，求所有老鼠都到达某个洞最小距离和。 输入格式： 第一行包含两个正整数 \(n, m(n, m \leq 5000)\), 分别表示老鼠和洞的数量。 第二行包含 \(n\) 个整数 \(x_1, x_2, \cdots, x_n\left(-10^9 \leq x_i \leq 10^9\right), x_i\) 表示第 \(i\) 个老鼠的坐标。 接下来的 \(m\) 行中, 第 \(j\) 行有两个正整数 \(p_j, c_j\left(-10^9 \leq p_j \leq 10^9, 1 \leq c_j \leq 5000\right...

洛谷P2471 [SCOI2007] 降雨量 题解 题目链接：P2471 [SCOI2007] 降雨量 题意： 我们常常会说这样的话：“\(X\) 年是自 \(Y\) 年以来降雨量最多的”。它的含义是 \(X\) 年的降雨量不超过 \(Y\) 年，且对于任意 \(Y < Z < X\)，\(Z\) 年的降雨量严格小于 \(X\) 年。例如 2002、2003、2004 和 2005 年的降雨量分别为 \(4920\)、\(5901\)、\(2832\) 和 \(3890\)，则可以说“2005 年是自 2003 年以来最多的”，但不能说“2005 年是自 2002 年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。 输入格式： 输入仅一行包含一个正整数 \(n\)，为已知的数据。以下 \(n\) 行每行两个整数 \(y_i\) 和 \(r_i\)，为年份和降雨量，按照年份从小到大排列，即 \(y_i<y_{i+1}\)。下一行包含一个正整数 \(m\)，为询问的次数。以下 \(m\) 行每行包含两个数 \(Y\) 和 \(X\)，即询问...

洛谷P3638 [APIO2013] 机器人 题解 题目链接：P3638 [APIO2013] 机器人 题意： VRI（Voltron 机器人学会）的工程师建造了 \(n\) 个机器人。任意两个兼容的机 器人站在同一个格子时可以合并为一个复合机器人。 我们把机器人用 \(1\) 至 \(n\) 编号。如果两个机器人的编号是连续的，那么它们是兼容的，可以合并成一个复合机器人。最初这 \(n\) 个机器人各自都只有唯 一的编号。而一个由两个或以上的机器人合并构成的复合机器人拥有两个编号， 分别是构成它的所有机器人中最小和最大的编号。 例如，\(2\) 号机器人只可以与 \(1\) 号或 \(3\) 号机器人合并。若 \(2\) 号机器人与 \(3\) 号机器人合并，可构成编号为 \(2\sim 3\) 的复合机器人。如果编号为 \(2\sim 3\) 的复合机器人与编号为 \(4\sim 6\) 的复合机器人合并，可构成编号为 \(2\sim 6\) 的复合机器人。当所有机器人合 并以后则构成 \(1\sim n\) 复合机器人。 工程师把这 \(n\) 个机器人放在了一个封闭的房...

洛谷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就会从他的额外修建的道路中选择一条能够重建这两块区域的连通性的，取代原来那条...