题解 洛谷 P7687 [CEOI2005] Critical Network Lines
2023-08-24 789 字 4 分钟

题解 洛谷 P7687 [CEOI2005] Critical Network Lines

P7687 [CEOI2005] Critical Network Lines简要题意给你一张图，图上有两类点 $A$ 和 $B$，现在要求你找到满足下面条件的边：删除这条边后该图变为两个块，且至少有一个块中只包含 $A$ 类点或只包含 $B$ 类点。 策略分析前置芝士：割边（桥） 我们不难看出题目想让我们求的边是图中的割边，但并非所有的割边都满足题目的条件。如下图（图中边上的数字是编号不是边权）： 这幅图中的割边有 $1,4,5,6,8$ 五条，而符合题目条件的只有 $1,6,8$ 这三条。仔细考虑我们在深搜的时候形成的深度优先生成树的性质，我们发现，当一个割边满足条件当且仅当它连接的一
题解 洛谷 P5058 [ZJOI2004] 嗅探器
2023-08-24 619 字 3 分钟

题解 洛谷 P5058 [ZJOI2004] 嗅探器

P5058 [ZJOI2004] 嗅探器简要题意给定一张图，再给处图中两个点 $x,y$，现在要在图中删去除了 $x,y$ 以外的一个点使得 $x$ 和 $y$ 不再连通，求要删除的点的编号 题目分析前置芝士 题目要求我们删掉一个点使得给定的两个点不连通，那么其实我们就是要找一个满足要求的割点，如下图标黑的点就是题目给定的两个点： 点 $1$ 是一个割点，我们删除点 $1$ 即可使得 $2,4$ 两点不连通，但是并非任意割点都满足要求，比方说下面这张图： 点 $3$ 和点 $4$ 都是图中的割点，但是删去 $4$ 并不能使得目标点 $1,7$ 不连通，所以只有点 $3$ 是符合条件的点，那
题解 洛谷 P9570 「NnOI R2-T2」Glaciaxion
2023-08-21 645 字 3 分钟

题解 洛谷 P9570 「NnOI R2-T2」Glaciaxion

洛谷 P9570 「NnOI R2-T2」Glaciaxion简要题意给定一个数 $n$ 和 $m$ 表示有从 $1$ ~ $n$ 的正整数和 $m$ 次操作。每次操作给出一个字母 N 或 Y，如果给出 N 说明有一个数字第一次被选中并输出，如果给出 Y 就要从刚刚选出来的数里再选一个输出出来。现在要求若干输出里字典序最小的序列，如果无解输出 No solution。 策略分析无解情况 当给出 N 的次数超过 $n$ 时不合法，因为每个数第一次出现的次数总和至多为 $n$。 当还没有给出 N 就给出 Y 时不合法，因为 Y 不能选出以前没有选出来的数。 $n$ 或 $m$ 等于 $0$ 的时候
题解 CF1413C Perform Easily
2023-08-19 897 字 4 分钟

题解 CF1413C Perform Easily

题解 CF1413C Perform Easily简要题意给定一个含有 $6$ 个元素的可重集 $a$，一个数 $n$ 和一个含有 $n$ 个数的可重集 $b$，现在要求 $b$ 中每个数和 $a$ 中任意一个数作差使得作差后得到的新的集合 $b$ 中最大的数和最小的数的差最小。 策略分析首先考虑暴力，每个数最后的值都有 $6$ 种可能，所以总可能数有 $6^n$ 种，显然不行。题目中 $n$ 的大小为 $10^5$，所以我们期待一个 $O(n\log n)$ 的做法。我们发现，所有数也只有 $6$ 种可能，想要枚举答案不可能，但我们可以枚举结果。于是我们想到把 $b$ 中每个元素都和 $a$
题解 BNDS OJ 1263 表达式求值
2023-08-18 588 字 3 分钟

题解 BNDS OJ 1263 表达式求值

题解 BNDS OJ 1263 表达式求值简要题意：输入一个表达式，包括 +，-，*，/，(，)。求出表达式的值，保留两位小数（不知道你谷有没有这道题）。 提供一组样例： 样例输入： 19-(6+3*5)/3 样例输出： 12.00 策略分析：这不是简单的数据结构入门题，我们只需要拿两个栈，一个存数字一个存运算符，碰到后括号就把它到前括号里的值全部算出来。因为在这6个运算符中，除了括号其他均是二元运算符，所以符号栈栈顶运算符（除了括号）一定匹配数字栈的头两个数字 ，按照运算优先级取出来算就可以了。运算优先级我们可以用一个 $ \operatorname{map} $ 来处理，具体细节见
题解 洛谷 P1168 中位数
2023-08-18 1.2k 字 5 分钟

