Q779’s Blog

洛谷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...

UOJ156 【清华集训2015】恐怖的奴隶主 题解 题目链接：#156. 【清华集训2015】恐怖的奴隶主 题意： “A fight? Count me in!” 要打架了，算我一个。 “Everyone, get in here!” 所有人，都过来！ 冷酷的酒客（Grim Patron）对战歌指挥官（Warsong Commander）的削弱感到很伤心，他打算用一道数学题来纪念战歌指挥官。 设 \(\left \{ u_i \right \}\) 为一数列 \[ \begin{equation} u_i = a + \frac{b}{u_{i-1}} + \frac{c}{u_{i-1}u_{i-2}} \quad (i \geq 2) \end{equation} \] 已知 \(u_0, u_1, a, b, c, n\)。保证 \(x^3 = a x^2 + b x + c\) 有 \(3\) 个不同的正整数解。 求 \(u_n\)。 输入格式： 输入仅一行，包含 \(6\) 个整数 \(u_0, u_1, a, b, c, n\)。 输出格式： 输出仅一行，包含 \...

洛谷P2512 [HAOI2008]糖果传递 题解 题目链接：P2512 [HAOI2008]糖果传递 题意： 有 \(n\) 个小朋友坐成一圈，每人有 \(a_i\) 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 \(1\)。 输入格式： 小朋友个数 \(n\)，下面 \(n\) 行 \(a_i\)。 输出格式： 求使所有人获得均等糖果的最小代价。 数据范围： 对于 \(100\%\) 的数据 \(n\le 10^6\)。 设最后每个人的糖果为 \(\bar{a} = \frac{1}{n} \sum_{1 \le i \le n} a_i\) ，记 \(b_i = a_i -\bar{a}\) 则题目变为如何将 \(b_i\) 全部转化为 \(0\) 。 设 \(x_i\) 表示最终方案中 \(i\) 给 \(i+1\) 了多少糖果（如果 \(x_i\) 为负，则代表 \(i+1\) 给了 \(i\) 多少） 由 \(b_i=0\) 得 \[ a_i+x_{i-1}+x_i = 0 \] 则答案为 \(\sum_{i=1}^{n} |x_i|\) ，考虑...

洛谷P2215 [HAOI2007]上升序列 题解 题目链接：P2215 [HAOI2007]上升序列 题意： 对于一个给定的 \(S=\{a_1,a_2,a_3,…,a_n\}\) , 若有 \(P=\{a_{x_1},a_{x_2},a_{x_3},…,a_{x_m}\}\) , 满足 \((x_1<x_2<…<x_m)\) 且 \((a_{x_1}<a_{x_2}<…<a_{x_m})\) 。那么就称 \(P\) 为 \(S\) 的一个上升序列。如果有多个 \(P\) 满足条件，那么我们想求字典序最小的那个。 任务： 给出 \(S\) 序列，给出若干询问。对于第 \(i\) 个询问，求出长度为 \(L_i\) 的上升序列，如有多个，求出字典序最小的那个（即首先 \(x_1\) 最小，如果不唯一，再看 \(x_2\) 最小……），如果不存在长度为 \(L_i\) 的上升序列，则打印 Impossible。 输入格式： 第一行一个 \(N\)，表示序列一共有 \(N\) 个元素。 第二行 \(N\) 个数，为 \(a_1, a_2 , \c...

SP2885 WORDRING - Word Rings 题解 题目链接：SP2885 WORDRING - Word Rings 题意： 如果字符串 \(A\) 的结尾两个字符与字符串 \(B\) 的开头两个字符相匹配，我们称 \(A\) 与 \(B\) 能 “ 相连 ” ( 注意： \(A\) 与 \(B\) 能相连，不代表 \(B\) 与 \(A\) 能相连 ) 当若干个串首尾 “ 相连 ” 成一个环时，我们称之为一个环串（一个串首尾相连也算） 我们希望从给定的全小写字符串中找出一个环串，使这个环串的平均长度最长 intercommunicational alkylbenzenesulfonate tetraiodophenolphthalein 如上例：第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串又能与第一个串相连。按此顺序连接，便形成了一个环串。 长度为 \(20+21+24=65\) ( 首尾重复部分需计算两次 ) ，总共使用了 \(3\) 个串，所以平均长度是 \(65/3\approx 21.6667\) 输入格式： 多组数据 每组数据第一行一个...