Note-algorithm

算法备考

参考博客：

• https://blog.csdn.net/coooode_king/article/details/129467411
• https://blog.csdn.net/Cyan_rose/article/details/103018865

CCF备考技巧

CSP（计算机软件能力认证考试），主要覆盖大学计算机专业所学习的程序设计，数据结构，算法以及相关的数学基础知识。

包括但不限于：

• 程序设计基础：
  逻辑与数学运算，分支循环，过程调用（递归），字符串操作，文件操作，etc.
• 数据结构：
  线性表（数组，队列，栈，链表），树（堆，排序二叉树），哈希表，集合与映射，图，etc.
• 算法与算法设计策略：
  排序与查找，枚举，贪心策略，分治策略，递推与递归，动态规划，搜索，图论算法，计算几何，字符串匹配，线段树，随机算法，近似算法, etc.

考试模式：

• OI机制（分点给分
• 4h内完成5道题

题型大致分布&注意事项：（据一位CSP420分的学姐说

• 第一题：水题
  稍有编程经验，20+-行代码可搓完
  1.注意细节：
  long long
  边界
  特殊情况
  2.用文件读入可节省大量时间
  3.宏定义节省for循环书写用时
  #define _for(i , a , b) for(int i=a; i<b; i++)
  4.声明数组大小时，用const定义的伪常量方便修改

  const int N=1007
  int Num[N] , Sum[N];
  char str[N]

• 第二题：小模拟
  处理比较简单的问题，需要梳理简单的逻辑和过程
  1.多重循环，接近n^2的复杂度。一般是时序题，熟练运用排序、多元数组、STL会有奇效
  2.必备STL神器
  string：字符串查找、拼接、花式读入
  set：自动排序，去重
  vector：盲开数组的首要选择
  priority_queue：自定义优先级的队列
  map：不同类型数据的双向字典

• 第三题：大模拟，字符串处理
  处理复杂的问题，涉及字符串的问题居多
  1.熟练掌握各种输入函数与字符串的处理，DFS, BFS，
  2.会设计复杂的层次化结构
  3.题库
  ZJU：acm.zju.edu.cn
  PKU：acm.pku.edu.cn/JudgeOnline
  HDU：acm.hdu.edu.cn
  USACO：train.usaco.org/usacogate
  Codeforces：codeforces.com
  4.题目不难，只是变态（😄）

• 第四题：算法题
  难度中，重点考图论和动规
  1.熟练掌握最小生成树、最短路径、简单递推
  2.会强连通分量，欧拉函数，动规优化（四边形优化，etc.
  3.会将DFS转变为非递归式避免爆栈（80‘->100’）

• 第五题：算法题
  难度高，设计算法面很多，数据量很大，需要堆算法极致优化，很难满分
  1.熟练掌握各种程序设计算法，以及对时间、空间的优化
  2.快速coding, debug
  3.精神状态极佳

常识

常识

long long

#define ll long long //不开long long 见祖宗

#define

#define INF  0x3f3f3f3f; //无穷大 与10^9同数量级 1061109567
// 可以使用memset(array, 0x3f, sizeof(array))
#define x first ;//结合pair
#define y second;

万能头文件

#include <bits/stdc++.h>

时间复杂度： 5*10e8对应1s，10^8->超过了可能会tle

空间复杂度：

数组最大开10^7
单个int大概能到10^9
1.代码中一共开辟了多少byte？ int/char/double => 4/1/8 byte
2.1024*1024byte == 1MB , 与题目限制的MB数比较即可。

循环m

循环 n 次与循环 n - 1 次
在写 while 循环时，如果需要循环 n 次可以这样写：while(n--)。
当需要循环 n - 1 次时则可以写成：while(--n)

puts

需要输出回车换行时，可以直接使用 puts(""); 语句。需要包含 #include<cstdio> 头文件

next_permutation （全排列）

// 当前排列更改为全排列中的下一个排列。
// 如果当前排列已经是全排列中的最后一个排列（元素完全从大到小排列），函数返回 false 并将排列更改为全排列中的第一个排列（元素完全从小到大排列）；否则，函数返回 true。
// 1 结合 数组
int a[] = {1, 2, 3, 4, 5};
    do{
      for(int i = 0; i < 5; i ++) cout << a[i] << " ";
      cout << endl;
    }while(next_permutation(a, a + 5));

// 2结合 vector
vector<int> a = {1, 2, 3, 4, 5};
    do{
      for(int i = 0; i < a.size(); i ++) cout << a[i] << " ";
      cout << endl;
    }while(next_permutation(a.begin(), a.end()));

// 全排列要先sort
int main(int argc, char** argv) {
    string str;
    cin>>str;
    sort(str.begin(),str.end());
    do{
        cout<<str<<endl;
    }while(next_permutation(str.begin(),str.end()));
    return 0;
}

数据量

常见数换算

2^0~2^10:0 1 2 4 8 16 32 64 128 256 524 1024
2^20 约10^6 (1048576)
2^16 =65536
2^15 =32768
2^63 =10^18

打表模板

#include <iostream>
#include <ostream>
using namespace std;
int sum=0;//计数器
void cnt(int n)
{
    sum++;
    for(int i=1;i<=n/2;i++)
        cnt(i);
}
int main()
{
	freopen("data.out","w",stdout);
	int n;
	for(n=1;n<=1000;n++)//计算每个结果
	{
		sum=0;//初始化计数变量 
		cnt(n);
		cout<<sum<<",";
		//将结果输出至文件
	}
}

其它小知识

