AcWing
未读[toc]
AcWing 算法基础课笔记 1.基础算法-CSDNAcWing《算法基础课》第1章 算法基础 - AcWingAcWing 795 前缀和 - 糖豆爸爸 - 博客园AcWing 796. 子矩阵的和 - 糖豆爸爸 - 博客园
前缀和和差分1 一维前缀和一维前缀和是针对一维数组而言的，它表示数组中从起始位置到当前位置的元素的累积和, 也就是区间和
通过计算前缀和, 可以快速获取数组中任意一个区间 [l, r] 的区间和，即 a[l] + a[l+1] + ... + arr[r], 而不需要每次都重新计算. 这样可以在一些需要频繁计算区间和的情况下大大提高效率, 例如动态规划, 子数组问题等
总结公式:
前缀和: S[i] = a[1] + a[2] + ... a[i]区间和：S[r] - S[l - 1] = a[l] + ... + a[r]
说明:
假设 S0 = a0 = 0
数组 a 和 S 的第 1 个元素都不存储（下标为 0 ）, 而从第 2 个元素开始存储（下标为 1）
注意遍历范围是 1 ~ n
在一些不涉及 a[i] ...
AcWing
未读[toc]
第一讲 基础算法 - 04高精度 | Akari的小站
AcWing 794. 高精度除法【简单】1 题目描述给定两个非负整数（不含前导 0） A，B，请你计算 A/B 的商和余数。
输入格式:共两行，第一行包含整数 A，第二行包含整数 B。
输出格式:共两行，第一行输出所求的商，第二行输出所求余数。
数据范围:1 ≤ A 的长度 ≤ 100000,1 ≤ B ≤ 10000,B 一定不为 0
输入样例:
72
输出样例：
31
2 算法步骤大整数 ÷ 小整数.
高精度数组利用字符串读入
把字符串翻转存入两个整型数组 A, B
从高位到低位, 当前被除数, 存商, 求余数 *
把数组 C 从高位到低位依次输出
3 时间复杂度时间复杂度: O(n)
4 AC代码4.1 数组注意 : lc = la, 结合图片去理解.
#include <bits/stdc++.h>#define endl '\n'using namespace std;typedef long long LL;LL r; // 计算 ...
AcWing
未读[toc]
第一讲 基础算法 - 04高精度 | Akari的小站
AcWing 793. 高精度乘法【简单】1 题目描述给定两个非负整数（不含前导 0） A 和 B，请你计算 A×B 的值。
输入格式:共两行，第一行包含整数 A，第二行包含整数 B。
输出格式:共一行，包含 A×B 的值。
数据范围:1 ≤ A 的长度 ≤ 100000,0 ≤ B ≤ 10000
输入样例：
23
输出样例：
6
2 算法步骤
高精度数组利用字符串读入
把字符串翻转存入两个整型数组 A, B
从低位到高位, 累加乘积, 进位, 存余 *
把数组 C 从高位到低位依次输出
3 时间复杂度时间复杂度: O(n^2)
4 AC代码注意 : lc = la + lb, 结合图片去理解.
4.1 数组#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int A[N], B[N], C[N];int la, lb, lc;void mul(int A[], int B[], int C[]);in ...
AcWing
未读[toc]
第一讲 基础算法 - 04高精度 | Akari的小站
AcWing 792. 高精度减法【简单】1 题目描述给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。
输入格式:共两行，每行包含一个整数。
输出格式:共一行，包含所求的差。
数据范围:1 ≤ 整数长度 ≤ 10^5
输入样例：
3211
输出样例：
21
2 算法步骤
高精度数组利用字符串读入
把字符串翻转存入两个整型数组 A, B
若 A < B, 则交换 A, B, 输出负号 *
从低位到高位, 逐位求差, 借位, 存差 *
把数组 C 从高位到低位依次输出
3 时间复杂度时间复杂度: O(n)
4 AC代码4.1 数组#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int A[N], B[N], C[N];int la, lb, lc;bool cmp(int A[], int B[]);void sub(int A[], int B[], int C[]);int ma ...
AcWing
未读[toc]
第一讲 基础算法 - 04高精度 | Akari的小站
AcWing 791. 高精度加法【简单】1 题目描述给定两个正整数（不含前导 0），计算它们的和。
输入格式:共两行，每行包含一个整数。
输出格式:共一行，包含所求的和。
数据范围:1 <= 整数长度 <= 100000
输入样例:
1223
输出样例：
35
2 算法步骤
高精度数字利用字符串读入
把字符串翻转存入两个整型数组 A, B
从低位到高位, 累加, 进位, 存余 *
把数组 C 从高位到低位依次输出
3 时间复杂度时间复杂度: O(n)
4 AC代码4.1 数组#include <bits/stdc++.h>#define endl '\n'using namespace std;const int N = 1e5 + 10;int A[N], B[N], C[N];int la, lb, lc;void add(int A[], int B[], int C[]);int main(){ ios::s ...
AcWing
未读[toc]
AcWing 791. 高精度加法C++数组实现 - AcWing高精度模板汇总-实用 - AcWingAcWing 高精度模板 - 糖豆爸爸 - 博客园AcWing《算法基础课》第1章 算法基础 - AcWingAcWing 算法基础课笔记 1.基础算法-CSDN博客A01 高精度算法 加法_哔哩哔哩_bilibili
高精度高精度计算实际上用数组存储和模拟运算.高精度计算也被称为大整数计算
1 大整数的存储
当输入的数很大时，可采用字符串方式接收。
拆成一位一位的数字，把它们存在一个数组中，一个数组元素表示一位数字
数组中是这样存储的：逆序存储
数组下标
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
原数
1
2
3
4
5
-
存储数
5
4
3
2
1
-
倒序存储原因：因为整数运算大都是从低位到高位运算的，即数字是高位在前、低位在后，而数组是低位在前、高位在后，所以要倒序存储. 这样当遇到进位等情况时，当最高位要进位的时候，我们在数组的末尾使用 push_back() 加一位即可，较方便。反之，在头部加一位要将整个数组后移 ...
AcWing
未读
AcWing 790. 数的三次方根 - 糖豆爸爸 - 博客园第一讲 基础算法 - 03二分 | Akari的小站
AcWing 790. 数的三次方根【简单】一、题目描述给定一个浮点数 n，求它的三次方根。
输入格式共一行，包含一个浮点数 n。
输出格式共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。
数据范围−10000 ≤ n ≤ 10000
输入样例：
1000.00
输出样例：
10.000000
二、分析浮点数二分还是很简单的，最开始使劲设置最大和最小，精度一般设为 1e-8，然后根据条件写 check()，发现符合就向左或向右逼近，直到结果的差，精度在可以接受的范围内。以本题来说，给出的数据相当于 y，而我们输出的相当于 x，即：y = x*x*x。因为 −10000 ≤ n ≤ 10000，开三次方根不会超过 100，所以 l、r 设置为 -100, 100即可。保留 6 位小数，所以 eps = 1e-8。
实际上，21*21*21 < 10000 < 22*22*22，最小开到 22 即可。
三、AC代码/** * @ve ...
AcWing
未读
二分查找（折半查找） 之二 | Akari的小站
二分查找 | Akari的小站
AcWing 789. 数的范围 - 糖豆爸爸 - 博客园
AcWing 789. 数的范围 - AcWing - yxc
AcWing 789. 数的范围(二分终极分析！) - AcWing - crayongrq
【A05 二分查找算法 最好的板子 - 董晓算法 - 哔哩哔哩】
二分一、简介二分搜索是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
二分查找算法在最坏情况下是对数时间复杂度的，需要进行 O(log n) 次比较操作。二分查找算法使用常数空间，对于任何大小的输入数据，算法使用的空间都是一样的。除非输入数据数量很少，否则二分查找算法比线性搜索更快，但数组必须事先被排序。尽管一些特定的、为了快速搜索而设计的数据结构 ...
AcWing
未读[toc]
二分查找（折半查找） 之二 | Akari的小站
二分查找 | Akari的小站
AcWing 789. 数的范围 - 糖豆爸爸 - 博客园
AcWing 789. 数的范围 - AcWing - yxc
AcWing 789. 数的范围(二分终极分析！) - AcWing - crayongrq
【A05 二分查找算法 最好的板子 - 董晓算法 - 哔哩哔哩】
一杯茶，一包烟，一道算法看一天。
AcWing 789. 数的范围【简单】*一、题目描述给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。如果数组中不存在该元素，则返回 -1 -1。
输入格式第一行包含整数 n 和 q，表示数组长度和询问个数。第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。如果数组中不存在该元素，则返回 -1 -1。
数据范围1 ≤ n ≤ 10 ...
AcWing
未读[toc]
AcWing 788. 逆序对的数量 - 糖豆爸爸 - 博客园
第一讲 基础算法 - 02归并排序 | Akari的小站
感谢微信群群友的解答：黑桃皇后、五个结晶水、但为君故
现在我也是似懂非懂的，看一天了······太菜了，hhh。
AcWing 788. 逆序对的数量【简单】*一、题目描述给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。
输入格式第一行包含整数 n，表示数列的长度。第二行包含 n 个整数，表示整个数列。
输出格式输出一个整数，表示逆序对的个数。
数据范围1≤n≤100000，数列中的元素的取值范围 [1,109]。
输入样例：
62 3 4 5 6 1
输出样例：
5
二、解题方法
1、暴力/** * @version: * @author: @Akari * @date: 2024-01-24 15:44:13 **/#include <bits/stdc++.h>#d ...
