洛谷P2617 Dynamic Rankings 题解
洛谷P2617 Dynamic Rankings 题解 题目链接:P2617 Dynamic Rankings 题意: 给定一个含有 \(n\) 个数的序列 \(a_1,a_2 \dots a_n\),需要支持两种操作: Q l r k 表示查询下标在区间 \([l,r]\) 中的第 \(k\) 小的数。 C x y 表示将 \(a_x\) 改为 \(y\) 。 输入格式: 第一行两个正整数 \(n,m\),表示序列长度与操作个数。 第二行 \(n\) 个整数,表示 \(a_1,a_2 \dots a_n\)。 接下来 \(m\) 行,每行表示一个操作,都为上述两种中的一个。 输出格式: 对于每一次询问,输出一行一个整数表示答案。 数据范围: \(1\le n,m \le 10^5\),\(1 \le l \le r \le n\),\(1 \le k \le r-l+1\),\(1\le x \le n\),\(0 \le a_i,y \le 10^9\)。 请注意常数优化,但写法正常的整体二分和树套树都可以以大约 \(1000\text{ms}\) 每个点的时间通过。 ...
洛谷P2487 [SDOI2011] 拦截导弹 题解
洛谷P2487 [SDOI2011] 拦截导弹 题解 题目链接:P2487 [SDOI2011] 拦截导弹 题意: 注意本题不是 P1020 [NOIP1999 提高组] 导弹拦截 ,本题有额外的速度限制(更科学了)。 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹,但是以后每一发炮弹都不能高于前一发的高度,其拦截的导弹的飞行速度也不能大于前一发。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。 在不能拦截所有的导弹的情况下,我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个,如果有多个最优方案,那么我们会随机选取一个作为最终的拦截导弹行动蓝图。 我方间谍已经获取了所有敌军导弹的高度和速度,你的任务是计算出在执行上述决策时,每枚导弹被拦截掉的概率。 输入格式: 第一行包含一个正整数 \(n\),表示敌军导弹数量。 下面 \(n\) 行按顺序给出了敌军所有导弹信息。 第 \...
洛谷P1117 [NOI2016] 优秀的拆分 题解
洛谷P1117 [NOI2016] 优秀的拆分 题解 题目链接:P1117 [NOI2016] 优秀的拆分 题意: 如果一个字符串可以被拆分为 \(\text{AABB}\) 的形式,其中 \(\text{A}\) 和 \(\text{B}\) 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。 例如,对于字符串 \(\texttt{aabaabaa}\) ,如果令 \(\text{A}=\texttt{aab}\),\(\text{B}=\texttt{a}\),我们就找到了这个字符串拆分成 \(\text{AABB}\) 的一种方式。 一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。 比如我们令 \(\text{A}=\texttt{a}\),\(\text{B}=\texttt{baa}\),也可以用 \(\text{AABB}\) 表示出上述字符串;但是,字符串 \(\texttt{abaabaa}\) 就没有优秀的拆分。 现在给出一个长度为 \(n\) 的字符串 \(S\),我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字...
洛谷P4016 负载平衡问题 题解
洛谷P4016 负载平衡问题 题解 题目链接:P4016 负载平衡问题 题意: \(G\) 公司有 \(n\) 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 \(n\) 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。 输入格式: 第一行一个正整数 \(n\),表示有 \(n\) 个仓库。 第二行 \(n\) 个正整数,表示 \(n\) 个仓库的库存量。 输出格式: 输出最少搬运量。 数据范围: \(1 \leq n \leq 100\)。 贪心题写什么网络流。原题:P2512 糖果传递 或者 P2125 图书馆书架上的书。 网上证明很多不写了,可以去看 mygr 巨佬写的文章 贴个 P2125 的代码:(这题要输出传递方案) #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &x, int y) { x < y ? x = y ...
洛谷P2336 [SCOI2012] 喵星球上的点名 题解
洛谷P2336 [SCOI2012] 喵星球上的点名 题解 题目链接:P2336 [SCOI2012] 喵星球上的点名 题意: qry 幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。 假设课堂上有 \(n\) 个喵星人,每个喵星人的名字由姓和名构成。喵星球上的老师会选择 \(m\) 个串来点名,每次读出一个串的时候,如果这个串是一个喵星人的姓或名的子串,那么这个喵星人就必须答到。 然而,由于喵星人的字码如此古怪,以至于不能用 ASCII 码来表示。为了方便描述,qry 决定用数串来表示喵星人的名字。 现在你能帮助 qry 统计每次点名的时候有多少喵星人答到,以及 \(m\) 次点名结束后每个喵星人答到多少次吗? 输入格式: 首先定义喵星球上的字符串给定方法: 先给出一个正整数 \(l\),表示字符串的长度,接下来 \(l\) 个整数,第 \(i\) 个整数 \(a_i\) 表示字符串的第 \(i\) 个字符。 输入的第一行有两个整数,分别表示喵星人的个数 \(n\) 个点名次数 \(m\)。 接下来 \(n\) 行,每行两个喵星球上的字符串,按照定...
洛谷P9973 [THUPC 2024 初赛] 你说得对,但是 AIGC 题解
洛谷P9973 [THUPC 2024 初赛] 你说得对,但是 AIGC 题解 你说得对,但是题目链接:P9973 [THUPC 2024 初赛] 你说得对,但是 AIGC 你说得对,但是题目背景 你说得对,但是本题不接受提供 hack 数据。 你说得对,但是题目描述 你说得对,但是众所周知 AIGC 是当下计算机领域最热门的方向之一,算协的几名成员也对此很有兴趣,经过长时间的奋战,终于研发出了一款全新的语言大模型——ChatSAA。 你说得对,但是当模型即将发布之时,开发团队忽然发现模型存在重大问题——由于开发团队的某名成员沉迷于一款中文二字英文七字的游戏(见样例),导致训练模型时使用的语料库被莫名其妙地污染了,这使得模型生成的句子全都带有一个相同的前缀。 你说得对,但是紧急更换语料库重新训练显然已经来不及了,无奈开发团队只能在文档中注明:本模型的最大特性(而非 bug)在于生成文本的前 19 个字符,这既是模型独特的防伪标记,也充分彰显了算协团队的人文情怀和文化素养。 你说得对,但是一个微不足道的问题在于:这会让人们一眼就能分辨出哪些句子是由 AI 生成的,这会对那些打算用 ...
洛谷P3239 [HNOI2015] 亚瑟王 题解
洛谷P3239 [HNOI2015] 亚瑟王 题解 题目链接:P3239 [HNOI2015] 亚瑟王 题意: 小 K 不慎被 LL 邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定,在脱坑之前,最后再来打一盘亚瑟王。既然是最后一战,就一定要打得漂亮。众所周知,亚瑟王是一个看脸的游戏,技能的发动都是看概率的。 作为一个非洲人,同时作为一个前 OIer,小 K 自然是希望最大化造成伤害的期望值。但他已经多年没写过代码,连 Spaly都敲不对了,因此,希望你能帮帮小 K,让他感受一下当欧洲人是怎样的体验。 本题中我们将考虑游戏的一个简化版模型。 玩家有一套卡牌,共 \(n\) 张。游戏时,玩家将 \(n\) 张卡牌排列成某种顺序,排列后将卡牌按从前往后依次编号为 \(1 - n\)。本题中,顺序已经确定,即为输入的顺序。每张卡牌都有一个技能。第 \(i\) 张卡牌的技能发动概率为 \(p_i\),如果成功发动,则会对敌方造成 \(d_i\) 点伤害。也只有通过发动技能,卡牌才能对敌方造成伤害。基于现实因素以及小 K 非洲血统的考虑,\(p_i\) 不会为 \(0\),也...
CF325D Reclamation 题解
CF325D Reclamation 题解 题目链接:Reclamation 题意: 给定一个大小为 \(r \times c\) 的二维环形网格图,每一行的第 \(1\) 格和第 \(c\) 格相邻。 现在按照给定的顺序将 \(n\) 个格子变成障碍物。 一个格子可以变成障碍的条件为该格子变成障碍后仍然存在一条从第 \(1\) 行到第 \(r\) 行的路径。 如果一个格子不可以变成障碍,就跳过该操作并且继续处理接下来的格子。路径为四相邻规则。 你需要求出最多可以有多少个格子变成障碍物。 输入格式: 第一行有三个整数 \(r,c,n(1 \le r,c \le 3000, 1 \le n \le 3 \times 10^5)\)。 接下来 \(n\) 行,每行两个正整数 \(r_i , c_i\),表示将位于 $r_i $ 行,\(c_i\) 列的格子变成障碍物。 输出格式: 输出一个整数表示答案。 如果删掉一格后环不再构成四连通,那么这个点和其他已删除的点将圆柱的侧面截断。 换句话说,此时这个环(或者说曲面)上存在一个由已删除点构成的八连通块。 维护环的连通性十分麻烦。考...
洛谷P2463 [SDOI2008] Sandy 的卡片 题解
洛谷P2463 [SDOI2008] Sandy 的卡片 题解 题目链接:P2463 [SDOI2008] Sandy 的卡片 题意: Sandy 和 Sue 都热衷于收集干脆面中的卡片。 然而,Sue 收集卡片是因为卡片上漂亮的人物形象,而 Sandy 则是为了积攒卡片兑换超炫的人物模型。 每一张卡片都由一些数字进行标记,第 \(i\) 张卡片的序列长度为 \(M_i\),要想兑换人物模型,首先必须要集够 \(N\) 张卡片,对于这 \(N\) 张卡片,如果他们都有一个相同的子串长度为 \(k\),则可以兑换一个等级为 \(k\) 的人物模型。相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。 Sandy 的卡片数远远小于要求的 \(N\),于是 Sue 决定在 Sandy 的生日将自己的卡片送给 Sandy,在 Sue 的帮助下,Sandy 终于集够了 \(N\) 张卡片,但是,Sandy 并不清楚他可以兑换到哪个等级的人物模型,现在,请你帮助 Sandy 和 Sue,看看他们最高能够得到哪个等级的人物模型。 输入格式: 第一行为一个数 \(N\)...
AT_joisc2019_a 試験 (Examination) 题解
AT_joisc2019_a 試験 (Examination) 题解 题目链接:試験 (Examination) 题意: 有 \(n\) 个二元组 \((a,b)\) 和 \(q\) 个询问 \((x,y,z)\) 。 每个询问求满足 \(a\ge x,~b\ge y,~a+b\ge z\) 的二元组个数。 数据范围: \(1\le n,q\le 10^5,~0 \le a,b,x,y\le 10^9,~0 \le z\le 2\times 10^9\)。 令 \(c = a + b\) ,那么问题就变成了,对于询问 \((x,y,z)\) ,求满足 \[ a \ge x,~b \ge y,~c \ge z \] 的三元组 \((a,b,c)\) 的个数。 不过这道题 \(c,z\) 都非常大,需要离散化一下。 时间复杂度 \(\mathcal{O}(n\log^2 n)\) 代码: #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f...
洛谷P3157 [CQOI2011] 动态逆序对 题解
洛谷P3157 [CQOI2011] 动态逆序对 题解 题目链接:P3157 [CQOI2011] 动态逆序对 题意: 对于序列 \(a\),它的逆序对数定义为集合 \[ \{(i,j)\mid i < j \,\land\, a_i > a_j\} \] 的元素个数。 现在给出 \(1\sim n\) 的一个排列,按照某种顺序依次删除 \(m\) 个元素。 你的任务是在每次删除一个元素之前统计整个序列的逆序对数。 输入格式: 第一行包含两个整数 \(n\) 和 \(m\),即初始元素的个数和删除的元素个数。 以下 \(n\) 行,每行包含一个 \(1 \sim n\) 之间的正整数,即初始排列。 接下来 \(m\) 行,每行一个正整数,依次为每次删除的元素。 输出格式: 输出包含 \(m\) 行,依次为删除每个元素之前,逆序对的个数。 数据范围: \(1\le n \le 10^5,~1\le m \le 50000\)。 考虑 CDQ 分治。 方便起见,我们把初始的数看作 \(n\) 个添加操作,修改为 \(f_i=1\) (删除则为 \(-1\) )...
CF618G Combining Slimes 题解
CF618G Combining Slimes 题解 题目链接:Combining Slimes 题意: 有一个 \(1 \times n\) 的网格,你将对这个网格进行 \(n\) 次操作。 每次从右端插入一个数 \(1\) 或 \(2\) 。当有两个相邻的数字 \(x\) 时,他们会合并为一个数字 \(x+1\) 。 插入 \(1\) 的概率为 \(p\) ,插入 \(2\) 的概率为 \(1-p\) 。(原题给的是整数 \(p_0=p\times 10^{9}\) ) 求无法合并时,\(n\) 个格子中所有数的和的期望。浮点输出,要求误差小于 \(10^{-4}\) 。 输入:一行,\(n,p_0\) 。输出:一行,答案。数据范围:\(1\le n,p_0 \le 10^9\) 。 由于每个数都可能出现,根据期望的线性性,所以我们可以分别计算每个数的贡献。 设 \(a_{i,j}\) 为用 \(i\) 个格子且最左边的那一格为 \(j\) 的概率,则 \[ a_{i,j} = a_{i,j-1}\cdot a_{i-1,j-1} \] 根据经验,\(a_{i,j}\) ...

![洛谷P2487 [SDOI2011] 拦截导弹 题解](/qwq/img/p187.webp)
![洛谷P1117 [NOI2016] 优秀的拆分 题解](/qwq/img/p162.webp)

![洛谷P2336 [SCOI2012] 喵星球上的点名 题解](/qwq/img/p197.webp)
![洛谷P9973 [THUPC 2024 初赛] 你说得对,但是 AIGC 题解](/qwq/img/p68.webp)
![洛谷P3239 [HNOI2015] 亚瑟王 题解](/qwq/img/p200.webp)

![洛谷P2463 [SDOI2008] Sandy 的卡片 题解](/qwq/img/p98.webp)

![洛谷P3157 [CQOI2011] 动态逆序对 题解](/qwq/img/p142.webp)

![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p214.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)