循环条件中一定不能用函数，否则会很慢。需要用根号时用i <= n / i;
判断一个数是否为整数：  if((int)x==x)  
当需要多次操作数组时需要备份： memcpy(backup, g, sizeof g);
把数组转化为数： for(int i = l; i <= r; i ++) res = res * 10 + num[i];
多行字符矩阵的快速读入for(int i=0; i<n; i++) { cin>>s; for(int j=0; j<s.length(); j++) { if(s[j]=='A') ans++; }
快速幂算法
res = res / i * (i - 1) 先写除法再写乘法防止中间结果溢出

实际运用模板

判断日期合法模板

bool check(int year, int month, int day)
{
    if(!month || month >= 13) return false;
    if((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) months[2] = 29;
    if(day > months[month] || day <= 0) return false;
    months[2] = 28;
    return true;
} 

输入输出

连续读取：

while (cin >> a >> b) { ...}

流同步：

ios::sync_with_stdio(false); 
cin.tie(0); 
cout.tie(0);

getchar()

std::getline(std::cin, str) 读入字符串直到行尾

int n,m; 
cin>>n>>m;
getchar();//读取换行符 
string str,temp; 
getline(cin,str);

使用getline进行读取

int n;
cin>>n;
cin.get();
for(int i = 0; i < n; i++ )
    {
        string s;
        getline(cin,s); // 读取带空格的字符串，整行读取
    }

不读取空格：while(cin >> c) str += c;

小数位数

#include <iomanip>
cout << fixed << setprecision(3) << x << " " << y << endl;

printf("%.4lf", m);

进制输出

int a = 2022;
int b = 0xaaa;
cout << hex << a << endl;
cout << dec << b << endl;

错误 & 调试

Segment fault 错误出现的原因

• 内存访问越界：访问数组时使用错误的下标，导致数组访问越界；搜索字符串时，依靠字符串结束符来判断字符串是否结束，但是字符串没有正常的使用结束符。
• 非法指针：使用空指针；新申请指针忘记赋 NULL，也忘记分配空间，直接使用造成非法访问。
• 堆栈溢出：数组开的非常大，导致堆栈溢出。

解决方法
 当做题遇到 Segment fault 错误时是不好调代码的，因为通常编译器只会报这个错误，但是不会报出现错误的具体地址。这时候可以使用 exit(0) 函数（正常退出程序）来定位错误出现的地方。配合二分法找到问题地点。

system(“pause”)

数论

裴蜀定理 ax+by = n * gcd(a,b) x,y是未知量

求gcd：更相减损法，辗转相除法（STL中的__gcd可以直接求）

引理：给定a，b 若d=gcd(a,b)>1 则一定不能凑出最大数
结论：如果 a,ba,b 均是正整数且互质，那么由 ax+by,x≥0,y≥0不能凑出的最大数是(a−1)(b−1)−1

模运算性质

(a * b) % p = (a % p * b % p) % p

输出正余数:

 int get_mod(int a, int b)   // 求a除以b的正余数
{return (a % b + b) % b;}   

取整

#include<cmath>
ceil((double)a / b);

约数

任何一个大于 1 数都能分解为素数幂次方乘积的形式
把一个数N 写成：N = (p1^x1^)(p^x2)(p3^x3)…(pk^xk)，其中pi为质数。则N的约数个数为：(x1+1)(x2+1)(x3+1)…(xk+1)

string>

s.substr(start_pos, num)

string流处理（stringstream）

#include

字符串转数字

stringstream ss;
int a = 50; string b;
ss << a; ss >> b;

string & int 互转

#include<string>
// string 转 int:
int num = stoi(s) 
long num = stol(s);
long long num = stoll(s);
double num = stod(s)
// int 转 string:     
string num = to_string(num) 

手写

// 将一个数的所有位数提取出来:
while(x)
{int t = x % 10;x /= 10;.....}
// 将字符串转换为整数:
for(int i = 0; i < str.size(); i ++)
{x = x * 10 + str[i] - '0';}

字符串以空格分隔split

stringstream ss;
string a ="how old are you , dear ?";
ss << a;
string b;
while(ss >> b) cout <<b<<endl;

string

#include<bits/stdc++.h>
using namespace std;
int main(){
    string str ="123456789abcdefghiaklmn";

    for(int i=0;i<10;i++) //把str看成一个字符串数组
        cout<<str[i]<<" ";
    cout << endl;

//find函数
    int pos = str.find("目标", start_pos); //找到输出pos,否则输出-1
    cout<<"123的位置: "<<str.find("123")<<endl;
//输出：123的位置: 0
    cout<<"34在str[2]到str[n-1]中的位置: "<<str.find("34",2)<<endl;
//输出：34在str[2]到str[n-1]中的位置: 2
    cout<<"ab在str[0]到str[12]中的位置: "<<str.rfind("ab",12)<<endl;
//输出：ab在str[0]到str[12]中的位置: 9

//substr()函数
    cout<<"str[3]及以后的子串:"<<str.substr(3)<<endl;
//输出：str[3]及以后的子串:456789abcdefghijklmn
//若小于限制长度则报错
    cout<<"从str[2]开始的4个字符:"<<str.substr(2,4)<<endl;
//输出：从str[2]开始的4个字符:3456

//find()函数
    str.replace(str.find("a"), 5, "@#");
    cout<<str<<endl;
//输出：123456789@#fghiaklmn

//insert()函数
    str.insert(2, "***");
    cout<<"从2号位置插入: "<<str<<endl;
//输出：12***3456789@#fghiaklmn

//添加字符串：append()函数
    str.append("$$$");
    cout<<"在字符串str后面添加字符串:"<<str<<endl;
//输出：12***3456789@#fghiaklmn$$$

//字符串长度
    cout<<str.size()<<endl;
    cout<<str.length()<<endl;

//交换字符串：swap()函数
    string str1="aaa",str2="bbb";
    swap(str1, str2);
    cout<<str1<<" "<<str2<<endl;

//字符串比较函数：compare()，相等输出0，不等输出1
    cout<<str1.compare(str2)<<endl;
    if(str1==str2) cout <<"=="; //直接比较也行
    if(str1!=str2) cout <<"!=";

    return 0;
}

树形dp

求树的直径

https://www.cnblogs.com/ljy-endl/p/11612275.html

初始化

memset(a, 0, sizeof(a));
fill(&a[0], a + sizeof(a) / sizeof(int), 1);

数据结构

指针与链表

链表指针节点新建可以这样it->next = new ListNode;

指针本身可作为bool值，有指针为1，nullptr为0

线段树

https://blog.csdn.net/weq2011/article/details/128791426

二叉树

以及访问（https://www.luogu.com.cn/problem/P1827）

并查集（UnionFind）

• 用集合中的某个元素来代表这个集合，则该元素称为此集合的代表元；
• 一个集合内的所有元素组织成以代表元为根的树形结构；
• 对于每一个元素 x，pre[x] 存放 x 在树形结构中的父亲节点（如果 x 是根节点，则令pre[x] = x）；
• 对于查找操作，假设需要确定 x 所在的集合，也就是确定集合的代表元。可以沿着pre[x]不断在树形结构中向上移动，直到到达根节点。
• 因此，基于这样的特性，并查集的主要用途有以下两点：
• 1、维护无向图的连通性（判断两个点是否在同一连通块内，或增加一条边后是否会产生环）；
• 2、用在求解最小生成树的Kruskal算法里。
• 时间复杂度logn（加上路径压缩和rank优化）

一般来说，一个并查集对应三个操作：

• 初始化（ Init()函数 ）
• 查找函数（ Find()函数 ）
• 合并集合函数（ Join()函数 ）

代码：

const int  N=1005					//指定并查集所能包含元素的个数（由题意决定）
int pre[N];     					//存储每个结点的前驱结点 
int rank[N];    					//树的高度 
void init(int n)     				//初始化函数，对录入的 n个结点进行初始化 
{
    for(int i = 0; i < n; i++){
        pre[i] = i;     			//每个结点的上级都是自己 
        rank[i] = 1;    			//每个结点构成的树的高度为 1 
    } 
}
int find(int x)     	 		    //查找结点 x的根结点 
{
    if(pre[x] == x) return x;  		//递归出口：x的上级为 x本身，则 x为根结点 
    return find(pre[x]); 			//递归查找 
} 
 
int find(int x)     				//改进查找算法：完成路径压缩，将 x的上级直接变为根结点，那么树的高度就会大大降低 
{
    if(pre[x] == x) return x;		//递归出口：x的上级为 x本身，即 x为根结点 
    return pre[x] = find(pre[x]);   //此代码相当于先找到根结点 rootx，然后 pre[x]=rootx 
} 

bool isSame(int x, int y)      		//判断两个结点是否连通 
{
    return find(x) == find(y);  	//判断两个结点的根结点（即代表元）是否相同 
}

bool join(int x,int y)
{
    x = find(x);						//寻找 x的代表元
    y = find(y);						//寻找 y的代表元
    if(x == y) return false;			//如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并，返回 false，表示合并失败；否则，执行下面的逻辑
    if(rank[x] > rank[y]) pre[y]=x;		//如果 x的高度大于 y，则令 y的上级为 x
    else								//否则
    {
        if(rank[x]==rank[y]) rank[y]++;	//如果 x的高度和 y的高度相同，则令 y的高度加1
        pre[x]=y;						//让 x的上级为 y
	}
	return true;						//返回 true，表示合并成功
}

原文链接：https://blog.csdn.net/the_ZED/article/details/105126583

实现2：

#include <iostream>
#include <vector>
using namespace std;

class UnionFindSet
{
public:
    UnionFindSet(int n)
        : _ufs(n, -1)
    {
    }
    // 合并集合
    void Union(int x1, int x2)
    {
        int root1 = find_root(x1);
        int root2 = find_root(x2);
        if (root1 != root2)
        {
            // 改进：默认root1为大集合，判断root2是否大于root1
            if (abs(_ufs[root1]) < abs(_ufs[root2]))
                swap(root1, root2);
            // root2 -> root1
            _ufs[root1] += _ufs[root2];
            _ufs[root2] = root1;
        }
    }

    // 找集合的代表元素
    int find_root(int x)
    {
        int root = x;
        while (_ufs[root] >= 0)
        {
            root = _ufs[root];
        }
        // 改进：路径压缩
        while (_ufs[x] >= 0)
        {
            // 记录父亲节点
            int parent = _ufs[x];
            // 让该节点直接指向root
            _ufs[x] = root;
            x = parent;
        }
        return root;
    }

    // 是否在同一个集合中
    bool isinset(int x1, int x2)
    {
        return find_root(x1) == find_root(x2);
    }
    // 计算集合个数
    int setsize()
    {
        int size = 0;
        for (auto i : _ufs)
        {
            if (i < 0)
                size++;
        }
        return size;
    }

private:
    vector<int> _ufs;
};

最小生成树

prim算法

//prime算法
//将城市X标记为visit=true时，就表示该城市加入到集合U，用sum累加记录边的总费用

#include<iostream>
#define NO 99999999   //99999999代表两点之间不可达
#define N 5
using namespace std;

bool visit[N];
long long money[N] = { 0 };
long long graph[N][N] = {0};

void initgraph()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			scanf(" %lld", &graph[i][j]);
		}
	}
	
}

