Q779’s Blog

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

洛谷P2470 [SCOI2007]压缩 题解 题目链接：P2470 [SCOI2007]压缩 题意： 给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母 \(\tt{R}\) 与 \(\tt{M}\) ，其中 \(\tt{M}\) 标记重复串的开始，\(\tt{R}\) 重复从上一个 \(\tt{M}\)（如果当前位置左边没有 \(\tt{M}\)，则从串的开始算起）开始的解压结果（称为缓冲串）。 \(\mathtt{bcdcdcdcd}\) 可以压缩为 \(\mathtt{bMcdRR}\)，下面是解压缩的过程： 已经解压的部分 解压结果 缓冲串 \(\mathtt{b}\) \(\mathtt{b}\) \(\mathtt{b}\) \(\mathtt{bM}\) \(\mathtt{b}\) \(\varnothing\) \(\mathtt{bMc}\) \(\mathtt{bc}\) \(\mathtt{c}\) \(\mathtt{bMcd}\) \(\ma...

CF727F Polycarp’s problems 题解 题目链接：CF727F Polycarp’s problems 题意： 有 \(n\) 道题目，每道题目有一个质量 \(a_i\) (可正可负)，题目按照一定顺序排列。cxy 作为出题人，由于不想让参赛者认为是毒瘤题，因此决定删减一些题目。 不妨设一个参赛者的初始心情为 \(q\)，他会按照顺序阅读这些题目。每读一道题目，他的心情会随着题目的质量改变。意思是说，如果他读了一道质量为 \(b\) 的题目，他的心情就会增加 \(b\) (即心情为 \(q, q+a_1, q+a_1+a_2, \cdots\))。 如果在读了某些题目后，参赛者的心情变为了负数，则他会立即停止阅读且认为这个题库是毒瘤题。 cxy 想知道，为了不让参赛者认为是毒瘤题 (即要使他们的心情时刻保持非负)，最少需要 (在题库中) 移除多少道题目 (其余题目的顺序保持不变)。由于 cxy 不知道参赛者的初始心情，但她有 \(m\) 次猜测 ” 参赛者的初始心情 \(q = b_i\)“。 对于她的每次猜测，找到满足条件的移除题目数的最小值。 输入格式：...

CF832C Strange Radiation 题解 题目链接：CF832C Strange Radiation 题意： \(n\) 个人站在一个数轴上，它们的坐标均为正整数，且小于 \(10^6\)。对于每个人，都有一个面对的方向 (左和右) 以及它的速度。 你可以在一个坐标为非负整数，且不超过 \(10^6\) 的位置上放置一个炸弹 ，并引爆它，这时，所有的人都会按照他们面对的方向以他们的速度跑起来。与此同时，两条奇怪的射线（应该是气流吧）会以 \(v\) 的速度从炸弹的位置发射出来——一条向右、一条向左。当然，速度 \(v\) 严格大于人的跑步速度。 这些射线之所以奇怪，是因为如果某一个时刻，射线的位置与某个人的位置重合，且该射线的方向与那个人跑步的方向一致，则他跑步的速度会立即增加射线的速度 \(v\)。 你需要在一个地方放置一个炸弹，使得目标时间——即有一个人到达过位置 \(0\)，且还有一个人到达过位置 \(10^6\) 的时间——尽可能地小。换句话说，找到最小的时间 \(t\)，使得存在那么一个放炸弹的位置，使得前 \(t\) 个单位时间内有人到达过位置 \(0...

CF618F Double Knapsack 题解 题目链接：CF618F Double Knapsack 题意： 给你两个可重集 \(A, B\)，\(A, B\) 的元素个数都为 \(n\)，它们中每个元素的大小 \(x\in [1,n]\)。请你分别找出 \(A, B\) 的子集，使得它们中的元素之和相等。 \(n\leq 10^6\)。 什么神仙构造题 姑且认为是打表找规律的构造题吧 结论：一定有解，并且存在连续子序列（子段）的解。 这里的连续子序列甚至不用排序，就是 \(A,B\) 任意排列中的某个连续子序列 证明：（鸽巢原理） 设 \(A_i = \sum_{j=1}^{i}a_j,B_i=\sum_{j=1}^{i}b_j\) ，并定义 \(A_0 = B_0=0\) 不失一般性1，我们假设 \(A_n \le B_n\) 。 定义 \(f : \mathbb{N} \to \mathbb{N}\) ， \(f(i)~(0\le i \le n)\) 表示满足 \(A_i \ge B_{f(i)}\) 的最大整数，显然 \(0\le f(i) \le n\) 。...

洛谷P4165 [SCOI2007]组队 题解 题目链接：P4165 [SCOI2007]组队 题意： NBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为 \(\min V\)，身高最矮的球员高度为 \(\min H\)，那么这支球队的所有队员都应该满足: \[ A \times ( \mathtt{height} – \min H ) + B \times ( \mathtt{speed} – \min V ) \le C \] 其中 \(A,B,C\) 为给定的经验值。这个式子很容易理解，如果一个球队的球员速度和身高差距太大，会造成配合的不协调。 请问作为球队管理层的你，在 \(N\) 名选秀球员中，最多能有多少名符合条件的候选球员。 输入格式： 第一行四个数 \(N,A,B,C\) 下接 \(N\) 行每行两个数描述一个球员的 \(\mathtt{height}\) 和\(\mathtt{speed}\) 。 输出格式： 最多候选球员数目。 数据范围： \(N \le 5\times 10^3\) ，\(...

洛谷P2511 [HAOI2008]木棍分割 题解 题目链接：P2511 [HAOI2008]木棍分割 题意： 有 \(n\) 根木棍, 第 \(i\) 根木棍的长度为 \(L_i\) ， \(n\) 根木棍依次连结了一起，总共有 \(n-1\) 个连接处。现在允许你最多砍断 \(m\) 个连接处，砍完后 \(n\) 根木棍被分成了很多段，要求满足总长度最大的一段长度最小，并且输出有多少种砍的方法使得总长度最大的一段长度最小，并将结果 \(\bmod 10007\) 。 输入格式： 第一行有 \(2\) 个数 \(n,m\) 。 接下来 \(n\) 行每行一个正整数 \(L_i\) ，表示第 \(i\) 根木棍的长度。 输出格式： 输出有 \(2\) 个数，第一个数是总长度最大的一段的长度最小值，第二个数是有多少种砍的方法使得满足条件。 数据范围： \(1 \le n\le 5\times 10^4,~ 0\le m\le \min\{n-1,1000\},~1\le L_i\le 1000\) 第一问比较简单，考虑二分然后贪心地去切就好了 考虑第二问怎么做。一眼计数型线性d...

CF578D LCS Again 题解 题目链接：CF578D LCS Again 题意： 给定一个字符串 \(S\)，求有多少个与 \(S\) 等长字符串 \(T\)，满足 \(\mathrm{LCS}(S,T)=|S|-1\)，其中 \(S,T\) 只包含前 \(m\) 个小写字母。 LCS（最长公共子序列） 输入格式： 第一行包括两个数字 \(n\) 和 \(m\)，第二行是给定的字符串 \(S\)。 输出格式： 输出一行一个整数表示答案。 一眼hash，然后发现假了。。。 这里就讲讲dp套dp解法，其他解法可以看这篇博客 考虑经典的LCS（最长公共子序列） \(f_{i,j}\) 表示第一个串前 \(i\) 个字符和第二个串前 \(j\) 个字符的最长公共子序列 显然 \(f_{i,j}\) 只与 \(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}\) 有关 而我们要求的就是 \(f_{i,j}=n-1\) 的方案数 从 \(f_{i,j}=n-1\) 可以得到 \[ \min \{i,j\} -1 \le f_{i,j} \le \min \{ i,...

洛谷P4643 [国家集训队]阿狸和桃子的游戏 题解 题目链接：P4643 [国家集训队]阿狸和桃子的游戏 题意： 阿狸和桃子正在玩一个游戏，游戏是在一个带权图 \(G=(V, E)\) 上进行的，设节点权值为 \(w(v)\) ，边权为 \(c(e)\) 。游戏规则是这样的： 阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。 为了保证公平性，节点的个数 \(N\) 为偶数。 经过 \(N/2\) 轮游戏之后，两人都得到了一个顶点集合。对于顶点集合 \(S\) ，得分计算方式为 \[ \sum_{v \in S}w(v) + \sum_{e=(u,v)\in E \land u,v\in S}c(e) \] 由于阿狸石头剪子布输给了桃子，所以桃子先染色。两人都想要使自己的分数比对方多，且多得越多越好。如果两人都是采用最优策略的，求最终桃子的分数减去阿狸的分数。 输入格式： 输入第一行包含两个正整数 \(N\) 和 \(M\) ，分别表示图 \(G\) 的节点数和边数，保证 \(N...