投稿
  1. 高性能架构探索首页
  2. C/C++

模板

admin • • C/C++ • 阅读 176

⭐ 算法汇总 ⭐

目录

  1. 前缀和

    1. 一维前缀和
    2. 二维前缀和

  2. kmp算法

  3. 双指针

  4. STL

  5. 结构体

  6. DSU

  7. algorithm中常用的函数

  8. [bfs / dfs](#bfs / dfs)

  9. 图论

    • dijkstra
    • spfa
    • floyd
    • 拓扑排序

  10. String

  11. 数论

    • 快速幂

  12. 高精度

前缀和

💺

适用场景：

  1. 通常是用来预处理的，在读入数据的同时就能够统计前缀和
  2. 常用来解决区间问题

一维前缀和

s[0] = a[0] = 0;

for(int i = 1; i <= n; i++){
    cin >> a[i];
    s[i] = s[i - 1] + a[i];
}

二维前缀和（用的蛮少的确实）

查看源图像

kmp算法

🌮

kmp算法是用于字符串匹配问题的

原理：next的含义一定要知道 ——

//s[]是文本串 p[]是模式串 n是s的长度，m是p的长度

//求next 数组
for(int i = 2, j = 0; i <= m; i++){
    while(j && p[i] != p[j + 1]) j = next[j];
    if(p[i] == p[j + 1]) j++;
    next[i] = j;
}

//开始匹配
for(int i = 1, j = 0; i <= n; i++){
    while(j && s[i] != p[j + 1]) j = next[j];
    if(s[i] == p[j + 1]) j++;
    if(j == m){
        j = next[j];
        //匹配成功之后的操作
    }
}
双指针

🏎️

适用情况：

  1. 一个序列维护一段区间
  2. 两个序列维护某种次序（归并排序）
for(int i = 0, j = 0; i < n; i++){
    while(j < i && check(i, j))
        j++;
    //具体的操作
}

一道真实代码（codeforce 279B）

for(int i = 0, j = 0; i < n; i++){
    while(j < n && sm + a[j] <= t){
        sm += a[j];
        j++;
    }
    ans = max(ans, r - i);
    sm -= a[i];
}

STL

vector 🌛

一维数组的使用

vector<int> a; // 存储单个类型
vector<pii> b; // 存储pair<类型， 类型>

能够直接使用的迭代器（其他的迭代器都是语句的返回值）

a.begin() = a.rend();
a.end() = a.rebegin();

vector的基本操作

  1. 插入操作

    🌑 insert(迭代器 + 偏移量， 元素)

    🌒 insert(迭代器 + 偏移量， [b数组]起始位置，[b数组] 结束位置)

    a.insert(a.begin() + 3, 5);
a.insert(a.begin() + 2, b + 2, b + 4); // b + 5不包括

// a: 1 2 3 4 5   b: 6 7 8 9 10
// a: 1 2 3 7 8 4 5

    🌘 push_back(元素) 在数组末尾插入

a.push_back(6)
  1. 删除操作

🌔 erase(迭代器 + 偏移量，迭代器 + 偏移量 [不包括])

🌖 erase(迭代器)

for(auto i = a.begin(); i != a.end(); i++){
    if(*i == 4)
        a.erase(i);
    if(*i == 10)
        a.erase(i, i + 2);
    }
    
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
                   +
                   |
// 1 2 3   5 6 7 8 9       12 13 14 15

🌓 pop_back() 删除数组的末尾元素

a.pop_back();
// a: 1 2 3
// a: 1 2
  1. 查询操作
a.front(); // 第一个元素
a.back(); // 最后一个元素
a[i];   // 用法跟数组相同
  1. 遍历
    🌙 i 是迭代器
for(auto i = a.begin(); i != a.end(); i++)
    cout << *i << endl;

🌕 it 是元素

for(auto it : a)
    cout << it << endl;

🌓 j 是下标 —— 前提是空间一定要存在（先resize一下）

for(int j = 0; j < a.size(); j++)
    cout << a[j] << endl;
  1. 常用函数

🌜 sort(起始位置， 结束位置)

sort(a.begin(), a.end());
    
//比较函数可以自己写，默认从小到大排序
bool cmp(int x, int y){
    return x > y;
}
    
bool cmp(const pair<int, char> a, const pair<int, char> b) {
    return a.first<b.first;
}
    
sort(a.begin(), a.end(), cmp);

🌛 reverse(迭代器 + 偏移量， 迭代器 + 偏移量 [取不到])

reverse(a.begin(), a.end());
reverse(a.begin() + 1, a.begin() + 3);
// a: 1 2 3 4 5
// a: 1 3 3 4 5
queue / priorty_queue🐼

  1. queue的小根堆就需要将待输入值取反

  2. 声明

    queue<int> q;
priorty_queue<pii , vector<pii>, greater<pii>> q;

  3. 入队 🍶

    q.push(3);
q.push({2,4});

  4. 出队 🌎

    q.pop()

  5. 访问元素 🌍

    q.front();
q.back();
map / unordered_map 💤

核心：

  1. 两者都是用来hash的，唯一的区别就是map是排好序的，而unordered_map没排序
  2. 第一个关键词必须唯一 🌊
  3. map本质上就是pair<int, int>，就是用来存放数据对的
map<string, int> m;
unordered_map<string, int> m;

常用的地方 —— 统计字符串出现的次数

for(int i = 0; i < n; i++){
    cin >> s;
    m[s]++;
}

⭐ 如果需要对map中的value进行排序的话，那么就没有必要开map来做，map的核心就是维护key的唯一性，那么可以借助pair和vector实现

vector<pii> v;

v.push(make_pair(3, 5)); 
v.push({3,5});

bool cmp(pii a, pii b)
    return a.second > b.second;

sort(v.begin(), v.end(), cmp);
set ⛅

当一个不重复的集合来用，比较好用于查询，判断这个元素是否存在在这个集合之中

  1. 插入元素

    set<int> a;
a.insert(1)

  2. 查询元素是否存在

    a.count(1); //只会输出0/1来判断元素是否存在，我感觉比find好用

  3. 删除

    a.earse(a.find(1));
结构体

🐋

真的超级实用，当单个物体包括多个属性的时候，就可以用结构体

bool cmp(node a, node b){ //按两个关键字排序
    if(a.w == b.w)
        return a.t > b.t; //在相同条件下，根据另一个要素排序
    return a.w > b.w;
}

结构体只是将数据对应关系包装起来了

DSU总结

⭐dsu能够解决的问题 ⭐

  • 连通性的问题

将每个状态或者个体看作一个点，将这些点通过函数连接，这样就会划分出不同的集合，用pre[i] = i来判断是否是存在多少个集合，并且集合中的统计基本上会统计在父节点上

核心代码

  • 查找 find
int find(int x){
	if(pre[x] == x)
        return x;
    return pre[x] = find(pre[x]);
}
  • 合并 merge
void merge(int x, int y){
	int fx = find(x);
    int fy = find(y);
    if(fx == fy)
        return;
    pre[fy] = fx;
}

这个代码是按秩压缩后的代码，这样压缩就是所有点都直接指向父节点，就是将整个并查集这棵树的深度减少

常见的额外维护的数组

  •   size[fx] += size[fy];

常见的小技巧

  1.  for(int i = 1; i <= n; i++){
     if(pre[i] == i)
         num[i] = ++cnt;
    • 对集合的遍历，可以筛出各个集合的根节点
    • num[i] = ++cnt;这条代码真的好，不仅找到了集合，还给集合打上了标记，num数组中的 i 对应的就是每个集合的根节点
  2.  for(int i = 1; i <= n; i++)
     a[num[find(i)]].push_back(color[i]);
    • num[find(i)]这样同一个集合就获得了同一个下标，就可以统计集合中的一些属性
  3.  == 法一 ==
 struct node{
     int x, y;
 }p[N];
 == 法二 ==
 int x[N];
 int y[N];
    • 用dsu维护像坐标这些的二维数据，但是dsu只能将两个一维的点合并到一个集合中，因此我们就要把二维的信息转化成一维的信息，这样的方法蛮多的，就举一种方法吧
    • 第二种方法就是 x * n + y，y总用的，我自己还是比较喜欢用结构体的方法
    • 多维的话就是不同的变量都会影响集合的连通，不单限于一种变量

  • 还有一个很重要的点：一定要初始化！！ ⭐

  • 接着是传递性的问题 —— 这个等有好的传递性的题目再去更新吧

Poj 1417 好题 dsu + dp 目前还是不会

algorithm中常用的函数

reverse

可以将一个容器直接翻转，包括STL或是数组，只是参数不同

vector<int>a;
int b[N];

reverse(a.begin() + 1, a.begin() + 4); //迭代器
reverse(b + 5, b + 10); // 数组名
sort

排序用，可以用于所有数据结构，这就是它的强大之处

bool cmp(int x, int y){
    if(x > y)
        return true;
    return false;
}

sort(a, a + n);
sort(b.begin(), b.end(), cmp);
lower_bound

不小于目标值的第一个元素 —— >= x

vector<int> v = {1, 2, 3, 4, 8};

auto it = lower_bound(v.begin(), v.end(), 3); //返回迭代器

cout << it - v.begin() << endl; //会输出下标2
cout << *it << endl; //会输出值3
upper_bound

大于目标值的第一个元素 ——> x

vector<int> v = {1, 2, 3, 4, 8};

auto it = lower_bound(v.begin(), v.end(), 3); //返回迭代器

cout << it - v.begin() << endl; //输出下标3
cout << *it << endl; //输出值4

二分查找有序序列，返回 0/1

vector<int> a{1,2,3,4,5,6};

int b = binary_search(a.begin(), a.end(), 7); //返回0 == b = 0
int c = binary_search(a.begin(), a.end(), 5); //返回1 == c = 1
getline
string s;
cin >> a;
getline(cin, s); //预读一行消除cin的干扰
for(int i = 0; i < 8; i++){
    getline(cin, s);
}

bfs / dfs

先聊聊bfs吧 🐮

关键词：最短路

核心思想：

  1. 单调性：对于某个特定的属性，入队的顺序必须保证性质的单调性
  2. 两段性：每一批加入队列中的元素都具有相同的性质，与前一段入队的性质保持差异

🤔 有点抽象，但是这两点非常重要

  1. bfs就是边权为 1 的图

  2. bfs在遍历的基础上，解决的是最短路问题，这点也是和dfs最大的区别

    •   void bfs(){
      queue<int> q;
      q.push(s);
      dis[s] = 0;
      while(!q.empty){
          int now = q.front();
          q.pop();
          for(int i = 0; i < 4; i++){
              //先判断条件
              //将满足条件的入队
          }
      }
  }

  3. 有一个很大的误区，就是bfs的起点只能加入一个点，其实不是的，多源bfs ——只要同时入队的点具有相同的性质，要保证整个队列的单调性和两段性（acwing 173 矩阵距离）

    •   for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
      	if(map[i][j] == '#')
      		q.push(make_pair(i, j)); // 将地图上‘#’的坐标入队

  4. bfs不仅仅能搜点到点的最短距离，也能够统计从某一个初始状态通过有限次转化到最终状态的最小次数 —— 最小步数模型（acwing 1107 魔板）

    最重要的是能够保证搜索到答案时候一定是最小的转化次数 ⭐

    while (!q.empty()){
    auto t = q.front();
    q.pop();
    
    //对这三种状态的搜索转化
    string m[3];
    m[0] = move0(t);
    m[1] = move1(t);
    m[2] = move2(t);

    for (int i = 0; i < 3; i ++ )
        if (!dist.count(m[i])){
            dist[m[i]] = dist[t] + 1;
       		pre[m[i]] = {'A' + i, t};
       		q.push(m[i]);
       		if (m[i] == end) 
                return dist[end];
       	}
   }
   return -1;
}

  5. 如果bfs的搜索空间很大，可以选择双端队列，起点和终点一起搜，两个队列交替搜索，当状态相遇时则说明搜索结束

    •   queue<int> q1;
  queue<int> q2;
  //还缺实践的代码
再来聊聊dfs吧 🐰

关键词：连通性，状态

核心思想：

  1. 回溯：一定要学会回溯的含义：什么时候回溯，什么时候不需要回溯，回溯的意义又是什么

    • 回溯其实就是试错的一种过程，撤销之前错误的操作，知道搜索完状态空间
    • 在统计连通块中点的个数的时候就不需要回溯

  2. 剪枝：dfs用的好不好其实就看剪枝了，如果搜索空间很大的化就需要在题目中寻找限制条件

  3. dfs能够解决一个状态能否到达另一个状态，只能判断连通性，不能保证搜索的路径是最短的 —— Codeforce 377A 属于是最好想到的dfs模型了，一般的题目不会这么直白的

    •   void dfs(int x, int y){
      size++;
      
      //边界条件的特判，代表着栈递归的结束
      if(cnt - size == k){
          flag = 1;
          return;
      }
      
      //空间状态的搜索
      for(int i = 0; i < 4; i++){
          int nx = x + dx[i][0];
          int ny = y + dy[i][1];
          
          if(flag == 1)
              return;
          
          if(judge(nx, ny)){
              vis[nx][ny] = 1;
              dfs(nx, ny);
          }
      }
  }

  4. 判断一种状态能否转化成另一种状态 —— 注意区别，不是要求最小的步骤，这种类型最难的是怎么抽象出状态 —— HDU 1181 变形课 真的是到好题，着状态找的确实有点巧妙

    •   struct{
      char start;
      char end;
  }map[N];
  
  void dfs(char next){
      if(next == 'm'){
          flag = 1;
          return;
      }
      
      for(int i = 0; i < len; i++){
          if(!vis[i] && map[i].start == next){
              vis[i] = 1;
              dfs(map[i].end);
              vis[i] = 0;  //回溯代表状态不止被遍历一次 important
          }
      }
  }

值得记录的题集🏇
一、
洛谷 p1019
带字符串匹配的问题
—— 字符串的后缀和字符串的前缀的匹配
跟那道头尾单个单词拼接的题大同小异，只是匹配的方式稍显差异。

int check(int x, int y){
    int f = 1;
    for(int i = s[x].size() - 1; i >= 1; i--){
        for(int j = i, k = 0; j < s[x].size(); k++, j++){
            if(s[x][j] != s[y][k]){
	        f = 0;
		break;
	    }
	}
	if(f == 1)
	  return s[x].size() - i;
	f = 1;
    }
    return 0;
}

完整代码

/************************************************************************* 
    > File Name: p1019.cpp
    > Author: Ansary
    > Created Time: 2022/3/9 19:44:57
 ************************************************************************/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

const int N = 1e5 + 2;

string s[21];
int vis[N];
int n;
int ans = -1, sum;
int check(int x, int y){
    int f = 1;
    for(int i = s[x].size() - 1; i >= 1; i--){
	for(int j = i, k = 0; j < s[x].size(); k++, j++){
	    if(s[x][j] != s[y][k]){
		f = 0;
		break;
	     }
	}
	if(f == 1)
	    return s[x].size() - i;
	f = 1;
    }
    return 0;
} 

void dfs(int x){
    int flag = 0;
    for(int i = 0; i < n; i++){
        if(vis[i] > 1 || check(x, i) == 0)
	    continue;
	if(check(x, i) == s[i].size() || check(x, i) == s[x].size())
	    continue;
	flag = 1;
	vis[i]++;
	ans += s[i].size() - check(x, i);
	dfs(i);
	vis[i]--;
	ans -= s[i].size() - check(x, i);
    }
    if(flag == 0)
        sum = max(ans, sum);
    return;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++)
	cin >> s[i];
    char sc;
    cin >> sc;

    for(int i = 0; i < n; i++){
	if(s[i][0] == sc){
            vis[i] = 1;
	    ans = s[i].size();
       	    dfs(i);
	    vis[i] = 0;
	}
    }  

    cout << sum << endl;
}