void printgraph()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			printf(" %lld", graph[i][j]);
		}
	}

}

int prim(int city)
{
	initgraph();
	printgraph();
	int index = city;
	int sum = 0;
	int i = 0;
	int j = 0;
	cout <<"访问节点：" <<index << "\n";
	memset(visit, false, sizeof(visit));
	visit[city] = true;
	for (i = 0; i < N; i++)
	{
		money[i] = graph[city][i];//初始化，每个与城市city间相连的费用存入money，以便后续比较
	}
		
	for (i = 1; i < N; i++)
	{
		int minor = NO;
		for (j = 0; j < N; j++)
		{
			if ((visit[j] == false) && money[j] < minor)  //找到未访问的城市中，与当前最小生成树中的城市间费用最小的城市
			{
				minor = money[j];
				index = j;
			}
		}
		visit[index] = true;
		cout << "访问节点：" << index << "\n";
		sum += minor; //求总的最低费用
		/*这里是一个更新，如果未访问城市与当前城市间的费用更低，就更新money,保存更低的费用*/
		for (j = 0; j < N; j++)
		{
			if ((visit[j] == false) && money[j]>graph[index][j])
			{
				money[j] = graph[index][j];
			}
		}
	}
	cout << endl;
	return sum;               //返回总费用最小值
}
int main()
{
	cout << "修路最低总费用为："<< prim(0) << endl;//从城市0开始
	return 0;
}

kruskal算法

//kruskal算法

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<vector>
using namespace std;
#define N 10005
#define M 50005
#define qm 100005
#define INF 2147483647
struct arr{
	int ff, tt, ww;
}c[M << 1];// 存储边的集合，ff，tt，ww为一条从ff连接到tt的权值为ww的边 
int tot = 0;//边的总数 
int ans = 0;//最小生成树的权值和 
int f[N];//并查集 
bool comp(const arr & a, const arr & b){
	return a.ww < b.ww;
}
int m, n;//边数量，点数量 
int getfa(int x){
	return f[x] == x ? x : f[x] = getfa(f[x]);
}//并查集，带路径压缩 
 
inline void add(int x, int y, int z){
	c[++tot].ff = x;
	c[tot].tt = y;
	c[tot].ww = z;
	return;
}//新增一条边 

void kruscal(){
	for (int i = 1; i <= n; i ++) f[i] = i;
	for (int i = 1; i <= m; i ++){
		int fx = getfa(c[i].ff);//寻找祖先 
		int fy = getfa(c[i].tt);
		if (fx != fy){//不在一个集合，合并加入一条边 
			f[fx] = fy;
			ans += c[i].ww;
		}
	}

	return;
} 
int main(){
	freopen("input10.txt", "r", stdin);
	freopen("output10.txt", "w", stdout);
	scanf("%d%d",&n, &m);
	int x, y, z;
	for (int i = 1; i <= m; i ++){
		scanf("%d %d %d", &x, &y, &z);
		add(x, y, z);
	}
	sort(c + 1, c + 1 + m, comp);//快速排序 
	kruscal();
	printf("%d\n", ans);
	return 0;
}

