Q779’s Blog

洛谷P2336 [SCOI2012] 喵星球上的点名 题解 题目链接：P2336 [SCOI2012] 喵星球上的点名 题意： cxy 幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。 假设课堂上有 \(n\) 个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择 \(m\) 个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。 然而，由于喵星人的字码如此古怪，以至于不能用 ASCII 码来表示。为了方便描述，cxy 决定用数串来表示喵星人的名字。 现在你能帮助 cxy 统计每次点名的时候有多少喵星人答到，以及 \(m\) 次点名结束后每个喵星人答到多少次吗？ 输入格式： 首先定义喵星球上的字符串给定方法： 先给出一个正整数 \(l\)，表示字符串的长度，接下来 \(l\) 个整数，第 \(i\) 个整数 \(a_i\) 表示字符串的第 \(i\) 个字符。 输入的第一行有两个整数，分别表示喵星人的个数 \(n\) 个点名次数 \(m\)。 接下来 \(n\) 行，每行两个喵星球上的字符串，按照定...

洛谷P9973 [THUPC 2024 初赛] 你说得对，但是 AIGC 题解 你说得对，但是题目链接：P9973 [THUPC 2024 初赛] 你说得对，但是 AIGC 你说得对，但是题目背景 你说得对，但是本题不接受提供 hack 数据。 你说得对，但是题目描述 你说得对，但是众所周知 AIGC 是当下计算机领域最热门的方向之一，算协的几名成员也对此很有兴趣，经过长时间的奋战，终于研发出了一款全新的语言大模型——ChatSAA。 你说得对，但是当模型即将发布之时，开发团队忽然发现模型存在重大问题——由于开发团队的某名成员沉迷于一款中文二字英文七字的游戏（见样例），导致训练模型时使用的语料库被莫名其妙地污染了，这使得模型生成的句子全都带有一个相同的前缀。 你说得对，但是紧急更换语料库重新训练显然已经来不及了，无奈开发团队只能在文档中注明：本模型的最大特性（而非 bug）在于生成文本的前 19 个字符，这既是模型独特的防伪标记，也充分彰显了算协团队的人文情怀和文化素养。 你说得对，但是一个微不足道的问题在于：这会让人们一眼就能分辨出哪些句子是由 AI 生成的，这会对那些打算用 ...

洛谷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 题解 题目链接：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 的卡片 题意： 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) 题解 题目链接：試験 (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] 动态逆序对 题意： 对于序列 \(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 题解 题目链接：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}\) ...

AT_icpc2014spring_e Parentheses 题解 题目链接：Parentheses 题意： 给定 \(n\) 个字符串 \(s_1,s_2,\cdots s_n\)，每个字符串由括号 ( 和 ) 组成。 请问是否可以排列这 \(n\) 个字符串，使得这些字符串拼接后是一个合法的字符串。 合法的字符串定义如下： 空字符串是合法的。 如果 \(A\) 和 \(B\) 是合法的，那么 \(A\) 和 \(B\) 拼接后也是合法的。 如果 \(A\) 是合法的，那么将 \(A\) 放在一对匹配的括号内得到的字符串也是合法的。 任何其他字符串都是不合法的。 例如，()() 和 (()) 是合法的，而 ()) 和 ((() 是不合法的。 输入格式： 输入的第一行包含一个整数 \(n~(1 \leq n \leq 100)\)，表示字符串的数量。 接下来 \(n\) 行，每行包含一个字符串 \(s_i~(1 \leq | s_i | \leq 100)\)。\(s_i\) 中的所有字符都是 ( 或 )。 输出格式： 如果可以组成一个合法的字符串，则输出一行 Yes，否...

洛谷P5361 [SDOI2019] 热闹的聚会与尴尬的聚会 题解 题目链接：P5361 [SDOI2019] 热闹的聚会与尴尬的聚会 题意： 小 Q 的生日快到了，他决定周末邀请一些朋友到他的新房子一起聚会！ 他的联系薄上有 \(n\) 位好友，他们两两之间或者互相认识，或者互相不认识。小 Q 希望在周六办一个热闹的聚会，再在周日办一个尴尬的聚会。 一场热闹度为 \(p\) 的聚会请来了任意多位好友，对于每一位到场的好友来说都有至少 \(p\) 位他认识的好友也参加了聚会，且至少对于一位到场的好友来说现场恰好有 \(p\) 位他认识的好友； 一场尴尬度为 \(q\) 的聚会请来了恰好 \(q\) 位好友，且他们两两互不认识。 两场聚会可能有重复的参与者，联系薄上也有可能有某些好友同时缺席了两场聚会。 小 Q 喜欢周六聚会的热闹度 \(p\) 与周日聚会的尴尬度 \(q\) 之间满足：\(\left\lfloor \frac{n}{p+1} \right\rfloor \le q\) 且 \(\left\lfloor \frac{n}{q+1} \right\rfloor ...

CF1379F2 Chess Strikes Back (hard version) 题解 题目链接：Chess Strikes Back (hard version) 题意： 请注意，简单版本和困难版本之间的区别在于，困难版本中不可用的格子可以再次变为可用，而简单版本中则不可以。只有在所有版本都解决后，才能进行破解。 伊尔达和伊万对国际象棋感到厌倦，但他们非常喜欢棋盘，于是他们发明了一种新游戏。棋盘是一个 \(2n \times 2m\) 的棋盘：它有 \(2n\) 行，\(2m\) 列，如果第 \(i\) 行和第 \(j\) 列的格子满足 \(i+j\) 是偶数，那么该格子是白色，否则是黑色。 游戏进行如下：伊尔达将棋盘上的某些白色格子标记为不可用，并要求伊万在剩余的白色格子上放置 \(n \times m\) 个国王，使得没有国王相互攻击。一个国王可以攻击另一个国王，如果它们位于共享一个边或一个角的相邻格子上。 伊尔达想探索不同的格子组合。最初所有格子都标记为可用，然后他有 \(q\) 个查询。在每个查询中，他要么将一个格子标记为不可用，要么将之前不可用的格子标记为可用。...

洛谷P2312 [NOIP2014 提高组] 解方程 题解 题目链接：P2312 [NOIP2014 提高组] 解方程 题意： 已知多项式方程： \[ a_0+a_1x+a_2x^2+\cdots+a_nx^n=0 \] 求这个方程在 \([1,m]\) 内的整数解（\(n\) 和 \(m\) 均为正整数）。 输入格式： 输入共 \(n + 2\) 行。 第一行包含 \(2\) 个整数 \(n, m\) ，每两个整数之间用一个空格隔开。 接下来的 \(n+1\) 行每行包含一个整数，依次为 \(a_0,a_1,a_2\ldots a_n\) 。 输出格式： 第一行输出方程在 \([1,m]\) 内的整数解的个数。 接下来每行一个整数，按照从小到大的顺序依次输出方程在 \([1,m]\) 内的一个整数解。 数据范围： \(0<n\le 100,|a_i|\le 10^{10000},a_0\ne 0,m<10^6\) 。 这个题有点哈希的味道。注意到对于质数 \(p\) ， \[ a_0+a_1x+a_2x^2+\cdots+a_nx^n\equiv 0 \pmod...