Q779’s Blog

洛谷P2766 最长不下降子序列问题 题解 题目链接：P2766 最长不下降子序列问题 题意： 给定正整数序列 \(x_1 \ldots, x_n\)。 计算其最长不下降子序列的长度 \(s\)。 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 \(s\) 的不下降子序列。 如果允许在取出的序列中多次使用 \(x_1\) 和 \(x_n\)（其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个不同的长度为 \(s\) 的不下降子序列。 令 \(a_1, a_2, \ldots, a_s\) 为构造 \(S\) 时所使用的下标，\(b_1, b_2, \ldots, b_s\) 为构造 \(T\) 时所使用的下标。且 \(\forall i \in [1,s-1]\)，都有 \(a_i \lt a_{i+1}\)，\(b_i \lt b_{i+1}\)。则 \(S\) 和 \(T\) 不同，当且仅当 \(\exists i \in [1,s]\)，使得 \(a_i \neq b_i\)。 输入格式： 第一行有一个正整数 \(n\)，表示给定序列的...

洛谷P2763 试题库问题 题解 题目链接：P2763 试题库问题 题意： 假设一个试题库中有 \(n\) 道试题。每道试题都标明了所属类别。 现要从题库中抽取 \(m\) 道题组成试卷。 并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 注意，同一道题可能有多个类别属性，但是每道题在组卷时只能归类于一种类型。 对于给定的组卷要求，计算满足要求的组卷方案。 输入格式： 第一行有两个正整数 \(k\) 和 \(n\)。\(k\) 表示题库中试题类型总数，\(n\) 表示题库中试题总数。 第二行有 \(k\) 个正整数，第 \(i\) 个正整数表示要选出的类型 \(i\) 的题数。这 \(k\) 个数相加就是要选出的总题数 \(m\)。 接下来的 \(n\) 行给出了题库中每个试题的类型信息。每行的第一个正整数 \(p\) 表明该题可以属于 \(p\) 类，接着的 \(p\) 个数是该题所属的类型号。 输出格式: 输出共 \(k\) 行，第 \(i\) 行输出 i: 后接类型 \(i\) 的题号。 如果有多个满足要求的方案，只要输出一个方案。 如果问题无解，则输出No ...