单调队列

const int N = 1000005;
int a[N];
deque<int> q;
int n, m;
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()];
	}
}

★STL

该部分有参考https://blog.csdn.net/weixin_49486457/article/details/123439229

随机访问迭代器容器：std::vector, std::deque, std::array, std::basic_string
双向迭代器容器：std::list, std::set, std::map, std::multiset, std::multimap

迭代器使用：

• std::prev() 注意越界问题，可用于vector,dequeue,list,map,set
• std::next() 注意越界问题，
• distance(vec.begin(), vec.end())

<vector>

#include<vector>
using namespace std;
	//初始化
    vector<int> a;			//定义一个vector，未初始化，输出》 0
    vector<int> a(3);		//定义一个长度为3的vector，未初始化，输出》0 0 0
    vector<int> a(10, 3); 	//定义一个长度为10，且每个数赋值为3
	vector<int> a(b.begin(),b.begin+3);	//将向量b中从下标0 1 2（共三个）的元素赋值给a，a的类型为int型
	//从数组中获得初值
	int b[7]={1,2,3,4,5,6,7};
	vector<int> a(b,b+7）;

    a.size()			//返回元素个数
    a.resize()			//改变大小，默认赋值，参数count,value
    a.reserve()			//预留空间，不改变其当前的大小
    a.empty();			//判断a是否为空，空则返回true，非空则返回false
    a.front(); if(!a.empty())	//返回a的第1个元素,当且仅当存在
    a.back(); if(!a.empty())	//返回vector的最后一个数
    a.clear();			//清空a中的元素
    a.pop_back();		//删除a向量的最后一个元素
    a.push_back(5);		//在a的最后一个向量后插入一个元素，其值为5
    a.emplace_back();

    for (int i = 0; i < 10; i ++) {a.push_back(i);}
    //三种遍历vector的方法
    for (int i = 0; i < a.size(); i ++) {cout << a[i] << ' '; }
    for (auto i = a.begin(); i != a.end(); i ++) {cout << *i << ' ';}
    for (auto x : a) {cout << x << ' ';}//C++11的新语法
   
    //结合算法erase() reverse()
    #include<algorithm> 
    a.erase(p)//从a中删除迭代器p指定的元素，p必须指向c中的一个真实元素，不能是最后一个元素end()
    a.erase(b,e)//从a中删除迭代器对b和e所表示的范围中的元素，返回e
    vector<int> a={1,2,3,4,5};
    reverse(a.begin(),a.end());//a的值为5，4，3，2，1  倒置
                  
    // vector 有重载=，可以直接比较两个vector是否一致              
    vector<int> sCount(26);
    vector<int> pCount(26);
    pCount[3] = 0;
    if (sCount == pCount) cout<<"1";
    
    // 重要：vector嵌套
    int m = 10;
    vector < string > s; 
    vector < vector < string > > hashmap ( m,s ) ;

<queue> <priority_queue>

#include <queue>
//queue <类型> 变量名  
//priority_queue <类型> 变量名;
queue <int> q; //定义一个名为q队列
priority_queue <int> q; //默认是大根堆
//定义小根堆
//小根堆：priority_queue <类型,vecotr <类型>,greater <类型>> 变量名
// priority_queue<int, vector<int>, greater<int>> heap;  

// queue & priority_queue
q.size();// 这个队列的长度
q.empty();//用于判断这个队列是否为空，空则返回true，非空则返回false
q.push(); //往队尾插入一个元素
q.pop(); //队列：把队头弹出  优先队列 ：弹出堆顶元素

// queue
q.front();// 返回队头元素
q.back(); //返回队尾元素

// priority_queue
q.top();// 返回堆顶元素

// clear
q = queue <int> ();

<deque>双端队列

#include <deque>
deque<int> dq;//定义一个int类型的双向队列

dq.size(); //返回这个双端队列的长度,unsigned int
dq.empty(); //返回这个队列是否为空，空则返回true，非空则返回false
dq.clear(); //清空这个双端队列
dq.front(); //返回第一个元素
dq.back(); //返回最后一个元素
dq.push_back(); //向最后插入一个元素
dq.pop_back(); //弹出最后一个元素
dq.push_front(); //向队首插入一个元素
dq.pop_front();//弹出第一个元素
dq.begin(); //双端队列的第0个数
dq.end(); //双端队列的最后一个的数的后面一个数

<stack>

include<stack>
stack<int> s;
s.size()	//返回这个栈的长度
s.push()	//向栈顶插入一个元素
s.top()		//返回栈顶元素
s.pop()		//弹出栈顶元素

<set>

set<string> s;//string 集合
size();// 返回元素个数
empty(); //返回set是否是空的
clear(); //清空
begin(); //第0个数，支持++或--，返回前驱和后继
end(); //最后一个的数的后面一个数，支持++或--，返回前驱和后继
insert(); //插入一个数
find(); //查找一个数
count(); //返回某一个数的个数
erase(x); //删除索引x  时间复杂度 O(k + logn)
erase(s.begin(),s.end());//删除一个迭代器

lower_bound(x); //返回大于等于x的最小的数的迭代器  核心操作
upper_bound(x); //返回大于x的最小的数的迭代器  不存在返回end()

<map>

会按照key的值自动排序

#include<map>
#include<unordered_map>
map<int, char> m;
m.find();
m.size();
m.insert({k, v});
m.erase(it);
m.erase(key);
m.clear();
m.count();// 可以代替find

lower_bound(x); //返回大于等于x的最小的数的迭代器
upper_bound(x); //返回大于x的最小的数的迭代器

// 映射操作
map<string,int>a;
a["abc"] = 1;//把字符串"abc" 映射为1
cout << a["abc"] << endl; //查找abc  程序输出 1

typedef pair<string,int> PSI;
map<string,int> mp;
mp.insert(make_pair("heihei",5));
mp.insert(PSI("haha",10));//简化

// 迭代器遍历
map<char,int> m;
for (auto x : m)
{
    cout << x.second << endl; 
}
map<char, int>::iterator it;
for (it = m.begin(); it != m.end(); it++)
{
    cout << it->first << " " << it->second << endl;
}

// find用法
map<int, char>::iterator it = m1.find(1);
if (it!= m1.end()) // 找到了，没找到会返回和end()一样的迭代器值
{
    cout << it->first << " " << it->second << endl;
}

使用map保存状态，使用移位操作进行状态标记
long long key = ((long long)i << 32) | jump<<1 | status;

<pair>

#include<utility>
pair<int, double> p3;  			// 使用默认构造函数
p3 = make_pair(1, 1.2);			// 利用make_pair赋值
vector< vector<pair<int, int> > >// 嵌套：与vector结合【再写个vector结合即可】

<string>

#include <string>
a.push_back('a');// 尾插一个字符
// insert(pos,char):在制定的位置pos前插入字符char
a.insert(a.begin(),'1'); //输出 1a
//插入字符串
string str2="hello";
string s2="weakhaha";
str2.insert(0,s2,1,3);
//将字符串s2从下标为1的e开始数3个字符，分别是eak，插入原串的下标为0的字符h前    
empty()//判断a是否为空，空则返回true，非空则返回false
size() length()
// 都是 返回字母个数
//!!注意他们的类型都是 注：std::string 的成员函数 length() 的返回值类型为 unsigned 类型，因此当 s.length() < t.length() 时，二者相减会得到一个很大的数产生运行时错误，所以相减之前需要先将二者强制类型转换为 int 类型。
clear() // 字符串清空

// substr
tring a = "ac";
    a += "w";//支持比较操作符>,>=,<,<=,==,!=
    cout << a << endl; //输出子串a :acw

    a += "ing";  
    cout << a << endl;
    //以字符串数组理解
    cout << a.substr(0, 3) << endl; //当第一个数是0 则后一位数:输出从头开始的长度为3的子串
    cout << a.substr(0, 3) << endl; //当第一个数是1 则输出下标为1 到下标为3的子串  
    cout << a.substr(0, 9) << endl;//如果超出长度范围 则输出原子串
    cout << a.substr(1) << endl; //从下标为1开始输出
    cout << a.substr(0) << endl; //原子串 

// c_str() 返回这个string对应的字符数组的头指针
string s = "Hello World!";
printf("%s", s.c_str()); //输出 "Hello World!"

<bitset>

#include<bitset>
bitset<4> bs;　　//无参构造，长度为４，默认每一位为０
bitset<8> b(12);　　//长度为８，二进制保存，前面用０补充
string s = "100101"; //01串赋值
bitset<10> bs(s);　　//长度为10，前面用０补充

// 支持操作
~取反，&与，|与或，^异或
>>，<<  移动
==，!=
[]   取0/1

// 常用函数    
count(); //返回1的个数
any(); //判断是否至少有一个1
none(); //判断是否全为0
set(); //把所有位置赋值为1
set(k,v); //将第k位变成v
reset(); //把所有位变成0
flip(); //把所有位取反，等价于~
flip(k); //把第k位取反

<algorithm>

#include<algorithm>

// 查找算法
find();			// 查找序列中第一个与给定值相等的元素的位置。
	auto it = std::find(vec.begin(), vec.end(), target);
find_if();		// 查找序列中第一个满足给定条件的元素的位置。
	auto it = std::find_if(vec.begin(), vec.end(), [](int i) { return i > 3; });
adjacent_find();// 查找序列中相邻的相同元素。
	auto pred = [](int a, int b) { return b == 2 * a; };
	auto pred = std::equal_to<int>();	// pred: 一个二元谓词，用于比较相邻元素，默认为 std::equal_to
	auto it = std::adjacent_find(vec.begin(), vec.end(), pred);
count();		// 计算序列中与给定值相等的元素的个数。
	int count = std::count(vec.begin(), vec.end(), 2);
count_if();		// 计算序列中满足给定条件的元素的个数。
	auto pred = [](int i) { return i % 2 == 0; };
	int count = std::count_if(vec.begin(), vec.end(), pred);
search();		// 查找序列中另一个序列的第一个出现的位置。
	auto it = std::search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
search_n();		// 查找序列中给定值出现的第一个位置，并返回该位置和下一个位置之间的所有元素。
	// 返回一个迭代器，指向找到子序列的起始位置。如果没有找到，则返回vec1.end()
	auto it = std::search_n(vec.begin(), vec.end(), count, value);	// 连续出现count个value
mismatch();		// 比较两个序列，并返回第一个不相等的元素的位置。
	auto result = std::mismatch(vec1.begin(), vec1.end(), vec2.begin(), pred);
equal();		// 比较两个序列是否相等。
	bool isEqual = std::equal(vec1.begin(), vec1.end(), vec2.begin(), pred);
is_sorted();	// 判断序列是否已经排序。
	bool isSorted = std::is_sorted(vec.begin(), vec.end())
binary_search();// 在排序后的序列中查找给定值的位置。
	bool is_found = std::binary_search(v.begin(), v.end(), target)
lower_bound();	// 返回第一个大于或等于给定值的元素的迭代器。
	auto lb = std::lower_bound(v.begin(), v.end(), 4);
upper_bound();	// 返回第一个大于给定值的元素的迭代器。
	auto ub = std::upper_bound(v.begin(), v.end(), 4);
equal_range();	// 返回包含给定值的两个迭代器，其 first 成员是指向第一个等于 value 的元素的迭代器，second 成员是指向第一个大于 value 的元素的迭代器。该函数适用于已排序的序列。
	auto range = std::equal_range(v.begin(), v.end(), 4);
	auto range_first = range.first;
	auto range_second = range.second;

// 排序操作
sort();					// 对序列进行排序。
	sort(a,a+5,cmp);//搭配数组  从小到大排序
	sort(b.begin(),b.end(),cmp);
	// 自定义sort函数（等同于cmp函数与运算符重载）
    sort(range, range + n, [&](Range a, Range b)
        {
            return a.r < b.r;
        });
stable_sort();			// 对序列进行稳定排序。
partial_sort();			// 对序列进行部分排序。
partial_sort_copy();	// 对序列进行部分排序，并将结果复制到另一个序列。
nth_element();			// 将序列的第 n 个元素放在正确的位置。
merge();				// 将两个有序序列合并为一个有序序列。
inplace_merge();		// 在原地将两个有序序列合并为一个有序序列。
sort_by_key();			// 根据键对序列进行排序。
stable_sort_by_key();	// 根据键对序列进行稳定排序。
sort_heap();			// 对堆进行排序。
make_heap();			// 将序列转换为堆。
pop_heap();				// 从堆中弹出顶部元素。
push_heap();			// 将元素插入到堆中。
    
// 修改算法
copy()：复制一个序列。
copy_if()：复制满足给定条件的序列元素。
replace()：将序列中指定的元素替换为另一个元素。
replace_if()：将序列中满足给定条件的元素替换为另一个元素。
fill()：将序列填充为指定值。
fill_n()：将序列的前 n 个元素填充为指定值。
transform()：将序列中的每个元素转换为另一个值。
generate()：将序列中的每个元素生成为一个指定函数的结果。
remove()：从序列中删除指定值的元素。
remove_if()：从序列中删除满足给定条件的元素。
unique()：删除序列中相邻重复的元素。
unique_copy()：将序列中相邻重复的元素复制到另一个序列。
swap()：交换两个序列。
reverse()：反转序列的顺序。
rotate()：将序列旋转指定的元素。
random_shuffle()：对序列进行随机排序。
shuffle()

// 聚合算法
accumulate()	// 对序列中的元素进行累加。
    	int sum = accumulate(arr.begin(), arr.end(), 0);
reduce()：对序列中的元素进行归约。
inner_product()：计算两个序列的点积。
adjacent_difference()：计算序列中相邻元素的差。
partial_sum()：计算序列中的部分和。
iota()：生成一个从 0 开始的序列。

// 迭代算法
for_each()：对序列中的每个元素执行一个指定的操作。
transform_reduce()：将序列中的元素转换为另一个值，并对结果进行归约。
for_each_n()：对序列的前 n 个元素执行一个指定的操作。
generate_n()：生成 n 个元素，并将它们插入到序列中

具体实现

merge();	//将两个有序序列合并为一个有序序列
// 二分查找 时间复杂度O(log n)
// binary_search
// binary_search 算法在 [first, last) 范围内执行二分查找，寻找是否存在值等于 val 的元素。如果找到目标元素，则返回 true；否则返回 false。
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val);
// lower_bound 返回第一个大于等于target的元素
// upper_bound 返回第一个大于target的元素
int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
int r = upper_bound(nums.begin(), nums.end(), target) - nums.begin();
// merge 归并两个有序序列
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());//合并v1和v2到v3
// 判断一序列是否为另一序列的子序列。返回真假
includes()
// 集合操作
    set_union()					// 并集
    set_intersection()			// 交集
    set_difference()			// 差集
    set_symmetric_difference()	// 对称差集（并-交）
    set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.begin()));
