关于全站推荐

# port 0：前言（必读）
本文章是在学习 STL 算法和容器后写的，如果有缺少的容器或函数，请评论区指正。

本文为 c++ 环境，编译选项为 `-std=c++14 -O2`。

火车头：
\`\`\`cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    return 0;
}
\`\`\`
配套题单为：[877299](https://www.luogu.com.cn/training/877299)
#### **本文目前共约13k字。** ####
# port 1：容器
STL 库拥有很多好用的容器，通用的定义方法是：

\`\`\`cpp
容器类型 < 数据类型 > 名称;
\`\`\`

其中数据类型可以是 `int`、`long long` 之类的普通类型，也可以是其他的 STL，比如：
\`\`\`cpp
vector < pair < pair < int,int >,int > > a;
\`\`\`
## 通用的迭代器（必读）
\`\`\`cpp
容器类型 < 数据类型 >::iterator it;//定义
//对于普通类型
for(it = a.begin();it != a.end();it++){
    cout << *it << ' ';
}
//也可以
for(auto x : a){
    cout << x << ' ';
}
//对于map
for(it = mp.begin();it != mp.end();it++){
    cout << it->first << ' ' << it->second >> '\n';
}
//也可以
for(auto x : mp){
    cout << it.first << ' ' << it.second >> '\n';
}
\`\`\`
## 序列式容器
### vector
#### 简介
`vector` 是动态数组，支持随机访问，尾部插入效率高。
#### 基本定义
\`\`\`cpp
vector < int > a;//定义一个空的vector
vector < int > a(arr);//用数组初始化
vector < int > a(n);//长度为n，初始值为0
vector < int > a(n,x);//长度为n，初始值为x
\`\`\`
#### 常用操作
- 下标访问：`a[i]`
- 尾部插入：`a.push_back(x)`
- 尾部删除：`a.pop_back()`
- 获取大小：`a.size()`
- 容量查询：`a.capacity()`
- 清空容器：`a.clear()`
- 判断为空：`a.empty()`
- 更改大小：`a.resize(x)`
#### 迭代器
\`\`\`cpp
vector < int >::iterator it;//定义一个给vector的迭代器
\`\`\`
相关函数：
- `a.begin()`：返回头部迭代器
- `a.end()`：返回尾部迭代器
#### 插入与删除
- `a.insert(it,x)`：在迭代器 $it$ 位置插入值 $x$。
- `a.erase(it)`：删除迭代器 $it$ 位置的元素
- `a.erase(l,r)`：删除 $[l,r)$ 区间元素
#### 题目
暂无，请贡献一些。
### deque
#### 简介
`deque` 基本和 `vector` 一样，支持双端操作。
::::warning[注意]
**注意：竞赛中请不要用 `deque`。**
::::
#### 常用操作
`deque` 拥有 `vector` 的全部函数，还有两个函数：
- 头部插入：`a.push_front(x)`
- 头部删除：`a.pop_front()`
#### 题目
[P1886 滑动窗口 /【模板】单调队列](https://www.luogu.com.cn/problem/P1886)  
不会的话可以看下[题解](https://www.luogu.com.cn/article/bme3dc8w)或我的代码。

::::info[我的代码]
\`\`\`cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int a[1000005];
deque < int > q;
int n,m;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++){
        while(!q.empty() && a[q.back()] > a[i]) q.pop_back();
        q.push_back(i);
        if(i >= m){
            while(!q.empty() && q.front() <= i - m) q.pop_front();
            cout << a[q.front()] << ' ';
        }
    }
    cout << '\n';
    while(!q.empty()) q.pop_front();
    for(int i = 1;i <= n;i++){
        while(!q.empty() && a[q.back()] < a[i]) q.pop_back();
        q.push_back(i);
        if(i >= m){
            while(!q.empty() && q.front() <= i - m) q.pop_front();
            cout << a[q.front()] << ' ';
        }
    }
    return 0;
}
\`\`\`
::::
### list
#### 简介
`list` 是一个双向链表容器，支持任意位置的高效插入和删除操作，但不支持随机访问。
#### 基本定义
\`\`\`cpp
list < int > a;//定义一个空的list
list < int > a(arr);//用数组初始化
list < int > a(n);// 长度为n，初始值为0
list < int > a(n,x);//长度为n，初始值为x
list < int > a(begin,end);// 用迭代器范围初始化
\`\`\`
#### 常用操作
- 头部插入：`a.push_front(x)`
- 尾部插入：`a.push_back(x)`
- 头部删除：`a.pop_front()`
- 尾部删除：`a.pop_back()`
- 获取大小：`a.size()`
- 清空容器：`a.clear()`
- 判断为空：`a.empty()`
- 反转链表：`a.reverse()`
- 排序链表：`a.sort()`（注意不是全局的 `sort`）
- 移除指定值：`a.remove(x)`
#### 迭代器
\`\`\`cpp
list < int >::iterator it;// 定义一个正向迭代器
list < int >::reverse_iterator rit;// 定义一个反向迭代器
\`\`\`
相关函数：
- `a.begin()`：返回头部迭代器
- `a.end()`：返回尾部迭代器
- `a.rbegin()`：返回反向头部迭代器
- `a.rend()`：返回反向尾部迭代器
所以还可以这样：
\`\`\`cpp
auto it = a.begin();
auto rit = a.rbegin();
\`\`\`
#### 插入与删除
- `a.insert(it,x)`：在迭代器 $it$ 位置插入值 $x$
- `a.erase(it)`：删除迭代器 $it$ 位置的元素
- `a.erase(l,r)`：删除 $[l,r)$ 区间元素
- `a.splice(pos,b)`：将链表 $b$ 的所有元素插入到 $pos$ 位置
#### 题目
[B3656 【模板】双端队列 1](https://www.luogu.com.cn/problem/B3656)
## 关联式容器
### set
#### 简介
`set` 是一个有序的关联容器，其内部元素会按照一定的规则自动排序（默认升序），且不允许存在重复元素。它基于红黑树实现，支持高效的插入、删除和查找操作，时间复杂度通常为 $O(\log_2 n)$
。
#### 基本定义
\`\`\`cpp
set < int > s;//定义一个空的set，默认按升序排序
set < int,greater < int > > s;//定义一个按降序排序的set
int arr[] = {1,2,3};
set < int > s(arr);//用数组初始化
set < int > s(begin,end);//用迭代器范围初始化
set < int > s2(s);//拷贝初始化，用s初始化s2
\`\`\`
#### 常用操作
- `s.insert(x)`：插入值 $x$，若已存在则插入失败
- `s.erase(x)`：删除值为 $x$ 的元素，返回删除的元素个数
- `s.size()`：返回容器中元素的个数
- `s.clear()`：清空容器中所有元素
- `s.empty()`：若容器为空返回 `true`，否则返回 `false`
- `s.find(x)`：查找值为 $x$ 的元素，返回其迭代器；若不存在，返回 `s.end()`
- `s.count(x)`：返回值为 $x$ 的元素个数（由于 `set` 中无重复元素，结果只能是 $0$ 或 $1$）
#### 迭代器
\`\`\`cpp
set < int >::iterator it;//定义一个正向迭代器
set < int >::reverse_iterator rit; // 定义一个反向迭代器
\`\`\`
相关函数：
- `s.begin()`：返回指向第一个元素的正向迭代器
- `s.end()`：返回指向最后一个元素之后位置的正向迭代器
- `s.rbegin()`：返回指向最后一个元素的反向迭代器
- `s.rend()`：返回指向第一个元素之前位置的反向迭代器
所以还可以这样：
\`\`\`cpp
auto it = s.begin();
auto rit = s.rbegin();
\`\`\`
#### 插入与删除
- `s.insert(it,x)`：在迭代器 $it$ 指示的位置附近插入 $x$ （实际位置由排序规则决定），返回新插入元素的迭代器
- `s.insert(l,r)`：插入迭代器范围 $[l,r)$ 内的元素
- `s.erase(it)`：删除迭代器 $it$ 指向的元素，返回下一个元素的迭代器
- `s.erase(l,r)`：删除迭代器范围 $[l,r)$ 内的元素，返回 $r$ 的迭代器
#### 题目
[P11227 [CSP-J 2024] 扑克牌](https://www.luogu.com.cn/problem/P11227)
### map
#### 简介
`map` 是一种有序的关联容器，其内部存储的是**键值对（key-value pair）**，会根据键（$key$）的大小按照特定规则自动排序（默认升序），且键具有唯一性（不允许重复）。它基于红黑树实现，支持高效的插入、删除和查找操作，核心操作的时间复杂度通常为 $O(\log_2 n)$。
#### 基本定义
\`\`\`cpp
map < int,string > m1;//定义空map，key为int型，value为string型，默认按key升序排序
map <string,int,greater < string > > m2;//定义按key降序排序的map（key为string型，value为int型）
int a[] = {0,1,2,3};
string b[] = {" ","a","b","c"};
map <int,string > m3;//手动通过数组初始化map（键值对一一对应）
for(int i = 1;i <= 3;i++) m3[b[i]] = a[i];
map < int,string > m4(m3.begin(),m3.end());//用迭代器范围初始化（拷贝m3的所有元素）
map < int,string > m5(m3);//拷贝初始化，用m3的元素初始化m5
\`\`\`
#### 常用操作
- `m.insert({key,val})`：插入键值对 $(key,val)$，若 $key$ 已存在则插入失败
- `m.erase(key)`：删除键为 $key$ 的键值对，返回删除的元素个数（$0$ 或 $1$，因 $key$ 唯一）
- `m.size()`：返回容器中键值对的个数
- `m.clear()`：清空容器中所有键值对
- `m.empty()`：若容器为空返回 `true`，否则返回 `false`
- `m.find(key)`：查找键为 $key$ 的键值对，返回其迭代器；若不存在，返回 `m.end()`
- `m.count(key)`：返回键为 $key$ 的元素个数（因 $key$ 唯一，结果只能是 $0$ 或 $1$）
- `m[key]`：访问键为 $key$ 对应的 $value$；若 $key$ 不存在，会自动创建该键值对（$value$ 为默认值）
#### 迭代器
\`\`\`cpp
map < int,string >::iterator it;//定义正向迭代器
map < int,string >::reverse_iterator rit;//定义反向迭代器
\`\`\`
相关函数：
- `m.begin()`：返回指向第一个键值对的正向迭代器
- `m.end()`：返回指向最后一个键值对之后位置的正向迭代器
- `m.rbegin()`：返回指向最后一个键值对的反向迭代器
- `m.rend()`：返回指向第一个键值对之前位置的反向迭代器
所以还可以这样：
\`\`\`cpp
auto it = m.begin();//定义正向迭代器
auto rit = m.rbegin();//定义反向迭代器
\`\`\`
#### 插入与删除
- `m.insert(pos,{key,val})`：在迭代器 $pos$ 指示的位置附近插入键值对 $(key,val)$（实际位置由排序规则决定），返回新插入元素的迭代器
- `m.insert(l,r)`：插入迭代器范围 $[l,r)$ 内的所有键值对
- `m.erase(pos)`：删除迭代器 $pos$ 指向的键值对，返回指向下一个元素的迭代器（**注意：不能删除 `m.end()` 指向的位置**）
- `m.erase(l,r)`：删除迭代器范围 $[l, r)$ 内的所有键值对，返回迭代器 $r$
#### 题目
[P1102 A-B 数对](https://www.luogu.com.cn/problem/P1102)
## 容器适配器
### stack
#### 简介
`stack` 是一种 **后进先出（LIFO,Last In First Out）** 的容器适配器，只能在容器的一端（栈顶）进行插入和删除操作。它默认基于 `deque` 实现，也可以指定底层容器（如 `vector` 或 `list`）。
#### 基本定义
\`\`\`cpp
stack < int > s1; //定义空栈，元素类型为int，默认底层容器是deque
//用 vector作为底层容器
stack < int,vector < int > > s2;
//用list作为底层容器
stack < int,list < int > > s3;
\`\`\`
#### 常用操作
- `push(val)`：将元素 $val$ 压入栈顶
- `pop()`：弹出栈顶元素（不返回值，若需要取值请先 `top()`）
- `top()`：返回栈顶元素的引用
- `size()`：返回栈中元素个数
- `empty()`：判断栈是否为空，空返回 `true`，否则返回 `false`
#### 示例代码
\`\`\`cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    stack < int > s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << "栈顶元素: " << s.top() << '\n';
    cout << "栈大小: " << s.size() << '\n';
    s.pop();
    cout << "栈顶元素: " << s.top() << '\n';
    while(!s.empty()){//遍历
        cout << s.top() << ' ';
        s.pop();
    }
    return 0;
}
\`\`\`
#### **底层容器要求**
`stack` 是容器适配器，底层容器需要支持以下操作：  
`push_back()`  
`pop_back()`  
`back()`  
默认使用 `deque`，由于 `deque` 较慢所以我们通常指定指定底层容器为 `vector` 或 `list`：
\`\`\`cpp
stack < int,vector < int > > s;//底层容器为vector
stack < int,list < int > > s;//底层容器为list
\`\`\`
#### 题目
[B3614 【模板】栈](https://www.luogu.com.cn/problem/B3614)
### queue
#### 简介
`queue` 是一种 **先进先出（FIFO, First In First Out）** 的容器适配器，只能在队尾插入元素，在队头删除元素。它默认基于 `deque` 实现，也可以指定底层容器（如 `list`）。
#### 基本定义
\`\`\`cpp
queue < int > q1;//定义空队列，元素类型为int，默认底层容器是deque
//用list作为底层容器
queue < int,list < int > > q2;
\`\`\`
#### 常用操作
- `push(val)`：将元素 val 插入队尾
- `pop()`：删除队头元素（不返回值，若需要取值请先 `front()`）
- `front()`：返回队头元素
- `back()`：返回队尾元素
- `size()`：返回队列中元素个数
- `empty()`：判断队列是否为空，空返回 `true`，否则返回 `false`
示例代码
\`\`\`cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    queue < int > q;
    q.push(10);
    q.push(20);
    q.push(30);
    cout << "队头元素: " << q.front() << '\n';
    cout << "队尾元素: " << q.back() << '\n';
    cout << "队列大小: " << q.size() << '\n';
    q.pop();
    cout << "队头元素: " << q.front() << '\n';
    while(!q.empty()){
        cout << q.front() << ' ';
        q.pop();
    }
    return 0;
}
\`\`\`
#### **底层容器要求**
`queue` 是容器适配器，底层容器需要支持以下操作：  
`push_back()`  
`pop_front()`  
`front()`  
`back()`  
默认使用 `deque`，也可以指定：
\`\`\`cpp
queue < int,list < int > > q;//底层容器为list
\`\`\`
#### 题目
[B3616 【模板】队列](https://www.luogu.com.cn/problem/B3616)
### priority_queue
#### 简介
`priority_queue` 是优先队列，每次出队的元素都是当前队列中优先级最高的元素（默认最大值优先）。它的底层默认使用堆实现，并且是一种容器适配器，可以基于 `vector` 或 `deque` 作为底层容器。
#### 基本定义
\`\`\`cpp
//默认：最大堆（降序）
priority_queue < int > pq1;
//自定义比较器，最小堆（升序）
priority_queue < int,vector < int >, greater < int > > pq2;
//使用list不能作为底层容器（需要随机访问迭代器）
\`\`\`
#### 常用操作
-`push(val)`：将元素 $val$ 插入队列，并自动调整堆结构
- `pop()`：移除队头（优先级最高）的元素（不返回值）
- `top()`：返回队头元素
- `size()`：返回队列中元素个数
- `empty()`：判断队列是否为空，空返回 `true`，否则返回 `false`
#### 示例代码
\`\`\`cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    priority_queue < int > pq;//默认大顶堆
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);
    cout << "队头元素: " << pq.top() << '\n';
    pq.pop();
    cout << "队头元素: " << pq.top() << '\n';
    cout << "队列大小: " << pq.size() << '\n';
    while(!pq.empty()){
        cout << pq.top() << ' ';
        pq.pop();
    }
    return 0;
}
\`\`\`
#### 自定义比较器
如果存储的是自定义类型，可以自己写比较器：
```cpp
struct Person{
    string name;
    int age;
};

