Q779’s Blog

洛谷P9087 「SvR-2」音符 题解 题目链接：P9087 「SvR-2」音符 题意： 我们用一个字符串代替一份乐谱，用字符代替每一个音符。 我们定义「重音」表示乐谱中出现了两个连续的相同字符，如 \(\tt eeeee\) 中存在 \(4\) 个「重音」。 现在 Sept 准备写一份长度为 \(n\) 的乐谱给 Tpes 看，他对乐谱的评价标准如下： 乐谱中每出现一个「重音」，他的愤怒值就会增加 \(a\)。 乐谱中每有一段长度为 \(k\) 的子串中不存在「重音」，他的愤怒值就会增加 \(b\)。 现在已知 \(n,k,a,b\)，请你帮 Sept 构造出一份乐谱，使得 Tpes 的愤怒值 \(x\) 最小。 输入格式: 本题有多组数据。 第一行一个整数 \(T\)，表示数据组数。 接下来 \(T\) 行，每行两个整数 \(n,k,a,b\)，意义如题目所述。 输出格式 共 \(2 \cdot T\) 行，对于每组数据都输出两行： 第 1 行表示 Tpes 最小的愤怒值 \(x\)。 第 2 行表示你构造出的乐谱。 数据范围： \(2\le T\le 100\)...

洛谷P1884 [USACO12FEB] Overplanting S 题解 题目链接：P1884 [USACO12FEB] Overplanting S 题意： 扫描线板子，求矩形面积并： 给定 \(n(n \le 10^5)\) 个矩形的左上角位置与右下角位置，求覆盖面积。 重叠部分只算一次，坐标范围 \(-10^8 \le x_1,y_1,x_2,y_2 \le 10^8\) ， 这里介绍一种不用线段树的扫描线。 先把每个矩形还是拆成 \(4\) 个点，并按每一维 \(0/1\) 的分类方式确定每个点距离坐标轴左下角的位置 换句话说，我们将左上角的点当作 out ，左下角的点当作 in ，方便从下到上依次考虑每个点 考虑对点按 \(x\) 顺序排序，对于相等的 \(x\) ，我们把他们放到一个 multiset 里分类讨论 \(y\) 的不同情况 因为用 multiset 排过序了，所以我们从下往上讨论每个 \(y\) ，以类似于区间覆盖的方式计算它的总长度 \(L\) 这样它的贡献可以看作 \(L\times (x_i - x_{\mathrm{last}})\) ，...