// 堆操作
    push_heap()
    pop_heap()
    make_heap()
    sort_heap()

// __gcd 最大公约数
int k=__gcd(n,m);//最大公约数
printf("%d ",k);
printf("%d", n * m / k); //最小公倍数

max(a,b);//返回最大值
min(a,b);//返回最小值
swap(a,b);//交换a和b

copy (v1.begin(),v1.end(),v2.begin());//v1复制给v2

// reverse
vector<int> v={1,2,3,4,5};
reverse(v.begin(),v.end());//v的值为5，4，3，2，1  倒置

// find
//在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，
//若存在返回其在向量中的位置
find(a.begin(),a.end(),10);
std::vector<std::string> myvector{ "www", "baidu", "com" };
auto it = find(myvector.begin(), myvector.end(), "com");
if (it != myvector.end())
        std::cout << "result: " << *it << std::endl;
    else
        std::cout << "no result." << std::endl;

// find
// 在容器或范围中查找相邻的重复元素，并返回指向第一对重复元素的迭代器
template <class ForwardIterator>
ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last);


// count
// count 算法用于计算范围 [first, last) 中值等于 val 的元素个数，并返回这个计数值。
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
  count (InputIterator first, InputIterator last, const T& val);
std::vector<int> numbers = {1, 2, 2, 3, 2, 4, 2, 5};

