这名用户暂未设置签名。
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
本题使用 **SPFA** 算法进行求解。 在读完题后，根据题目让我们求最多能赚取多少差价，我们可以考虑如下解决方式： 先用 SPFA 算法求出： 从 $1$ 到 $i$ 的所有路径中，水晶球的最低价格 $minv_{i}$。 从 $i$ 到 $n$ 的所有路径中，水晶球的最高价格 $maxv_{i}$。 求解过程中需…
本题考察**模拟**，依题意写模拟寻宝的过程即可。 本题在找寻房间的过程，由于数据范围较大，不能暴力找，可以通过取模的方式优化。 本题还要注意取模后的特判情况，注意数据范围，数组不要混淆或开小。 以下是本题的代码： ``` #include using namespace std; const int N = 1000…
本题我采用的是排序后进行统计的方法。 先将数组从小到大排序。 再正序枚举，对于每个新出现的数，我们从它开始向后扫描，直到一个和它不相等的数为止，扫描过程中统计与当前数相等的数的个数并在扫描结束后输出。 注意在扫描结束后，当前循环变量要跳到合适位置，也就是与当前数字不相等数的下标前一位。 以下是我的代码： ``` #in…
本题在读完题后，依据题目所说的分得最少的分组数目，我们有一种初步想法，那就是让每组的价值尽量大。 由我们的初步想法，设计出这样的贪心策略： 首先将纪念品按照价格从小到大排序。 然后设置两个指针 $i$，$j$，$i$ 指针初始化为1，$j$ 指针初始化为 $n$。 我们接着正序枚举 $i$，每次对于当前纪念品，从 $j…
#### 本题考察结构体排序 读完题后，我们依照题目意思，以学生总分为第一关键字，学生语文成绩为第二关键字，学生学号为第三关键字进行**多关键字排序**即可。 以下是我的代码： ``` #include using namespace std; int n; struct Node { int a,b,c,sum; i…
在本题中，我们要计算可选的住宿方案的总数。 对于这个问题，我们可以考虑左右两个端点。我们每次枚举右端点，然后将所有符合要求的左端点的方案加进答案。 根据题目给的小数据，总装饰色调种类 $k \le 50$。因此我们可以直接开一个数组 $sum$，对于每种装饰颜色且满足要求的旅店进行统计。 统计方式是这样的： 若当前旅店…
### 区间动态规划问题 本题和**环形石子合并**问题类似，只不过**环形石子合并**问题只有一个参数，而本题有头标记和尾标记两种参数。 但解决的思路是相同的，我们只需要改变处理问题的细节。 首先是准备工作：对于**环形问题**，我们要先**破环城链**，也就是把数组重新赋值一份。 定义状态为 $f_{i,j}$ 表…
#### 依题意模拟即可 我们按照题目给出的识别码计算方法，计算出正确的识别码，并判断题目给的 ISBN 号码的识别码，是否与计算出的识别码相同。 若相同，输出 Right。 若不相同，则输出正确的 ISBN 号码。 我们只需要遍历一遍字符串，因此时间复杂度为 $O(n)$。 我们遍历的过程中，只需要从第一个字符遍历到…
#### 本题考察模拟 我的思路是先外层循环 5 次，每次设置一个初始下标变量 $k$，将它的初值赋为 $n-1$，然后倒序循环，每次看最大的字符 $t$ 减去当前字符串的字符 $str_{k}$ 是否大于等于 $n-k$。 若满足以上要求，那么代表从这一位开始能有一个更大的 Jam 数字，我们就终止循环，把当前数字从…
#### 背包问题 本题在读完题目后，会发现这是一道经典的 $01$ 背包问题。 我们回顾下如何求解 $01$ 背包问题： 首先假设每件物品的体积为 $v_{i}$，价值为 $w_{i}$。 定义状态为 $f_{i,j}$ 表示前 $i$ 个物品，容量为 $j$ 的情况下的最优解。 初始化为 $f_{0,0}$为 $0…
#### 本题使用扩展欧几里得算法 我们需要求关于 $x$ 的同余方程 $ a x \equiv 1 \pmod {b}$ 的最小正整数解。 这道题可以转化为扩展欧几里得解线性同余方程的算法。 先说下线性同余方程的形式： 给定整数 $a , b, m$ 对于这组数，求一个整数 $x$ 使它满足 $ a x \equiv…
首先对于题目要求：要使得两列火柴之间的距离和最小，即要每对火柴之间的高度尽可能的近。 由于火柴高度是 int 范围内的，因此我们要先对两个数组进行离散化操作。 那么我们其实就是让 $b$ 数组尽可能的符合 $a$ 数组原本的顺序。 由于 $a$ 数组是无序的，因此我们通过映射的方式将 $a$ 数组映射为有序的。 映射操…
#### 本题要用进制转换和找规律 我们读完题目就会发现题目说的 当 $k = 3$ 时，数列分别是$3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,3^0+3^1+3^2,…$ 那么我们可以把这个数列通过三进制表示出来，数列即为 $1,10,11,100,101,110,111,…$ 注意，以…