二、
洛谷 p1025

  • 当出现n个物品中选m个，将n拆成m个数之后，往往可以选择用dfs遍历（数据范围要小）
  • 为了保证每次取的数都是单调不递减的，下一次的遍历的开始是上一次遍历的结束，并且 sum + i * (k - num) >= n
/*************************************************************************
    > File Name: p1025.cpp
    > Author: Ansary
    > Created Time: 2022/3/9 21:18:45
 ************************************************************************/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int n, k;
int ans;

//下一个数一定是上一个数的不递减
void dfs(int num, int startx, int sum){
    if(num == k){
	if(sum == n)
	    ans++;
	 return;
    }
    
    for(int i = startx; sum + i * (k - num) <= n; i++)
        dfs(num + 1, i, sum + i);
}

int main(){
    cin >> n >> k;
    dfs(0, 1, 0);
    cout << ans << endl;
}
图论

图论这一板块知识点可谓是又广又难，那我就把自己会的记录下来吧

img

⭐ vis数组的应用

img

建图的方法 🏖️

有向图的结构体

struct Edge{
	int to, w, next;
}edges[N];

初始化

void init(){
    memset(dis, inf , sizeof dis);
    memset(vis, 0, sizeof vis);
    memset(head, -1, sizeof head);
    cnt = 0;
}