// 使用 count 统计值为 2 的元素个数
int numTwos = std::count(numbers.begin(), numbers.end(), 2);
std::cout << "值为 2 的元素出现次数为: " << numTwos << std::endl;


// erase
//从c中删除迭代器p指定的元素，p必须指向c中的一个真实元素，不能等于c.end()
c.erase(p)
//从c中删除迭代器对b和e所表示的范围中的元素，返回e
c.erase(b,e)
   
    
// 自定义比较
class Person
{
public:
    Person(std::string name, int age)
        : m_Name(name), m_Age(age) {}
 
    bool operator==(const Person & p) const // 注意此处要声明为 const
    {
        return this->m_Age == p.m_Age;
    }
 
    std::string m_Name;
    int m_Age;
};
 
void test02()
{
    std::vector<Person> v;
    v.push_back(Person("刘备", 35));
    v.push_back(Person("关羽", 35));
    v.push_back(Person("张飞", 35));
    v.push_back(Person("赵云", 30));
    v.push_back(Person("曹操", 25));
 
    Person p("诸葛亮", 35);
    int num = std::count(v.begin(), v.end(), p);
 
    std::cout << "年龄为 35 的人数为： " << num << std::endl;
}

前缀和 & 差分

▲一维前缀和

对于数组a[1], a[2], a[3], a[4], …… a[n]

前缀和数组 （即数列Sn）

a[0] = 0;
for (int i=1; i<=n; i++)
	s[i] = s[i-1] + a[i]

异或也有加的性质，也可以用于前缀和

▲二维前缀和

sum[i][j] = 
a[1][1]+a[1][2]+a[1][3]+…+a[1][j]
+a[2][1]+a[2][2]+a[2][3]+…+a[2][j]
+……
+a[i][1]+a[i][2]+a[i][3]+…+a[i][j]

计算公式：

sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]
子矩阵的和 = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] 

▲差分数组（d[k]=a[k]-a[k-1]）

即 a[k] = d[1]+d[2]+d[3]+……+d[k]

对[left,right]都加v，相当于

d[left] += v;

d[right + 1] -= v;

for (int i = 1; i <= m; i++)
    {
        int left, right;
        cin >> left >> right;
        d[left] += v;
        d[right + 1] -= v;
    }
还原
int additive = 0;
    for (int i = 1; i <= n; i++)
    {
        additive += d[i];
        query[i] = additive;
    }

https://www.lanqiao.cn/problems/2128/learning/

单调栈

二分

单调性？ 二段性？