题解 洛谷 P1168 中位数

题解 洛谷 P1168 中位数由于这道题目比较水，所以机房中诞生了四种做法，分别是权值线段树、堆、二分以及 $\operatorname{multiset}$。 这里主要介绍本题的堆解法 通过读题我们可以轻易发现，每两次插入数据就需要进行一次访问，且期间必须维护当前访问过的所有元素组成的数列具有单调性 。 问题一：如何维护数列的单调性 于是我们很容易想到可以使用优先队列对其插入的数字进行动态排序来维护其单调性。如果你不知道什么是优先队列，那么不妨先通过下面的传送门去看一看优先队列的用法： 点我 于是你现在明白了什么是优先队列，我们只需要在维护好的单调队列里取出中位数就可以了。
题解 洛谷 P1257/P1429/P7883 平面最近点对
2023-08-18 947 字 5 分钟

题解 洛谷 P1257/P1429/P7883 平面最近点对

题解 洛谷 P1257/P1429/P7883 平面最近点对本文主要介绍分治法P1257因为数据范围太小从而可以$n^2$水过，所以只评了个橙，那么直接$n^2$做就可以了 P1429/P7883这两道题的数据范围都在$10^5$，所以我们期望的时间复杂度是$O(nlogn)$，这时候我们就不要充分发扬人类智慧了（，果断使用分治 分治策略考虑将这些点划分成若干区间进行比较，因为点是乱序的，所以我们先对所有点按照$x$坐标从小到大进行排序，排好序以后从中间序号的点来二分整个$xOy$系，递归二分若干次后，我们只需要对三种情况的点进行比较就可以了 1.两个点都在$mi
题解 洛谷 P1438 无聊的数列
2023-08-18 1.1k 字 6 分钟

题解 洛谷 P1438 无聊的数列

P1438 无聊的数列简要题意给定一个序列 $a$，要求进行两种操作。 对于区间 $[l,r]$ 对应加上一个长为 $r - l +1$，首项为 $K$，公差为 $D$ 的等差数列； 查询第 $p$ 个数的值。 策略分析题目要求将一段等差数列加到一段区间上去。我们一眼丁真想到了线段树，但是对于加的不是同一个值的情况，朴素的做法只能进行单点修改，如果这样单点改下去再单点查，和直接在数组上模拟没有任何区别，我们写线段树不光要多递归几层还很废空间。 遇到这种一眼就是线段树却不知道如何维护的题，我们就需要重新再回去审题来寻找操作的特殊性质。我们发现这道题的特殊性质就是等差数列。那么等差数列有什么性
题解 洛谷 U334987 营救千泷の小翼龙
2023-08-18 204 字 2 分钟

题解 洛谷 U334987 营救千泷の小翼龙

U334987 营救千泷の小翼龙简要题意给你一个数 $n$ 和 $v$，求 $v \times \sum_{i=1}^n i^3 \bmod 998244353$。 策略分析本题是一道纯纯诈骗题，我们打表或者运用数学归纳法都可以得到如下结论：$$\sum_{i=1}^n i^3 = (\sum_{i=1}^ni)^2 = (\frac{n + n^2}{2})$$于是我们就可以直接带进去 $O(1)$ 算了，于是我们做完了，写代码时请注意取模。 参考代码123456789101112131415161718192021222324#includ
题解 UVA11149 Power of Matrix
2023-08-18 1.3k 字 7 分钟

题解 UVA11149 Power of Matrix

题解 UVA11149 Power of Matrix简要题意：给定一个 $n \times n$ 的矩阵 $A$ 和一个数 $k$，求 $\sum_{i = 1}^{k}A^i $。 法一：暴力求解，单次时间复杂度 $O(n^3k)$法二：分治，单次时间复杂度 $O(n^3log^2k)$我们可以按照分治的定义照猫画虎，将原式变成这样：$$A+A^2+A^3+A^4+\ldots+A^K = (A+A^2+A^3+\ldots+A^{\frac{k}{2}})+A^{\frac{k}{2}}(A+A^2+A^3+\ldots+A^{\frac{k}{2}})$$ 然后递归