Q779’s Blog

UOJ48 【UR #3】核聚变反应强度 题解 题目链接：#48. 【UR #3】核聚变反应强度 题意： 著名核物理专家 Picks 提出了核聚变特征值这一重要概念。 核聚变特征值分别为 \(x\) 和 \(y\) 的两个原子进行核聚变，能产生数值为 \(\text{sgcd}(x, y)\) 的核聚变反应强度。 其中， \(\text{sgcd}(x, y)\) 表示 \(x\) 和 \(y\) 的次大公约数，即能同时整除 \(x, y\) 的正整数中第二大的数。如果次大公约数不存在则说明无法核聚变， 此时 \(\text{sgcd}(x, y) = -1\)。 现在有 \(n\) 个原子，核聚变特征值分别为 \(a_1, a_2, \dots, a_n\)。然后 Picks 又从兜里掏出一个核聚变特征值为 \(a_1\) 的原子，你需要计算出这个原子与其它 \(n\) 个原子分别进行核聚变反应时的核聚变反应强度，即 \[ \text{sgcd}(a_1, a_1), \text{sgcd}(a_1, a_2), \dots, \text{sgcd}(a_1, a_n) \]...

洛谷P3983 赛斯石（赛后强化版） 题解 题目链接：P3983 赛斯石（赛后强化版） 题意： 现需上市 \(\mathtt{Need}\) 赛斯重量的赛斯石，卖家想算出这些赛斯石经过某种合并方式来获得的最大收益。然而目前有一个问题，市场在真程大殿附近（真程海洋中心位置），卖家需要租船送赛斯石过去（即不考虑卖家自己租船过去的费用），目前有十种船可以租，载重量从 \(1\mathtt{si}\) 到 \(10\mathtt{si}\) ，每艘船的租价也是有所不同的，如下表所示： 由于真程大殿附近有强烈的赛斯力，导致无法对赛斯石进行任何操作，商家将赛斯石运过来之后就只能按照之前合并好的卖。假设卖家不返回，且这些赛斯石全部能卖出去。现在卖家他要计算总盈利（设总盈利=赛斯石的总收益-租船所需总费用），请你设计一个程序，算出一种最佳方案，以获得最大总盈利。 输入格式： 输入一共有两行 第一行有一个数据 \(\mathtt{Need}\)（赛斯石的总量，单位：\(\mathtt{si}\) ） 第二行有十个数据 \(a_1,a_2,\dots, a_{10}\)（分别为 \(1\math...

UOJ14 【UER #1】DZY Loves Graph 题解 题目链接：#14. 【UER #1】DZY Loves Graph 题意： cxy 开始有 \(n\) 个点，现在她对这 \(n\) 个点进行了 \(m\) 次操作，对于第 \(i\) 个操作 (从 \(1\) 开始编号) 有可能的三种情况： Add a b：表示在 \(a\) 与 \(b\) 之间连了一条长度为 \(i\) 的边 (注意，\(i\) 是操作编号)。保证 \(1\le a,b \le n\) 。 Delete k：表示删除了当前图中边权最大的 \(k\) 条边。保证 \(k\) 一定不会比当前图中边的条数多。 Return：表示撤销第 \(i−1\) 次操作。保证第 \(1\) 次操作不是 Return 且第 \(i−1\) 次不是 Return 操作。 请你在每次操作后告诉 cxy 当前图的最小生成树边权和。如果最小生成树不存在则输出 \(0\)。 输入格式： 第一行包含两个正整数 \(n,m (n\le 3\times 10^5,m\le 5\times 10^5)\) 。表示有 \(n\...

UOJ21 【UR #1】缩进优化 题解 题目链接：#21. 【UR #1】缩进优化 题意： 小 O 是一个热爱短代码的选手。在缩代码方面，他是一位身经百战的老手。世界各地的 OJ 上，很多题的最短解答排行榜都有他的身影。这令他感到十分愉悦。 最近，他突然发现，很多时候自己的程序明明看起来比别人的更短，实际代码量却更长。这令他感到很费解。经过一番研究，原来是因为他每一行的缩进都全是由空格组成的，大量的空格让代码量随之增大。 现在设小 O 有一份 \(n\) 行的代码，第 \(i\) 行有 \(a_i\) 个空格作为缩进。 为解决这一问题，小 O 要给自己文本编辑器设定一个正整数的默认 Tab 宽度 \(x\)，然后对于每一行，编辑器从头至尾不断把连续 \(x\) 个空格替换成一个 Tab，直到剩余空格数不足 \(x\) 个。 最终缩进所占代码量为空格数与 Tab 数的和。请你帮小 O 选择一个合适的 \(x\) ，使得缩进所占代码量最小。 输入格式： 第一行包含一个正整数 \(n(n \leq 10^6)\)，表示代码行数。 接下来 \(n\) 行，第 \(i\) 行包含一个正...

CF822E Liar 题解 题目链接：CF822E Liar 题意： 给定两个字符串 \(s, t\)，长度分别为 \(n, m\)。你需要选择 \(s\) 的若干个两两不相交的子串，然后将它们按照原先在 \(s\) 中出现的顺序合并起来，希望得到 \(t\)。 令 \(f(s, t)\) 表示要选择的 \(s\) 的子串数目的最小值，以便它们的并是串 \(t\)。如果无法合理选择这样的子串，则 \(f(s, t) = +\infty\)。现在 cxy 想知道，对于给定的 \(s, t\)，是否有 \(f(s, t) \leq x\)。 输入格式： 第一行包含一个正整数 \(n,~(n \leq 10^5)\)，表示字符串 \(s\) 的长度。 第二行为一个长度为 \(n\) 的，只包含小写字母 \(\mathtt{a} \sim \mathtt{z}\) 的字符串 \(s\)。 第三行包含一个正整数 \(m,~(m \leq n)\)，表示字符串 \(t\) 的长度。 第四行类似地包含一个长度为 \(m\) 的字符串 \(t\)。 第五行包含一个正整数 \(x,~(x \l...

CF712E Memory and Casinos 题解 题目链接：CF712E Memory and Casinos 题意： 现有一排 \(n\) 个赌场。 cxy 在第 \(i\) 个赌场时有 \(p_i\) 的几率获胜并移动到第 \(i+1\) 个赌场，如果 \(i=n\) 则 cxy 会离开赌场； 同时有 \(1-p_i\)的概率失败并移动到第 \(i-1\) 个赌场，如果\(i=1\) 则 cxy 会离开赌场。 定义 cxy “掌控”一段区间 \([i,j]\) 当且仅当 cxy 完成以下过程： cxy 从 \(i\) 号赌场出发； cxy 从未在 \(i\) 号赌场失败； cxy 某一次在 \(j\) 号赌场获胜并离开。 现在有 \(q\) 次操作，操作有以下两种： \(1\ i\ a\ b\)：令 \(p_i = \frac{a}{b}\)； \(2\ l\ r\)：询问 cxy “掌控”区间 \([l,r]\) 的概率。 保证在任意时刻 \(p_i\) 构成的序列是单调不降的。 关键词：线段树、等比数列求和、概率、DP（思想） 设 \(f(l,r)\)...

DP总结-状压dp 状压dp（状态压缩动态规划）是一种dp。（废话） 状压dp的核心就是把若干状态压缩为一个整数 通常要压缩的元素个数不超过 \(15\) ，此时状态数共有 \(2^{15}=32768\) 。 状压dp更多的是一种思想，常见于数位dp等需要记录大量信息的dp中。 集合的整数表示 注意，当集合元素个数较多的时候，可能需要使用 1ll<<n 或者 1ull<<n 。 基本表示： 空集：0 大小为 \(n\) 的全集： (1 << n) - 1 第 \(i\) 个元素 \(x_i\) ：1 << i 交集： \(S\cap \{x_i\}\) ：(S >> i) & 1 \(S\cap T\)：S & T 并集： \(S \cup \{x_i\}\) ：S | (1 << i) \(S \cup T\) ：S | T 绝对补集： \(\sim\!S\) ：U^S 或 U-S 或 (~S) & U ，U为全集 相对补集： \(S\setminus\{x_i\}\...

AT_arc078_d [ARC078F] Mole and Abandoned Mine 题解 题目链接：AT_arc078_d [ARC078F] Mole and Abandoned Mine 题意： cxy 准备住在一个废弃的矿洞里，矿洞的结构可以用一个包含 \(n\) 个点，\(m\) 条边的连通无向简单图来表示，其中点以 \(1,2,\cdots,n\) 编号。第 \(i\) 条边连接点 \(a_i\) 和 \(b_i\)，并且移除它需要花费 \(c_i\) 元。 cxy 想要移除一些边，使得点 \(1\) 和点 \(n\) 之间有且仅有唯一的路径，请你帮她寻找满足要求所需的最小花费。 注：一条路径 (path) 指的是不能经过重复点的途径 (walk)，一条迹 (trail) 指的是不能经过重复边的途径。 输入格式： n m a1 b1 c1 ⋮ ⋮ ⋮ am bm cm 输出格式： 一行，即答案。 数据范围： 保证是连通简单图。 \(2 \leq n \leq 15,~n - 1 \leq m \leq \binom{n}{2},~1 \leq a_i, b...

CF911F Tree Destruction 题解 题目链接：CF911F Tree Destruction 题意： 给定一棵 \(n(2\le n \le 2\times 10^5)\) 个结点的无根树。 每次挑选这棵树的两个叶子，加上两个叶子之间的边数（距离），然后将其中一个点去掉。 问你重复操作后边数（距离）之和最大可以是多少？ 很有趣的贪心题，并且需要一定代码能力。 尝试一下用Roundgod刚刚教我的方法来做这道题 注：刚刚请教了Roundgod有关贪心题的做法 他说思想是可以考虑两个元素，谁会被优先选。 正好这是一道比较简单的贪心题，可以试一试。 对于两个不同的叶子 \(j,k\) ，如果已经确定了 \(j\) ，怎么找到最优的 \(k\) ？ 这里需要一个结论：无权树上任意一个结点，与它距离最远的结点一定是直径的某个端点。 那么确定了 \(j\) 以后， \(k\) 一定是选择直径端点中较远的那一个。 不同的 \(j\) 对应的 \(k\) 不一定相同，因此考虑 \(k\) 相同时，我们会选哪个 \(j\) 如果 \(j_1,j_2\) 都是非直径端点的...

洛谷P2331 [SCOI2005]最大子矩阵 题解 题目链接：P2331 [SCOI2005]最大子矩阵 题意： 这里有一个 \(n\times m\) 的矩阵，请你选出其中 \(d\) 个子矩阵，使得这个 \(d\) 个子矩阵分值之和最大。注意：选出的 \(d\) 个子矩阵不能相互重叠。 输入格式： 第一行为 \(n,m,d~(1\le n\le 100,~1\le m\le 2,~1\le d\le 10)\) ，接下来 \(n\) 行描述矩阵每行中的每个元素的分值（每个元素的分值的绝对值不超过 \(32767\) ）。 输出格式： 只有一行为 \(d\) 个子矩阵分值之和最大为多少。 注意到 \(m\) 最多只有 \(2\) ，因此分别讨论 下文中用 \(a\uparrow b+c\) 表示 \(a\leftarrow \max\{a,b+c\}\)。 当 \(m=1\) 时， 题目转化为限制个数不超过 \(d\) 个的最大子段和 设 \(g_{i,j}\) 表示只考虑前 \(i\) 个数分了 \(j\) 个矩形（子段）的最大价值，则 \[ g_{i,j} = \ma...

洛谷P2486 [SDOI2011]染色 题解 题目链接：P2486 [SDOI2011]染色 题意： 给定一棵 \(n\) 个节点的无根树，共有 \(m\) 个操作，操作分为两种： 将节点 \(a\) 到节点 \(b\) 的路径上的所有点（包括 \(a\) 和 \(b\)）都染成颜色 \(c\)。 询问节点 \(a\) 到节点 \(b\) 的路径上的颜色段数量。 颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。 输入格式： 输入的第一行是用空格隔开的两个整数，分别代表树的节点个数 \(n\) 和操作个数 \(m\)。 第二行有 \(n\) 个用空格隔开的整数，第 \(i\) 个整数 \(w_i\) 代表结点 \(i\) 的初始颜色。 第 \(3\) 到第 \((n + 1)\) 行，每行两个用空格隔开的整数 \(u, v\)，代表树上存在一条连结节点 \(u\) 和节点 \(v\) 的边。 第 \((n + 2)\) 到第 \((n + m + 1)\) 行，每行描述一个操作，其格式为： 每行首先有一个字符 \(op\)，代...

CF491B New York Hotel 题解 题目链接：CF491B New York Hotel 题意： New York 是个由 \(N\) 条垂直道路 (编号为 \(1\sim N\)) 和 \(M\) 条水平道路 (编号为 \(1\sim M\) ) 组成的城市。 \(C\) 个朋友分别住在该城市中的 \(C\) 个酒店中，这些酒店分别坐落在垂直道路和水平道路的相交处。由于他们要庆祝 cxy 的生日，于是他们想去 \(H\) 个餐馆中的一个 (当然，这 \(H\) 个餐厅也坐落在垂直道路和水平道路的相交处)。 他们想知道，这 \(C\) 个酒店到餐馆的最大距离 (即最远的酒店到餐厅的距离) 的最小可能值是多少。帮助朋友们确定一个合适的餐厅以庆祝生日。 假设相邻两个相交处的距离均等于 \(1\)。 输入格式： 第一行包含两个正整数 \(N,M ~(N,M\le 10^9)\) ，描述城市的大小。 第二行包含一个正整数 \(C~ (C\le 10^5)\)，表示朋友们住的酒店个数。 接下来的 \(C\) 行，每行两个正整数 \(x,y ~(x\le N,y\le M)\...