洛谷P5358 [SDOI2019]快速查询 题解 题目链接：洛谷P5358 [SDOI2019]快速查询 题意： 给定一个长度为 \(n\) 的整数数列，里面的元素依次编号为 \(a_1,~a_2,~a_3,~\dots,~a_n\)。初始的时候，所有元素都为零。现在按照时间顺序提供了若干次关于这个数列的修改或询问，每一次修改或询问一定为以下六种情况之一： 1 i x ：将 \(a_i\) 赋值为给定整数 \(x\)； 2 x ：将所有元素同时加上 \(x\)； 3 x ：将所有元素同时乘上 \(x\)； 4 x ：将所有元素同时赋值为 \(x\)； 5 i ：询问第 \(i\) 个元素 \(a_i\) 现在的值是多少； 6 ：询问现在所有元素的和。 输入格式： 为了避免读入太大，输入文件采取如下的形式。 第一行给定整数 \(n\)，表示给定数列长度为 \(n\)。 第二行给定整数 \(q\)，并且之后的 \(q\) 行，每一行提供一个修改或询问，输入的格式与题目所述一致，请参见样例。 我们称上述给定的修改或询问为标准操作。 之后给定一个整数 \(t\)，并且之后的 \(...

SP1557 GSS2 - Can you answer these queries II 题解 题目链接：SP1557 GSS2 - Can you answer these queries II 题意： 给定一个长度为 \(n\) 的序列 \(a_i\) 。 \(q\) 次询问，查询区间最大子段和，相同的数只算一次。选出的子段可以为空 数据范围： \(1\le n,q \le 10^5,~ |a_i| \le 10^5\) 。 真就加了一句话就比 GSS1 难了 \(+\infty\) 倍（悲） 感觉这题是 GSS 系列第二难的题。 因为相同的数只能算一次，所以直接维护那 \(4\) 个信息就不太行了。 想起来一道题叫 HH 的项链，这题的思想和那道题有一些相似。 考虑从左往右依次加入每个元素，记 \(\mathtt{pre}(a_i)\) 表示 \(a_i\) 上次出现的位置。 对于第 \(i\) 个元素 \(a_i\) ，它能产生贡献的范围为 \([\,\mathtt{pre}(a_i) + 1, i-1\,]\) 任意 \(l~(\mathtt{pre}(a_i) ...

洛谷P5568 [SDOI2008] 校门外的区间 题解 题目链接：P5568 [SDOI2008] 校门外的区间 题意： 受校门外的树这道经典问题的启发，cxy 根据基本的离散数学的知识，抽象出 \(5\) 种运算维护集合 \(S\) （\(S\) 初始为空）并最终输出 \(S\)。现在，请你完成这道校门外的树之难度增强版——校门外的区间。 五种运算如下： U T：\(S = S \cup T\) I T：\(S = S \cap T\) D T：\(S = S - T\) C T：\(S = T - S\) S T：\(S = S \oplus T\) 集合的基本运算操作定义如下： \(A \cup B\)：\(\{x | x \in A \vee x \in B\}\) \(A \cap B\)：\(\{x | x \in A \wedge x \in B\}\) \(A - B\)：\(\{x | x \in A \wedge x \notin B\}\) \(A \oplus B\)：\((A-B)\cup (B-A)\) 输入格式： 输入 \(M\) 行。 ...

洛谷P4137 Rmq Problem / mex 题解 题目链接：P4137 Rmq Problem / mex 题意： 有一个长度为 \(n\) 的数组 \(\{a_1,a_2,\ldots,a_n\}\)。 \(m\) 次询问，每次询问一个区间内最小没有出现过的自然数。 输入格式： 第一行，两个正整数 \(n,m\)。 第二行，\(n\) 个非负整数 \(a_1, a_2, \ldots , a_n\)。 接下来 \(m\) 行，每行两个正整数 \(l,r\)，表示一次询问。 输出格式： 输出 \(m\) 行，每行一个数，依次表示每个询问的答案。 数据范围： \(1\leq n,m\leq 2\times {10}^5,~1\leq l\leq r\leq n,~0\leq a_i\leq 2\times 10^5\) 线段树上二分经典题，维护区间 \(\mathrm{mex}\) 。 建一棵可持久化权值线段树，然后从左往右扫一遍 每次修改当前权值对应的「最后一次出现的位置」为「当前位置」 查询区间 \([l,r]\) 时，答案就是第 \(r\) 棵线段树上，第一个「最...

UOJ340 【清华集训2017】小 Y 和恐怖的奴隶主 题解 题目链接：#340. 【清华集训2017】小 Y 和恐怖的奴隶主 题意： 小 Y 是一个喜欢玩游戏的 OIer。一天，她正在玩一款游戏，要打一个 Boss。 虽然这个 Boss 有 \(10^{100}\) 点生命值，但它只带了一个随从——一个只有 \(m\) 点生命值的 “恐怖的奴隶主”。 这个 “恐怖的奴隶主” 有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即生命值 \(\leq 0\)），且 Boss 的随从数量小于上限 \(k\)，便会召唤一个新的具有 \(m\) 点生命值的 “恐怖的奴隶主”。 现在小 Y 可以进行 \(n\) 次攻击，每次攻击时，会从 Boss 以及 Boss 的所有随从中的等概率随机选择一个，并扣减 \(1\) 点生命值，她想知道进行 \(n\) 次攻击后扣减 Boss 的生命值点数的期望。为了避免精度误差，你的答案需要对 \(998244353\) 取模。 输入格式： 从标准输入读入数据。 输入第一行包含三个正整数 \(T, m, k\)，\(T\) 表示询问组数，\(m, k...

SP1043 GSS1 - Can you answer these queries I 题解 题目链接：SP1043 GSS1 - Can you answer these queries I 题意： 给定一个长度为 \(n\) 的序列 \(a_i\) 。 \(q\) 次询问，查询区间最大子段和 数据范围： \(1\le n,q \le 5\times 10^4,~ |a_i| \le 2\times10^4\) 。 纯粹是为了凑齐才写的，详见 GSS3 线段树经典题。我们需要维护总和、最大前缀、最大后缀、最大子段和。 \[ \mathtt{sum[u]} = \mathtt{sum[l]} + \mathtt{sum[r]} \\\mathtt{pre[u]} = \max\{\mathtt{pre[l]},~\mathtt{sum[l]}+\mathtt{pre[r]}\} \\\mathtt{suf[u]} = \max\{\mathtt{suf[r]},~\mathtt{sum[r]}+\mathtt{suf[l]}\} \\\mathtt{res[u]} = \m...

SP2916 GSS5 - Can you answer these queries V 题解 题目链接：SP2916 GSS5 - Can you answer these queries V 题意： 多组数据。每组数据给定一个长度为 \(n\) 的序列 \(a_i\) 。 \(q\) 次询问，查询左端点在 \([x_1, y_1]\) 之间，且右端点在 \([x_2, y_2]\) 之间的最大子段和 数据保证 \(x_1\leq x_2,y_1\leq y_2\) ，但是不保证端点所在的区间不重合。 数据范围： \(1 \le T\le 5, ~1\le n \le 10^4,~ |a_i| \le 10^4,~1\le q \le 10^4\) 。 首先要先做下 GSS1 或 GSS3 ，知道怎么用线段树维护区间最大子段和。 然后这道题其实只是在询问上做了一些修改。 对于 \(r_1 < l_2\) 的情况，很简单，就是 \([l_1,r_1]\) 的 \(\mathtt{pre}\) 加 \([l_2,r_2]\) 的 \(\mathtt{suf}\) 加 \(...

洛谷P4314 CPU 监控 题解 题目链接：P4314 CPU 监控 题意： 维护一个数据结构，支持 询问区间最大值。 询问区间历史最大值。 区间加法。 区间赋值。 数据范围： \(1\le T,E\le 10^5,~1\le X\le Y\lt T,~-2^{31}\leq Z\lt 2^{31}\)。 对于每个结点，我们需要维护 \(6 + 1\) 个值，分别对应 加法标记、历史最大加法标记、赋值标记、历史最大赋值标记、最大值、历史最大值、是否存在赋值标记。 肯定有人和我一样好奇为什么要维护历史最大的标记。 因为修改是基于标记的修改，当标记下传时可能不是历史最大值对应的标记。 打个比方，区间 \(+1\) 再 \(-1\) 。加法标记变成了 \(0\) ，但是我们历史最大加法标记应当是 \(1\) ，历史最大值应为 \(1\) 。 接下来就是维护的细节了。 \(\mathtt{push\_up}\) 函数比较简单，就是合并一下最大值和历史最大值。 询问和修改也没啥特别的，主要难在 \(\mathtt{push\_down}\) 函数。 首先搞清楚我们的标记处理顺序：...

洛谷P6154 游走 题解 题目链接：P6154 游走 题意： S 城可以看作一个有 \(n\) 个点 \(m\) 条边的有向无环图。可能存在重边。 cxy 在 S 城随机游走，她会在所有路径中随机选择一条路径，选择所有路径的概率相等。路径的起点和终点可以相同。 定义一条路径的长度为经过的边数，你需要求出 cxy 走的路径长度的期望，答案对 \(998244353\) 取模。 输入格式： 第一行两个整数 \(n,m\)。 接下来 \(m\) 行，每行两个整数 \(x,y\)，表示存在一条从 \(x\) 到 \(y\) 的有向边。 输出格式： 一行一个整数，表示答案对 \(998244353\) 取模后的值。 数据范围： \(1\le n \le 10^5,~0 \le m \le 7\times 10^5\) 。 期望dp + topo 小清新题~ 设 \(f_u\) 表示以 \(u\) 为终点的路径总长度，\(g_u\) 表示以 \(u\) 为终点的路径总条数。 考虑以拓扑序转移。对于边 \((u,v)\) ，有转移（其中 \(a \uparrow b + c\) 表示 a...

洛谷P1137 旅行计划 题解 题目链接：P1137 旅行计划 题意： 小明要去一个国家旅游。这个国家有 \(N\) 个城市，编号为 \(1\) 至 \(N\) ，并且有 \(M\) 条道路连接着，小明准备从其中一个城市出发，并只往东走到城市 \(i\) 停止。 所以他就需要选择最先到达的城市，并制定一条路线以城市 \(i\) 为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。 现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的 \(i\) ，都需要你为小明制定一条路线，并求出以城市\(i\)为终点最多能够游览多少个城市。 输入格式： 第\(1\)行为两个正整数 \(N, M\) 。 接下来 \(M\) 行，每行两个正整数 \(x, y\) ，表示了有一条连接城市 \(x\) 与城市 \(y\) 的道路，保证了城市 \(x\) 在城市 \(y\) 西面。 输出格式： 共 \(N\) 行，第 \(i\) 行包含一个正整数，表示以第 \(i\) 个城市为终点最多能游览多少个城...