题解 洛谷 P1257/P1429/P7883 平面最近点对
2023-08-18 880 字 3 分钟

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

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

题解 洛谷 P1168 中位数

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

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

U334987 营救千泷の小翼龙 简要题意 给你一个数 和 ，求 。 策略分析 本题是一道纯纯诈骗题，我们打表或者运用数学归纳法都可以得到如下结论： 于是我们就可以直接带进去 算了，于是我们做完了，写代码时请注意取模。 参考代码 123456789101112131415161718192021222324#include <iostream>#include <cstdio>#define LL long longusing namespace std;namespace SHAWN { const int mod = 998244353;
题解 UVA11149 Power of Matrix
2023-08-18 1.1k 字 5 分钟

题解 UVA11149 Power of Matrix

题解 UVA11149 Power of Matrix 简要题意： 给定一个 的矩阵 和一个数 ，求 $_{i = 1}{k}Ai $。 法一：暴力求解，单次时间复杂度 法二：分治，单次时间复杂度 我们可以按照分治的定义照猫画虎，将原式变成这样： 然后递归处理即可，分治部分的代码大概长这样： 12345678mat solve(mat bas, LL pos) { \\bas是原矩阵，pos代表当前k的大小 if (pos == 1) { return bas; } mat s; clear(s); for (int i = 0; i < n
题解 洛谷 P1438 无聊的数列
2023-08-18 1k 字 4 分钟

题解 洛谷 P1438 无聊的数列

P1438 无聊的数列 简要题意 给定一个序列 ，要求进行两种操作。 对于区间 对应加上一个长为 ，首项为 ，公差为 的等差数列； 查询第 个数的值。 策略分析 题目要求将一段等差数列加到一段区间上去。我们一眼丁真想到了线段树，但是对于加的不是同一个值的情况，朴素的做法只能进行单点修改，如果这样单点改下去再单点查，和直接在数组上模拟没有任何区别，我们写线段树不光要多递归几层还很废空间。 遇到这种一眼就是线段树却不知道如何维护的题，我们就需要重新再回去审题来寻找操作的特殊性质。我们发现这道题的特殊性质就是等差数列。那么等差数列有什么性质呢？等差数列等差。虽然说这是一
题解 BNDS OJ 1263 表达式求值
2023-08-18 526 字 2 分钟

题解 BNDS OJ 1263 表达式求值

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

题解 CF1413C Perform Easily

题解 CF1413C Perform Easily 简要题意 给定一个含有 个元素的可重集 ，一个数 和一个含有 个数的可重集 ，现在要求 中每个数和 中任意一个数作差使得作差后得到的新的集合 中最大的数和最小的数的差最小。 策略分析 首先考虑暴力，每个数最后的值都有 种可能，所以总可能数有 种，显然不行。题目中 的大小为 ，所以我们期待一个 的做法。我们发现，所有数也只有 种可能，想要枚举答案不可能，但我们可以枚举结果。于是我们想到把 中每个元素都和 中所有元素作差，最后得到 个数放入一个新的数组 。因为我们要考虑最大和最小的差最小，所以我们需要使
题解 洛谷 P9570 「NnOI R2-T2」Glaciaxion
2023-08-21 592 字 2 分钟

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

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

题解 洛谷 P5058 [ZJOI2004] 嗅探器

P5058 [ZJOI2004] 嗅探器 简要题意 给定一张图，再给处图中两个点 ，现在要在图中删去除了 以外的一个点使得 和 不再连通，求要删除的点的编号 题目分析 前置芝士 题目要求我们删掉一个点使得给定的两个点不连通，那么其实我们就是要找一个满足要求的割点，如下图标黑的点就是题目给定的两个点： 点 是一个割点，我们删除点 即可使得 两点不连通，但是并非任意割点都满足要求，比方说下面这张图： 点 和点 都是图中的割点，但是删去 并不能使得目标点 不连通，所以只有点 是符合条件的点，那么我们就要去筛选割点中符合要求的点。 怎么筛呢？其实我们
题解 洛谷 P7687 [CEOI2005] Critical Network Lines
2023-08-24 726 字 3 分钟

题解 洛谷 P7687 [CEOI2005] Critical Network Lines

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