加边

void add(int from, int to, int w){
    edges[cnt].w = w;
    edges[cnt].to = to;
    edges[cnt].next = head[from];
    head[from] = cnt++;
}
dijkstra :happy:

适用的范围：

  1. 单源最短路问题
  2. 非负权边

核心思想：贪心，每次取出的都是dis最小的点，并且这个点在之后是不会被再次更新了，每个点只会被更新一次

核心代码

void dijkstra()
{
    dis[s] = 0;
    for(int i = 1; i <= n-1; i++){
        int mi = inf, now;
        for(int j = 1; j <= n; j++){
            if(vis[j] == 0 && dis[j] < mi){
                mi = dis[j];
                now = j; 
            }
        }
        vis[now] = 1;
        for(int i = head[now]; i != -1; i = edge[i].next){
            int v = edge[i].to; 
            if(dis[v] > dis[now] + edge[i].w) 
                dis[v] = dis[now] + edge[i].w;             
        }
    }
}

优先队列优化的版本，适用于稀疏图

void dijkstra(){
    priority_queue<pii, vector<pii>, greater<pii>> q;
    dis[s] = 0;
    q.push({dis[s], s});  //存pair
    while(!q.empty()){
        int now = q.top().second;
        q.pop();
        if(vis[now] == 1)
            continue;
        vis[now] = 1;
        for(int i = head[now]; i != -1; i = edges[i].next){                
            int v = edges[i].to;
            if(dis[v] > dis[now] + edges[i].w){
                dis[v] = dis[now] + edges[i].w;
                q.push({dis[v],v});
           }
       }
}
spfa 🌊

适用范围：

  1. 单源最短路
  2. 可以处理存在负权的图
  3. 可以判断图中是否存在负权回路

核心思想：每个点都可能被重复更新

  • 先给出用于单源最短路径的模板（存在负权边是没有影响的）

    •   void spfa(){
      dis[s] = 0;
      queue <int> q;
      q.push(s);
      vis[s] = 1;
      while(!q.empty()){
          int now = q.front();
          q.pop();
          vis[now] = 0;
          for(int i = head[now]; i != -1; i = edges[i].next){
              int v = edges[i].to;
              if(dis[v] > dis[now] + edges[i].w){
                  dis[v] = dis[now] + edges[i].w;
                  if(vis[v] != 0)
                      continue;
                  vis[v] = 1;
                  q.push(v);
              }
          }
      }
  }

  • 判断是否存在负权回路（判断条件：同一个节点入队的次数超过了总的节点数num[v] >= n） ——（POJ 3259-Wormholes）

    •   bool spfa(){
      queue<int> q;///队列
      memset(num,0,sizeof(num));///记录该点进入队列的次数
      vis[1]=1;///进队标记1
      num[1]=1;
      dis[1]=0;
      q.push(1);
      while(!q.empty()){
          int now = q.front();
          q.pop();
          vis[now] = 0;//只要出队就取消标记
          for(int i = head[q]; i != -1; i = edges[i].next){
              int v = edges[i].to;
              if(dis[now] + edges[i].w < dis[v]){
                 dis[v] = dis[now] + edges[i].w;
                 if(!vis[v]){
                     num[v]++; //记录点入队的累计次数
                     if(num[v] >= n)//如果进队的次数等于n的话，说明有负环的存在了
                          return false;
                     vis[v] = 1;
                     q.push(v);
                 }
              }
          }
      }
      return true;
  }
Floyd 🍥

适用范围：

  1. 多源最短路径
  2. 得看题目中所给的n，v的范围，范围小的话就无脑用就完事
  3. 可以求出任意两点的距离，这点很重要哦

核心思想：Dp，复杂度是真的高，三层for循环

朴实无华的三层for循环

for(int k = 1; k <= n; k++)
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(e[i][j] > e[i][k] + e[k][j])
                e[i][j] = e[i][k] + e[k][j];
拓扑排序 🌳

适用范围：

  1. 可以求无环图的最短路径
  2. 判断是否存在环，入队的点数小于总的n，说明有环

核心思想：先将入度为0的点入队，每次出队的时候更新入度的数组，若出现新的入度为0的点就入队

  • 最短路径

    •   long long topsort(){
      queue <int> Q;
      dis[1] = 0;
      
      //这个预处理是关键
      for(int i = 1; i <= n; i++) 
          if(du[i]==0) 
              Q.push(i);
      
      while(!Q.empty()){
          int now = Q.front();Q.pop();
          for(int i = head[now]; i != -1; i = edge[i].next){
              int to = edge[i].to;
              long long d = edge[i].d;
              dis[to] = min(dis[to],dis[now]+d);
              if(--du[to] == 0) 
                  Q.push(to);
          }  
      }
      return max(0ll, dis[n]);
  }

  • 判环代码

    •   int topsort(){
      int ans=0; // 把额外的部分标记出来
   
      queue<int>q;
      for(int i = 1; i <= n; i++){
          if(in[i] == 0){
              q.push(i);
              ans++; // 把额外的部分标记出来
          }
      }
   
      while(!q.empty()){
          int now = q.front();
          q.pop();
   
          for(int i=0; i < G[now].size(); i++){
              int v = G[now][i];
              in[v]--;
              if(in[v]==0){
                  q.push(v);
                  ans++;  // 把额外的部分标记出来
              }
          }
      }
      return ans;
  }
  
  //在main函数中判断
  if(ans == n)
      cout << "Yes" << endl;
  else
      cout << "No" << endl;

    上面都是一些最基础的算法，接着就讲下一些图论的小技巧吧

    虚拟源点 / 汇点 🌏
    1. 同时有多个源点和多个汇点，建立超级源点和超级汇点
    2. 同时有多个源点和一个汇点，建立超级源点
    3. 同时有多个汇点和一个源点，建立超级汇点

    突然想到跟多源bfs有点像，相当于一开始多个点入队而不是单个点，不知道这个想法正不正确 🤔

    image-20211107114240060

    Hdu 2680 Choose the best route（Dijkstra + 建立超级源点）

    for(int i = 0; i < m; i++){
    int p;
    cin >> p;
    add(0, p, 0); // 将源点与 0 这个虚拟点相连，w为 0
}

dijkstra(0); // 从虚拟源点开始搜索
    反向建图 🌗

    条件：当多个源点对应一个汇点时，我们可以选择反向建图（Hdu 2680）

    for(int i = 0; i < n; i++){
    int a, b, c;
    cin >> a >> b >> c;
    add(b, a, c); //连边的时候直接反向建图
}
    很难不总结

    图论的代码其实不是很难，难的点其实在怎么建图上，只要图建出来了，写起来就是打板子

String

具有STL中的所有属性，这就是它的强大之处，可以参考

  • String转int的技巧

    for(int i = 0; i < tmp.size(); i++)
    sum = sum * 10 + (tmp[i] - '0');

erase函数可以把string删没的

数论

快速幂
  • a * b 对p取模的值
ll mul(ll a, ll b, ll p){
    ll ans = 0;
    for(; b; b >>= 1){
        if(b & 1)
            ans = (ans + a) % p;
        a = a * 2 % p;
    }
    return ans;
}
  • ab 对p取模的值
int power(int a, int b, int p){
    int ans = 1 % p;
    for(; b; b >>= 1){
        if(b & 1)
            ans = (long long)ans * a % p;
        a = (long long)a * a % p;
    }
    return ans;
}
最小公约数
int gcd(int a, int b){
	return b ? gcd(b, a % b) : a;
}
最大公倍数
int lcm(int a, int b){
    return a * b / gcd(a, b);
}

思维题

image-20220109145209021

  • 遍历的时候根据题目所给的限制条件找到遍历的条件
  • 不重复且在意顺序的时候，可以用 set 实现
  • 总结： STL还是没用熟

高精度

高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

高精度乘法

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

原文链接: https://www.cnblogs.com/Ansary/p/15828513.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

    模板

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/186911

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月12日 上午11:12
下一篇 2023年2月12日 上午11:12

相关推荐