note[14] 话说我好像对于 OI 和 笔记 这两个分类有点模糊啊。 题：估计 \(\displaystyle\sum_{i=1}^n \frac{i}{\ln i}\) 的大小（时间复杂度估计） 解： \[ \begin{aligned} \sum_{i=1}^n \frac{i}{\ln i} & =O\left(\int_1^n \frac{x}{\ln x} \mathrm{~d} x\right) \\[6pt] & =O\left(\int_0^{\ln n} \frac{\mathrm{e}^{2 t}}{t} \mathrm{~d} t\right) && t=\ln x \\[6pt]& =O\left(\int_0^{2 \ln n} \frac{\mathrm{e}^{2 t}}{2 t} \mathrm{~d}(2 t)\right) \\[8pt]& =O(\operatorname{Ei}(2 \ln n)) && \operatorname{Ei}(x) \sim \mathrm{e...

[ABC254D] Together Square 题解 题目链接：[ABC254D] Together Square 题意： 给定 \(n\)，求满足以下条件的二元组 \((i, j)\) 数量：\(1 \le i, j \le n, i \times j = k^2(k \in \mathbb{N}^*)\)。 \(1 \le n \le 2 \times 10^5\) 先来讲讲常规做法： 记 \(f_i\) 为 \(i\) 最大的完全平方数因子，然后我们可以得到这样一个式子 \[ i \times j=f_i \times \frac{i}{f_i} \times f_j \times \frac{j}{f_j} \] 整理一下可得 \[ \frac{i}{f_i}=\frac{j}{f_j} \] 统计一下 \(\frac{i}{f_i}\) 即可。 时间复杂度 \(\mathcal{O}(n \sqrt{n})\) 或者用筛法可以到 \(\mathcal{O}(n \log n)\) 代码： #include <bits/stdc++.h> using nam...

洛谷P9150 邮箱题 题解 题目链接：P9150 邮箱题 题意： 有一张 \(n\) 个点和 \(m\) 条边构成的有向图。每个点内都有一把另一个点的钥匙，\(i\) 号点内有 \(k_i\) 号点的钥匙。你能进入一个点当且仅当你有该点的钥匙。保证 \(k_i\) 构成排列。 只要进入了一个点，就获得了这个点内有的钥匙。一旦获得钥匙就不会被消耗。 现在你拿到了 \(i\) 号点的钥匙并到了 \(i\) 号点。你需要对每个 \(i\) 求出： 有多少点能被你到达。 有多少点能被你到达并返回起点 \(i\)。 请注意：给出的边均是有向边！ 输入格式： 本题有多组数据。 第一行，一个正整数 \(T\)，表示数据的组数。对于每组数据： 第一行，两个整数 \(n,m\)，表示图的点数和边数。 第二行，\(n\) 个整数 \(k_1, k_2, \ldots, k_n\)，表示 \(i\) 号点内有 \(k_i\) 号点的钥匙。保证 \(k_i\) 构成排列。 接下来 \(m\) 行，每行两个整数 \(x, y\)，表示图上的一条从 \(x\) 指向 \(y\) 的有向边。保证不含重...

洛谷P9228 原神 题解 题目链接：P9228 原神 题意： 原神中有一个魔法师，她可以打出 $ n $ 次火元素攻击魔法和 $ m $ 次冰元素攻击魔法，每次攻击的伤害分别为 $ a_1,a_2,, a_n $ 和 $ b_1,b_2,, b_m $。 元素攻击之间存在如下反应规则： 每次元素攻击可以给没有元素附着的怪物附着相应的元素，初始时怪物没有元素附着； 如果用火元素攻击打到冰元素附着的怪物身上，那么本次伤害将 $ $，并清空元素附着； 如果用冰元素攻击打到火元素附着的怪物身上，那么本次伤害将 $ +k $，并清空元素附着。 现在魔法师可以任意安排攻击顺序，也就是说，每次攻击过后，魔法师可以从自己没有使用过的魔法中任意挑选一种使用。她希望最大化总伤害，请问最大总伤害是多少。 输入格式： 第一行三个整数 $ n,m,k $。 第二行 $ n $ 个整数 $ a_1,a_2,, a_n $。 第三行 $ m $ 个整数 $ b_1,b_2,, b_m $。 输出格式： 一行一个整数，表示答案。 数据范围： \(1 \leq n,m \leq 10^6\)，\(0 \l...

CF1527D MEX Tree 题解 题目链接：CF1527D MEX Tree 题意： 本题有多组测试数据。 给出一棵 \(n\) 个点的树，点从 \(0\) 到 \(n - 1\) 编号。定义一条路径的权值是路径上所有点编号的 \(\operatorname{mex}\)。对于每个 \(0\le i\le n\) 求出 \(\operatorname{mex}\) 为 \(i\) 的路径有几条。注意，这里统计的路径需要包括至少一条边。 一个集合的 \(\operatorname{mex}\) 定义为最小的不在集合中的非负整数。 数据范围： \(2 \le n \le 2\times 10^5, \sum n_i \le 2\times 10^5\) 。 先考虑在链上怎么做。我们从 \(0\) 开始往上推，设当前枚举到了 \(x\) 。 可以发现 \(0\) 到 \(x\) 的数一定会在一个区间 \([l,r]\) 内，根据乘法原理可知 \(\mathrm{mex} > x\) 的路径数有 \(l\times (n - r + 1)\) 条。 接着考虑在树上怎么做。...

小蓝书 17.1 题解 传送门：小蓝书 17.1 第一部分 例题 例1 某聚会有 \(605\) 个人参加，已知每个人至少和其余的一个人握过手 求证：必有一个人至少和其中两个人握过手。 解： 本题最特别的就是这个 \(605\) 了，我们注意到它是奇数。 考虑反证法，如果每个人都至多和其中一个人握过手，图就变成了这个样子： 设边数为 \(m\) ，则节点数为 \(2m\) ，这是个偶数，与 \(605\) 是奇数矛盾，故原命题成立。 例2 能否让马跳动几次，将下图一所示的阵势变为图二？ 提示：看图三，知道要干嘛了吧。 解： 先把每个格子编号，然后把每个马能跳到的地方都连上，如图所示 显然，两幅图中的马无论怎么跳都不会改变相对顺序，因此不可能。 例3 有 \(n(n \ge 3)\) 个人，他们之间有些人互相认识，有些人互相不认识，且至少有一个人没有与其他人都认识 问：与其他人都认识的人数的最大值是多少？ 解： 注意，这里没有与其他人都认识，不代表这个人一个都不认识。 考虑作无向图 \(G\) ，两点相邻当且仅当他们互相认识。 因为要最大值，所以有且仅有一个人没有...

小蓝书 17.1 小蓝书上这一章只讲了图的定义。 关于图的定义我写过专门的一篇文章图论相关概念，我就摘录一部分内容上来了。 图的定义 图 (graph) 是一个二元组 \(G=(V(G), E(G))\) ，其中： \(V(G)\) 是非空集，称为 点集 (vertex set) 。 对于 \(V(G)\) 中的每个元素，我们称其为 顶点 (vertex) 或 节点 (node)，简称 点 。 \(\left| V(G) \right|\) 也被称作图 \(G\) 的 阶 (order)。 \(E(G)\) 为 \(V(G)\) 各节点之间边的集合，称为 边集 (edge set)。 形象地说，图是由若干点以及连接点与点的边构成的。 事实上，我们常用 \(G=(V,E)\) 表示图，其中 \(V\) 表示点集，\(E\) 表示边集。 练习题 传送门：小蓝书 17.1 题解 这章节是有点水，但是例题可不水。

小蓝书 16.1 题解 传送门：小蓝书 16.1 一、加法原理和乘法原理 例1 从 \(1,2,3,\cdots,100\) 中取 \(3\) 个数，使这 \(3\) 个数恰好成等差数列的不同取法有_______种。 解法1： 设取出的 \(3\) 个数构成首项为 \(a\) ，公差为 \(d\) 的等差数列： \[ a,a+d,a+2d \quad (a,d \in \mathbb{Z}_+) \] 则 \(a+2d \le 100\) ，则 \[ 1 \le d \le \left\lfloor{\dfrac{100-a}{2}}\right\rfloor \le \left\lfloor{\dfrac{100-1}{2}}\right\rfloor = 49 \] 整理一下就是 \[ 1\le d \le 49 \\ a\le 100-2d \] 对于每个确定的 \(d\) ，\(a\) 都有 \(100-2d\) 种取法，则答案为 \[ \sum_{d=1}^{49}(100-2d) = 49\times 100 -2 \times \frac{49(49+1)}{2} ...

洛谷P9035 「KDOI-04」Pont des souvenirs 题解 题目链接：P9035 「KDOI-04」Pont des souvenirs 题意： 给定正整数 \(n,k\)，求有多少个长度为 \(n\) 的正整数序列 \(a\) 满足： \(0<a_1\le a_2\le a_3\le\cdots\le a_n\le k\)； \(\forall\ i\not=j\)，\(a_i+a_j\le k+1\)。 答案对 \(10^9+7\) 取模。 输入格式： 本题包含多组测试数据。 输入的第一行包含一个正整数 \(T\)，表示测试数据组数。 对于每组测试数据，输入包含一行两个正整数 \(n,k\)。 输出格式： 对于每组测试数据，输出一行一个整数表示答案。 数据范围： 对于 \(100\%\) 的数据，保证 \(1\le T\le2\times10^5\)，\(1\le n,k\le10^7\) 设 \(a_0 = 1\) ，并记 \(b_i = a_i - a_{i - 1}\) 。考虑枚举 \(a_n\) 的值，分为两种情况讨论： \(a_n ...

洛谷P8969 幻梦 | Dream with Dynamic 题解 题目链接：P8969 幻梦 | Dream with Dynamic 题意： 有一个长度为 \(n\) 的序列，开始时第 \(i\) 位为 \(a_i\)。你需要完成 \(q\) 次操作： A l r x，对于所有的 \(l\le i\le r\)，令 \(a_i\gets a_i+x\)。 P l r，对于所有的 \(l\le i\le r\)，令 \(a_i\gets\operatorname{popcount}(a_i)\)。 J p，查询 \(a_p\) 的值。 其中 \(\operatorname{popcount}(x)\) 为 \(x\) 的二进制表示中 \(1\) 的个数。 注意：本题时空限制为 10s 1.00GB。 输入格式： 第一行两个正整数 \(n,q\)。 第二行 \(n\) 个正整数 \(a_1, a_2, \ldots, a_n\)。 接下来 \(q\) 行，每行描述一个操作，形如以下三种中的一种： A l r x P l r J p 输出格式： 对于每个 J 操作，输出...