int lower_bound(vector<int>& A, int target) {
    int left = 0, right = A.size();
    while(left < right) {
        int mid = left + ((right - left) >> 1);
        if(A[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}


int upper_bound(vector<int>& A, int target) {
    int left = 0, right = A.size();
    while(left < right) {
        int mid = left + ((right - left) >> 1);
        if(A[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left;
}

https://www.lanqiao.cn/problems/2145/learning/

快速幂

long long solve(long long a, long long b, long long p)
{
    long long ans = 1;
    long long base = a;
    while(b)
    {
        if (b & 0x1) 
        {
            ans *= base;
            ans %= p;
        }
        base *= base;
        base %= p;
        b >>= 1;
    }
    return ans;
}

越界

相乘结果输出1410065408，超越int界

贪心

▲不相交区间问题（或称为区间调度问题、活动安排问题）
  给定一些区间（活动），每个区间有左端点和右端点（开始时间和终止时间），要求找到最多的不相交区间（活动）。
  以下按“活动安排问题”来解释。
  这个问题的目的是求最多活动数量，所以那种持续时间长的活动不受欢迎，受欢迎的是尽快结束的、持续时间短的活动。
  考虑以下3种贪心策略：
  1）按最早开始时间贪心：先选最早开始的活动a，当a结束后，再选下一个最早开始的活动。这种策略不好，因为它没有考虑活动的持续时间。假如a一直不结束，那么其他活动就不能开始。
  2）最早结束时间：先选最早结束的活动a，a结束后，再选下一个最早结束的活动。这种策略是合理的。越早结束的活动，越能腾出后续时间容纳更多的活动。
  3）用时最少：先选时间最短的活动a，再选不冲突的下一个最短活动。这个策略似乎也可行，但是很容易找到反例，证明这个策略不正确。
  下图的例子，
  用“策略1）最早开始时间”，选3；
  用“策略2）最早结束时间”，选1、2、5、6；
  用“策略3）用时最少”，选4、1、2。
  策略2）的结果是最好的。
总结活动安排问题的贪心策略：先按活动的结束时间（区间右端点）排序，然后每次选结束最早的活动，并保证选择的活动不重叠。

▲区间合并问题

给定若干个区间，合并所有重叠的区间，并返回不重叠的区间个数。

贪心策略：按区间左端点排序，然后逐一枚举每个区间，合并相交的区间。
  定义不重叠的区间个数（答案）为ans。设当前正在合并的区间的最右端点为end，枚举到第i个区间[Li, Ri]时：
  若Li≤end，说明与第i区间相交，需要合并，ans不变，更新end = max(end, Ri)。
  若Li > end，说明与第i区间不相交，ans加1，更新 end = max(end, Ri)。区间覆盖问题

▲区间覆盖问题

给定一个目标大区间，和一些小区间，问最少选择多少小区间，可以覆盖大区间。
  贪心策略：尽量找出右端点更远的小区间。
  操作步骤：先对小区间的左端点排序，然后依次枚举每个小区间，在所有能覆盖当前目标区间右端点的区间之中，选择右端点最大的区间。

快速幂

//非递归快速幂
int qpow(int a, int n){
    int ans = 1;
    while(n){
        if(n&1) ans *= a;  //如果n的当前末位为1，ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

典型题目

C++面向对象补充

类

拷贝构造

// 拷贝构造函数
classname (const classname &obj) {
   // 构造函数的主体
}

友元

类的友元函数是定义在类外部，但有权访问类的所有私有（private）成员和保护（protected）成员。尽管友元函数的原型有在类的定义中出现过，但是友元函数并不是成员函数。

友元可以是一个函数，该函数被称为友元函数；友元也可以是一个类，该类被称为友元类，在这种情况下，整个类及其所有成员都是友元。

class Box
{
   double width;
public:
   double length;
   friend void printWidth( Box box );
   void setWidth( double wid );
};

继承

继承、基类、派生类、多继承

#include <iostream>
using namespace std;
// 基类 Shape
class Shape 
{
   public:
      void setWidth(int w){ width = w; }
      void setHeight(int h){ height = h; }
   protected:
      int width;
      int height;
};
 
// 基类 PaintCost
class PaintCost 
{
   public:
      int getCost(int area){ return area * 70; }
};
 
// 派生类
class Rectangle: public Shape, public PaintCost
{
   public:
      int getArea()
      { return (width * height); }
};
 
int main(void)
{
   Rectangle Rect;
   int area;
   Rect.setWidth(5);
   Rect.setHeight(7);
   area = Rect.getArea();
   // 输出对象的面积
   cout << "Total area: " << Rect.getArea() << endl;
   // 输出总花费
   cout << "Total paint cost: $" << Rect.getCost(area) << endl;
   return 0;
}
// ans
// Total area: 35
// Total paint cost: $2450

重载

函数重载

#include <iostream>
using namespace std;
class printData
{
   public:
      void print(int i) {
        cout << "整数为: " << i << endl;
      }
      void print(double  f) {
        cout << "浮点数为: " << f << endl;
      }
      void print(char c[]) {
        cout << "字符串为: " << c << endl;
      }
};
 
int main(void)
{
   printData pd;
   // 输出整数
   pd.print(5);
   // 输出浮点数
   pd.print(500.263);
   // 输出字符串
   char c[] = "Hello C++";
   pd.print(c);
   return 0;
}

一元运算符重载

#include <iostream>
using namespace std;
 
class Distance
{
   private:
      int feet;             // 0 到无穷
      int inches;           // 0 到 12
   public:
      // 所需的构造函数
      Distance(){
         feet = 0;
         inches = 0;
      }
      Distance(int f, int i){
         feet = f;
         inches = i;
      }
      // 显示距离的方法
      void displayDistance()
      {
         cout << "F: " << feet << " I:" << inches <<endl;
      }
      // 重载负运算符（ - ）
      Distance operator- ()  
      {
         feet = -feet;
         inches = -inches;
         return Distance(feet, inches);
      }
    // 重载小于运算符（ < ）
      bool operator <(const Distance& d)
      {
         if(feet < d.feet)
         {
            return true;
         }
         if(feet == d.feet && inches < d.inches)
         {
            return true;
         }
         return false;
      }
};

int main()
{
   Distance D1(11, 10), D2(-5, 11);
   -D1;                     // 取相反数
   D1.displayDistance();    // 距离 D1
   -D2;                     // 取相反数
   D2.displayDistance();    // 距离 D2
    
    if( D1 < D2 )
   {
      cout << "D1 is less than D2 " << endl;
   }
   else
   {
      cout << "D2 is less than D1 " << endl;
   }
   return 0;
}
// ans
// F: -11 I:-10
// F: 5 I:-11
// D2 is less than D1

二元运算符重载

类内： Box operator+(const Box&);

类外： Box operator+(const Box&, const Box&);

#include <iostream>
using namespace std;
class Box
{
   public:
      double getVolume(void)
      {
         return length * breadth * height;
      }
      void setLength( double len )
      {
          length = len;
      }
      void setBreadth( double bre )
      {
          breadth = bre;
      }
      void setHeight( double hei )
      {
          height = hei;
      }
      // 重载 + 运算符，用于把两个 Box 对象相加
      Box operator+(const Box& b)
      {
         Box box;
         box.length = this->length + b.length;
         box.breadth = this->breadth + b.breadth;
         box.height = this->height + b.height;
         return box;
      }
   private:
      double length;      // 长度
      double breadth;     // 宽度
      double height;      // 高度
};
// 程序的主函数
int main( )
{
   Box Box1;                // 声明 Box1，类型为 Box
   Box Box2;                // 声明 Box2，类型为 Box
   Box Box3;                // 声明 Box3，类型为 Box
   double volume = 0.0;     // 把体积存储在该变量中
   // Box1 详述
   Box1.setLength(6.0); 
   Box1.setBreadth(7.0); 
   Box1.setHeight(5.0);
   // Box2 详述
   Box2.setLength(12.0); 
   Box2.setBreadth(13.0); 
   Box2.setHeight(10.0);
   // Box1 的体积
   volume = Box1.getVolume();
   cout << "Volume of Box1 : " << volume <<endl;
   // Box2 的体积
   volume = Box2.getVolume();
   cout << "Volume of Box2 : " << volume <<endl;
   // 把两个对象相加，得到 Box3
   Box3 = Box1 + Box2;
   // Box3 的体积
   volume = Box3.getVolume();
   cout << "Volume of Box3 : " << volume <<endl;
   return 0;
}
// ans
// Volume of Box1 : 210
// Volume of Box2 : 1560
// Volume of Box3 : 5400

多态

每个子类都有一个函数 area() 的独立实现。这就是多态的一般使用方式。有了多态，您可以有多个不同的类，都带有同一个名称但具有不同实现的函数，函数的参数甚至可以是相同的。

纯虚函数：

您可能想要在基类中定义虚函数，以便在派生类中重新定义该函数更好地适用于对象，但是您在基类中又不能对虚函数给出有意义的实现，这个时候就会用到纯虚函数。

= 0 告诉编译器，函数没有主体，上面的虚函数是纯虚函数。

#include <iostream> 
using namespace std;
 
// 修改之前的
class Shape {
   protected:
      int width, height;
   public:
      Shape( int a=0, int b=0)
      {
         width = a;
         height = b;
      }
      int area()
      {
         cout << "Parent class area :" <<endl;
         return 0;
      }
};
// 修改过后的
class Shape {
   protected:
      int width, height;
   public:
      Shape( int a=0, int b=0)
      {
         width = a;
         height = b;
      }
      virtual int area()
      {
         cout << "Parent class area :" <<endl;
         return 0;
      }
};
// 纯虚函数
class Shape {
   protected:
      int width, height;
   public:
      Shape( int a=0, int b=0)
      {
         width = a;
         height = b;
      }
      // pure virtual function
      virtual int area() = 0;
};

class Rectangle: public Shape{
   public:
      Rectangle( int a=0, int b=0):Shape(a, b) { }
      int area ()
      { 
         cout << "Rectangle class area :" <<endl;
         return (width * height); 
      }
};
class Triangle: public Shape{
   public:
      Triangle( int a=0, int b=0):Shape(a, b) { }
      int area ()
      { 
         cout << "Triangle class area :" <<endl;
         return (width * height / 2); 
      }
};
// 程序的主函数
int main( )
{
   Shape *shape;
   Rectangle rec(10,7);
   Triangle  tri(10,5);
 
   // 存储矩形的地址
   shape = &rec;
   // 调用矩形的求面积函数 area
   shape->area();
 
   // 存储三角形的地址
   shape = &tri;
   // 调用三角形的求面积函数 area
   shape->area();
   
   return 0;
}
// 修改之前的ans
// Parent class area :
// Parent class area :
// 修改之后的ans
// Rectangle class area :
// Triangle class area :

高精度板子

plus

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+5,INF=0x3f3f3f3f;
 
int main()
{
    vector<int> a;vector<int> b,c;
    string f,g;
    cin>>f>>g;
    for(int i=f.size()-1;i>=0;--i)
    {
        int x=f[i]-'0';
        a.push_back(x);
    }
    for(int i=g.size()-1;i>=0;--i)
    {
        int x=g[i]-'0';
        b.push_back(x);
    }
    int n=max(a.size(),b.size());
    int t=0;
     for(int i=0;i<a.size()||i<b.size();++i)
     {
         if(i<a.size())t+=a[i];
         if(i<b.size())t+=b[i];
         c.push_back(t%10);
         t=t/10;
     }
     if(t!=0)
     {
         c.push_back(1);
        n++;
     }
    for(int i=n-1;i>=0;--i)
    {
        cout<<c[i];
    }
    return 0;
}

minus

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include <limits.h>
using namespace std;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
bool cmp(vector<int> n, vector<int>m)
{
	if (n.size() != m.size())return n.size() > m.size();
	for (int i = n.size() - 1; i >= 0; --i)
		if (n[i] != m[i])return n[i] > m[i];
	return true;
}
vector<int> sub(vector<int>& a, vector<int>& b) {
	vector<int>c; int t = 0;
	for (int i = 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;
}
int main()
{
	vector<int> a, b, C;
	string A, B;
	cin >> A >> B;
	for (int i = A.size() - 1; i >= 0; --i) {
		a.push_back(A[i] - '0');
	}
	for (int i = B.size() - 1; i >= 0; --i)b.push_back(B[i] - '0');
	if (cmp(a, b))
		C = sub(a, b);
	else {
		C = sub(b, a);
		printf("-");
	}
	for (int i = C.size() - 1; i >= 0; --i) {
		cout << C[i];
	}
 
	return 0;
}

multiply

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include <limits.h>
using namespace std;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
vector<int> cheng(vector<int>& A, int& B) {
	vector<int>c; long long 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 = t / 10;
	}
 
	return c;
}
int main()
{
	vector<int> a;
	string A;
	int b;
	cin >> A >> b;
	if (b == 0)
	{
		cout << '0';
		return 0;
	}
	for (int i = A.size() - 1; i >= 0; --i) {
		a.push_back(A[i] - '0');
	}
    
	auto c = cheng(a, b);
	for (int i = c.size() - 1; i >= 0; --i) {
		cout << c[i];
	}
 
	return 0;
}

div

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include <limits.h>
using namespace std;
const int N=1e5+5,INF=0x3f3f3f3f;int t=0;
vector<int> cu(vector<int>&A,int&B){
    vector<int>c;
    for(int i=A.size()-1;i>=0;--i)
    {
        t=A[i]+t*10;
        c.push_back(t/B);
        t=t%B;
    }
    reverse(c.begin(),c.end());
    while(c.size()>1&&c.back()==0)c.pop_back();
    return c;
}
int main()
{
    vector<int> a;
    string A;int b;
    cin>>A>>b;
    for(int i=A.size()-1;i>=0;--i){
        a.push_back(A[i]-'0');
    }
    auto c=cu(a,b);
    for(int i=c.size()-1;i>=0;--i){
        cout<<c[i];
    }
    cout<<"\n"<<t;
    return 0;
}