bool cmp(Person a,Person b){
    return a.age < b.age;
}

priority_queue < Person,vector < Person >,cmp > pq;
\`\`\`
#### 底层容器要求
`priority_queue` 底层容器需要支持随机访问迭代器，并且支持以下操作：  
`push_back()`  
`pop_back()`  
随机访问（如 `vector`、`deque`）  
默认使用 `vector` 作为底层容器，建议不要更改。
# port 2：算法
- `find`：顺序查找。`find(v.begin(),v.end(),x)`，其中 $x$ 为需要查找的值。
- `reverse`：翻转数组、字符串。`reverse(v.begin(),v.end())` 或 `reverse(a + x,a + y)`。
- `unique`：去除容器中相邻的重复元素。返回值为指向**去重后**容器结尾的迭代器或指针，原容器大小不变。与 `sort` 结合使用可以实现完整容器去重。
- `sort`：排序。`sort(v.begin(),v.end(),cmp)` 或 `sort(a + x,a + y,cmp)`，其中 $y$ 是排序的数组最后一个元素的后一位，$cmp$ 为自定义的比较函数。
- `stable_sort`：稳定排序，用法同 sort()。
- `nth_element`：按指定范围进行分类，即找出序列中第 $n$ 大的元素，使其左边均为小于它的数，右边均为大于它的数。`nth_element(v.begin(),v.begin() + n,v.end(),cmp)` 或 `nth_element(a + x,a + y + n,a + y,cmp)`。
- `binary_search`：二分查找。`binary_search(v.begin(),v.end(),x)`，其中 $x$ 为需要查找的值。
- `lower_bound`：在一个有序序列中进行二分查找，返回指向第一个 大于等于 $x$ 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。`lower_bound(v.begin(),v.end(),x)`。
- `upper_bound`：在一个有序序列中进行二分查找，返回指向第一个 大于 $x$ 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。`upper_bound(v.begin(),v.end(),x)`。
::::warning[`lower_bound` 和 `upper_bound` 的时间复杂度]
在一般的数组里，这两个函数的时间复杂度均为 $O(\log_2 n)$，但在 `set` 等关联式容器中，直接调用 `lower_bound(s.begin(),s.end(),x)` 的时间复杂度是 $O(n)$ 的。

`set` 等关联式容器中已经封装了 `lower_bound` 等函数（像 `s.lower_bound(x)` 这样），这样调用的时间复杂度是 $O(\log_2 n)$ 的。
::::
- `next_permutation`：将当前排列更改为 全排列中的下一个排列。如果当前排列已经是 全排列中的最后一个排列（元素完全从大到小排列），函数返回 `false` 并将排列更改为 全排列中的第一个排列（元素完全从小到大排列）；否则，函数返回 `true` `next_permutation(v.begin(),v.end())` 或 `next_permutation(v + x,v + y)`。
- `prev_permutation`：将当前排列更改为 全排列中的上一个排列。用法同 `next_permutation`。
# port 3：string
## 简介
`string` 则是一个简单的类，使用简单，在OI中被广泛使用。并且相比于其他 STL 容器，`string` 的常数较低。

`string` 能动态分配空间，这使得我们可以直接使用 `cin` 来输入，但其速度较慢。

`string` 的加法运算符可以直接拼接两个字符串或一个字符串和一个字符。`string` 重载了比较运算符，按字典序比较，所以我们可以直接调用 `sort` 对字符串进行排序。
## 声明
`string` 的定义方法十分简单，为 `string s`。
## 转 `char` 数组
`string` 转 `char` 数组的方式很简单，只要用一个函数 `s.c_str()` 就可以解决。
\`\`\`cpp
printf("%s",s);//编译错误
printf("%s",s.c_str());//能够正确输出
\`\`\`
## 长度
很多函数都可以返回 `string` 的长度，如下：
\`\`\`cpp
printf("%zu",s.size());//我用这个
printf("%zu",s.length());//有人用这个
printf("%zu",strlen(s.c_str()));//绝对的整活，还慢
\`\`\`
::::info[复杂度]
第三种写法是 $O(n)$ 的，前两种都是 $O(1)$ 的。
::::
::::warning[返回值]
这几种函数的返回值都是 `size_t` 或 `unsigned long` 类型。因此，这些返回值不支持直接与负数比较或运算，需要时要进行强制类型转换。
::::
## 查找
`find(s,pos)` 函数可以用来查找字符串中 $s$ 在 $pos$（含）之后第一次出现的位置（若不传参给 $pos$ 则默认为 $0$）。如果没有出现，则返回 `string::npos`（一般是 $-1$，但类型仍为 `size_t`/`unsigned long`）。
示例：
\`\`\`cpp
string s = "IAKIOI",s1 = "OI",s2 = "I";
int pos = 4;
s.find("I");//返回0
s.find("a");//返回string::npos
s.find(s1)//返回4
s.find(s2,pos);//返回5
\`\`\`
## 截取
`substr(pos,len)` 函数的参数返回从 $pos$ 位置开始截取最多 $len$ 个字符组成的字符串（如果从 $pos$ 开始的后缀长度不足 $len$ 则截取到末尾）。

示例：
\`\`\`cpp
string s = "IAKIOI", t = "OI";
s.substr(3,3);//返回IOI
t.substr(1,3);//返回I
\`\`\`
## 插入/删除
`insert(pos,cnt,s1)` 和 `insert(pos,s2)` 是插入函数。它们分别表示在 $pos$ 处连续插入 $cnt$ 次字符串 $s1$ 和插入字符串 $s2$。

`erase(pos,cnt)` 函数将字符串 $pos$ 位置开始（含）的 cnt 个字符删除（若不传参给 $cnt$ 则删去 $pos$ 位置及以后的所有字符）。

示例：
\`\`\`cpp
string s = "IAKIOI",t = " IOI";
char ch = '!';
s.erase(3);//s = "IAK"
s.insert(3,t);//s = "IAKIOI"
s.insert(7,3,ch);//s = "IAKIOI!!!"
\`\`\`
## 替换
`replace(pos,cnt,s1)` 和 `replace(l,r,s2)` 是替换函数。它们分别表示从 $pos$ 位置开始 $cnt$ 个字符的子串替换为 $s1$ 以及将以 $l$ 开始（含），$r$ 结束（不含）的子串替换为 $s2$，其中 $l$ 和 $r$ 均为迭代器。

示例：
\`\`\`cpp
string s = "IOI";
s.replace(1,2,"");//s = "I"
s.replace(s.begin(),s.begin() + 1,"NOI");//s = "NOI"
\`\`\`
## 例题
[P5734 【深基6.例6】文字处理软件](https://www.luogu.com.cn/problem/P5734)

# port 1：前言
自从上次写了[STL 学习笔记](https://www.luogu.com.cn/article/0fi7x46h)后，我就一直想写一些其他的东西，于是有了这篇文章。

本系列目前有 $2$ 篇文章，分别为：
1. [基本算法1：高精度](https://www.luogu.com.cn/article/fcm7mn36)
2. [基本算法2：排序](https://www.luogu.com.cn/article/1hwhgz7x)

::::warning[注意]{open}
本文需要提前学习以下知识：
- `string` 的使用，可以看[STL 学习笔记](https://www.luogu.com.cn/article/0fi7x46h)的port3
- 竖式，小学的东西，你肯定会用
::::
# port 2：简介
高精度算法用于完成一些无法用普通数据类型储存的计算，我们在此介绍以下六种高精度算法，它们分别是：
- 高精度比较
- 高精度加法
- 高精度减法
- 高精度乘法
- 高精度除法
- 高精度取模
# port 3：高精度比较
## 简介
高精度比较可以比较非常大的数字，时间复杂度为 $O(n)$，可以解决大数比较的问题。
## 思想
我们首先来看这道题：[U621859 高精度比较](https://www.luogu.com.cn/problem/U621859)

看数据范围，$80\%$ 的数据在 `int` 范围内，我们可以直接用 `int` 比较，得 $80$ 分。
::::error[code]
\`\`\`cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    int a,b;
    cin >> a >> b;
    if(a < b) cout << -1;
    if(a == b) cout << 0;
    if(a > b) cout << 1;
    return 0;
}
\`\`\`
::::
为了得到 $100$ 分，我们可以把题目分步解决：
- 用字符串存储两个数
- 判断符号
- 比较输出
## 实现
首先第一步：用字符串存储两个数，我这里用的是 `string`，很简单。
::::info[code]
\`\`\`cpp
string s1,s2;
cin >> s1 >> s2;
\`\`\`
::::
第二步：判断符号，如果是一正一负就可以直接输出，如果都是负就标记一下。
::::info[code]
\`\`\`cpp
if(s1[0] == '-' && s2[0] != '-'){
    cout << -1;
    return 0;
}
if(s1[0] != '-' && s2[0] == '-'){
    cout << 1;
    return 0;
}
bool f = false;
if(s1[0] == '-' && s2[0] == '-') f = true;
\`\`\`
::::
第三步：比较输出，首先比它们的长度，如果不一样就是长的更大，长度一样就按字典序的结果，最后如果有标记就将结果乘上 $-1$。
::::info[code]
\`\`\`cpp
int ans;
if(s1.size() != s2.size()){
    if(s1.size() > s2.size()) ans = 1;
    else ans = -1;
}else{
    if(s1 == s2) ans = 0;
    else if(s1 > s2) ans = 1;
    else ans = -1;
}
if(f) ans *= -1;
cout << ans;
\`\`\`
::::
## 完整代码
::::success[AC code]
\`\`\`cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    //第一步
    string s1,s2;
    cin >> s1 >> s2;
    //第二步
    if(s1[0] == '-' && s2[0] != '-'){
        cout << -1;
        return 0;
    }
    if(s1[0] != '-' && s2[0] == '-'){
        cout << 1;
        return 0;
    }
    bool f = false;
    if(s1[0] == '-' && s2[0] == '-') f = true;
    //第三步
    int ans;
    if(s1.size() != s2.size()){
        if(s1.size() > s2.size()) ans = 1;
        else ans = -1;
    }else{
        if(s1 == s2) ans = 0;
        else if(s1 > s2) ans = 1;
        else ans = -1;
    }
    if(f) ans *= -1;
    cout << ans;
    return 0;
}
\`\`\`
::::
[AC 记录](https://www.luogu.com.cn/record/241504105)
# port 4：高精度加法
## 简介
高精度加法用于解决大数的加法计算问题，时间复杂度为 $O(n)$。
## 思想
先来看[P1601 A+B Problem（高精）](https://www.luogu.com.cn/problem/P1601)这道题。

看数据范围可以发现：

> $20\%$ 的测试数据，$0\le a,b \le10^9$；

所以直接用 `int` 存就是[P1001 A+B Problem](https://www.luogu.com.cn/problem/P1001)，代码：
::::error[code]
\`\`\`cpp
#include <iostream>
using namespace std;

int main(){
    int a,b;
    cin >> a >> b;
    cout << a + b;
    return 0;
}
\`\`\`
::::
记录为：[243492790](https://www.luogu.com.cn/record/243492790)，得 $40$ 分 ~~（数据水了）~~。

$100$ 分的实现方法如下：

1. 把数用字符串存下来。

2. 把数**倒过来**存储进数组里，这样数组的下标 $i$ 就能对应原数的从右往左第 $i$ 位了。

3. 像做竖式加法一样一位一位对齐地进行加法，这里要注意进位，如果加出来的结果 $ \ge 10$，那么需要往更高一位进位，然后将这一位模 $10$。

4. 输出时要像存的时候倒着输出。
## 实现
首先看一下我的定义：
\`\`\`cpp
string s1,s2;
int a[1000],b[1000],c[1000];
int i,len;
\`\`\`
其中 $a$ 和 $b$ 为两个数，$c$ 为结果，$len$ 为长度。

第一步非常简单，就不说了，直接贴代码：
::::info[code]
\`\`\`cpp
cin >> s1 >> s2;
\`\`\`
::::
第二步也很简单，就是一定要**倒过来存**。
::::info[code]
```cpp
for(i = 0;i < s1.size();i++){
    a[s1.size() - i - 1] = s1[i] - '0';
}
for(i = 0;i < s2.size();i++){
    b[s2.size() - i - 1] = s2[i] - '0';
}
\`\`\`
::::
第三步要先求一下 $len$，再遍历一遍，把每位都加一下再处理进位。
::::info[code]
\`\`\`cpp
len = s1.size() > s2.size() ? s1.size() : s2.size();
for(i = 0;i < len;i++){
    c[i] += a[i] + b[i];
    c[i + 1] += c[i] / 10;
    c[i] %= 10;
}
\`\`\`
::::
最后看一下有没有多一位，然后**倒着输出**即可。
::::info[code]
\`\`\`cpp
len = c[len] != 0 ? len + 1 : len;
for(i = len - 1;i >= 0;i--){
    cout << c[i];
}
\`\`\`
::::
## 完整代码
::::success[AC code]
\`\`\`cpp
#include <bits/stdc++.h>
using namespace std;

string s1,s2;
int a[1000],b[1000],c[1000];
int i,len;

int main(){
    //第一步
    cin >> s1 >> s2;
    //第二步
    for(i = 0;i < s1.size();i++){
        a[s1.size() - i - 1] = s1[i] - '0';
    }
    for(i = 0;i < s2.size();i++){
        b[s2.size() - i - 1] = s2[i] - '0';
    }
    //第三步
    len = s1.size() > s2.size() ? s1.size() : s2.size();
    for(i = 0;i < len;i++){
        c[i] += a[i] + b[i];
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    //第四步
    len = c[len] != 0 ? len + 1 : len;
    for(i = len - 1;i >= 0;i--){
        cout << c[i];
    }
    return 0;
}
\`\`\`
::::
[AC 记录](https://www.luogu.com.cn/record/243499779)
# port 5：高精度减法
## 简介
高精度减法用于解决大数的减法计算问题，时间复杂度为 $O(n)$。
## 思想
先来看[P2142 高精度减法](https://www.luogu.com.cn/problem/P2142)这道题。

看数据范围可以发现：

> $20\%$ 数据 $a,b$ 在 long long 范围内；

所以直接用 `long long` 存就是变量的减法，代码：
::::error[code]
\`\`\`cpp
#include <iostream>
using namespace std;

int main(){
    long long a,b;
    cin >> a >> b;
    cout << a - b;
    return 0;
}
\`\`\`
::::
记录为：[243521502](https://www.luogu.com.cn/record/243521502)，得 $20$ 分。

$100$ 分的实现方法如下：

1. 把数用字符串存下来，要注意如果第一个数更小要交换两个数。

2. 把数**倒过来**存储进数组里，这样数组的下标 $i$ 就能对应原数的从右往左第 $i$ 位了。

3. 像做竖式减法一样一位一位对齐地进行减法，这里要注意退位，如果减出来的结果 $ < 0$，那么需要往更高一位借位，然后将这一位加 $10$。

4. 输出时要像存的时候倒着输出。
## 实现
首先看一下我的定义：
\`\`\`cpp
string s1,s2;
int a[10100],b[10100],c[10100];
int i,len,p;
char f = '+';
\`\`\`
其中 $a$ 和 $b$ 为两个数，$c$ 为结果，$len$ 为长度，$p$ 为结果的有效位置，$f$ 表示符号。

第一步非常简单，注意一下比较的部分参见port3，直接贴代码：
::::info[code]
\`\`\`cpp
cin >> s1 >> s2;
if(s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2)){
    f = '-';
    swap(s1,s2);
}
\`\`\`
::::
第二步也很简单，就是一定要**倒过来存**。
::::info[code]
\`\`\`cpp
for(i = 0;i < s1.size();i++){
    a[s1.size() - i - 1] = s1[i] - '0';
}
for(i = 0;i < s2.size();i++){
    b[s2.size() - i - 1] = s2[i] - '0';
}
\`\`\`
::::
第三步要先求一下 $len$，再遍历一遍，把每位都减一下再处理退位。
::::info[code]
\`\`\`cpp
len = s1.size();
for(i = 0;i < len;i++){
    if(a[i] >= b[i]){
        c[i] += a[i] - b[i];
    }else{
        a[i + 1]--;
        a[i] += 10;
        c[i] = a[i] - b[i];
    }
}
\`\`\`
::::
最后算一下有效位置并**输出符号**，然后**倒着输出**即可。
::::info[code]
\`\`\`cpp
if(f == '-') cout << f;
for(i = len - 1;i >= 0;i--){
    if(c[i] != 0){
        p = i;
        break;
    }
}
for(i = p;i >= 0;i--){
    cout << c[i];
}
\`\`\`
::::
## 完整代码
::::success[AC code]
\`\`\`cpp
#include <bits/stdc++.h>
using namespace std;

string s1,s2;
int a[10100],b[10100],c[10100];
int i,len,p;
char f = '+';

int main(){
    cin >> s1 >> s2;
    if(s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2)){
        f = '-';
        swap(s1,s2);
    }
    for(i = 0;i < s1.size();i++){
        a[s1.size() - i - 1] = s1[i] - '0';
    }
    for(i = 0;i < s2.size();i++){
        b[s2.size() - i - 1] = s2[i] - '0';
    }
    len = s1.size();
    for(i = 0;i < len;i++){
        if(a[i] >= b[i]){
            c[i] += a[i] - b[i];
        }else{
            a[i + 1]--;
            a[i] += 10;
            c[i] = a[i] - b[i];
        }
    }
    if(f == '-') cout << f;
    for(i = len - 1;i >= 0;i--){
        if(c[i] != 0){
            p = i;
            break;
        }
    }
    for(i = p;i >= 0;i--){
        cout << c[i];
    }
    return 0;
}
\`\`\`
::::
[AC 记录](https://www.luogu.com.cn/record/243523710)
# port 6：高精度乘法
## 简介
高精度乘法用于解决大数的乘法计算问题，时间复杂度最优为 $O(n \log_2 n)$，要用FFT，由于我~~太菜~~不想写FFT，所以复杂度为 $O(n^2)$。
## 思想
先来看[P1303 A*B Problem](https://www.luogu.com.cn/problem/P1303)这道题。

看题面：
> 每个非负整数不超过 $10^{2000}$。

所以又是高精度，这次是乘法，有点难。

$100$ 分的实现方法如下：

1. 把数用字符串存下来。

2. 把数**倒过来**存储进数组里，这样数组的下标 $i$ 就能对应原数的从右往左第 $i$ 位了。

3. 按照我们列竖式的方法，把每一位都乘过去，注意 $a_i \times b_j$ 要存到 $c_{i+j}$ 里，记得进位。

4. 输出时要像存的时候倒着输出。
## 实现
首先看一下我的定义：
\`\`\`cpp
string s1,s2;
int a[2005],b[2005],c[4000005];
int p;
\`\`\`
其中 $a$ 和 $b$ 为两个数，$c$ 为结果，$p$ 为结果的有效位置。

第一步非常简单，直接贴代码：
::::info[code]
\`\`\`cpp
cin >> s1 >> s2;
\`\`\`
::::
第二步也很简单，就是一定要**倒过来存**。
::::info[code]
\`\`\`cpp
for(int i = 0;i < s1.size();i++){
    a[i] = s1[s1.size() - i - 1] - '0';
}
for(int i = 0;i < s2.size();i++){
    b[i] = s2[s2.size() - i - 1] - '0';
}
\`\`\`
::::
第三步要先做一个双重循环，再乘一下后处理进位。
::::info[code]
\`\`\`cpp
for(int i = 0;i < s1.size();i++){
    for(int j = 0;j < s2.size();j++){
        c[i + j] += a[i] * b[j];
        if(c[i + j] >= 10){
            c[i + j + 1] += c[i + j] / 10;
            c[i + j] %= 10;
        }
    }
}
\`\`\`
::::
最后算一下有效位置，然后**倒着输出**即可。
::::info[code]
\`\`\`cpp
for(int i = s1.size() + s2.size() - 1;i >= 0;i--){
    if(c[i] != 0){
        p = i;
        break;
    }
}
for(int i = p;i >= 0;i--){
    cout << c[i];
}
\`\`\`
::::
## 完整代码
::::success[AC code]
\`\`\`cpp
#include <bits/stdc++.h>
using namespace std;

string s1,s2;
int a[2005],b[2005],c[4000005];
int p;

int main(){
    cin >> s1 >> s2;
    for(int i = 0;i < s1.size();i++){
        a[i] = s1[s1.size() - i - 1] - '0';
    }
    for(int i = 0;i < s2.size();i++){
        b[i] = s2[s2.size() - i - 1] - '0';
    }
    for(int i = 0;i < s1.size();i++){
        for(int j = 0;j < s2.size();j++){
            c[i + j] += a[i] * b[j];
            if(c[i + j] >= 10){
                c[i + j + 1] += c[i + j] / 10;
                c[i + j] %= 10;
            }
        }
    }
    for(int i = s1.size() + s2.size() - 1;i >= 0;i--){
        if(c[i] != 0){
            p = i;
            break;
        }
    }
    for(int i = p;i >= 0;i--){
        cout << c[i];
    }
    return 0;
}
\`\`\`
::::
[AC 记录](https://www.luogu.com.cn/record/243529271)
# port 7：高精度除法
## 简介
高精度除法用于解决大数的除法计算问题，时间复杂度为 $O(n)$。
## 思想
先来看[P1480 A/B Problem](https://www.luogu.com.cn/problem/P1480)这道题。

看题面：
> $0\le a\le 10^{5000}$，$1\le b\le 10^9$。

所以又是高精度，不过 $b$ 是低精度，所以简单一些。

$100$ 分的实现方法如下：

1. 把 $a$ 用字符串存下来，$b$ 用 `int` 存下来。

2. 从高位到低位遍历，每位除完后记一下余数。

3. 输出时要像存的时候倒着输出。
## 实现
首先看一下我的定义：
\`\`\`cpp
string s;
int a[5005],b;
long long rem = 0;
int p;
\`\`\`
其中 $a$ 和 $b$ 为两个数，$c$ 为结果，$p$ 为结果的有效位置。

第一步非常简单，直接贴代码：
::::info[code]
\`\`\`cpp
cin >> s >> b;
\`\`\`
::::
第二步也很简单，直接贴代码。
::::info[code]
\`\`\`cpp
for(int i = 0;i < s.size();i++){
    rem = (rem << 3) + (rem << 1) + (s[i] ^ 48);
    a[i] = rem / b;
    rem %= b;
}
\`\`\`
::::
最后算一下有效位置，然后**倒着输出**即可。
::::info[code]
\`\`\`cpp
p = s.size() - 1;
for(int i = 0;i < s.size();i++){
    if(a[i] != 0){
        p = i;
        break;
    }
}
for(int i = p;i < s.size();i++){
    cout << a[i];
}
\`\`\`
::::
## 完整代码
::::success[AC code]
\`\`\`cpp
#include <bits/stdc++.h>
using namespace std;

string s;
int a[5005],b;
long long rem = 0;
int p;

int main(){
    cin >> s >> b;
    for(int i = 0;i < s.size();i++){
        rem = (rem << 3) + (rem << 1) + (s[i] ^ 48);
        a[i] = rem / b;
        rem %= b;
    }
    p = s.size() - 1;
    for(int i = 0;i < s.size();i++){
        if(a[i] != 0){
            p = i;
            break;
        }
    }
    for(int i = p;i < s.size();i++){
        cout << a[i];
    }
    return 0;
}
\`\`\`
::::
[AC 记录](https://www.luogu.com.cn/record/243537921)
# port 8：高精度取模
## 简介
高精度除法用于解决大数的除法计算问题，时间复杂度为 $O(n)$。
## 思想
先来看[P2818 天使的起誓](https://www.luogu.com.cn/problem/P2818)这道题。

看题面：
> 对于 $100 \%$ 的数据，$2\le n\le 10^8$，$2\le m\le 10^{1000}$。

和高精度除法差不多，注意到存下来的余数直接输出即可。
## 实现
很简单，直接贴代码：
::::success[AC code]
\`\`\`cpp
#include <bits/stdc++.h>
using namespace std;

string s;
int b;
long long rem = 0;

int main(){
    cin >> b >> s;
    for(int i = 0;i < s.size();i++){
        rem = (rem << 3) + (rem << 1) + (s[i] ^ 48);
        rem %= b;
    }
    cout << (rem ? rem : b);
    return 0;
}
\`\`\`
::::
[AC 记录](https://www.luogu.com.cn/record/243541316)
# port 9：总结
本文到此结束了，感谢观看！

我会在下期《[基本算法2：排序](https://www.luogu.com.cn/article/1hwhgz7x)》再次回来。