本文最后更新于 80 天前，其中的信息可能已经有所发展或是发生改变。
一些不太理解的玩意：
1、
“>>=”右移后赋值运算符，‘<<=“左移后赋值运算符
参考 256 128 64 32 16 8 4 2 1
x>>=n 即x*(1/2^n)
x<<=n 即x*(2^n)
2、
1、加速流奇淫巧技：
一、
read（）快读： 读入大量数据时比 scanf 快
// 快速读入，加快读入速度
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main()
{
int t;
while(t=read()) //0进不入循环 会结束，但可以读0
cout<<t<<endl;
}
二、
输入输出 cin cout 加速： 但速度上 scanf, printf 还是略胜一筹，字符串输入输出时，gets()和puts()更快
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
return 0;
}注意事项：
1、不适用于混合输入输出：
如果你的程序在输入输出中同时使用了C++的输入输出流和C标准库的输入输出函数（如scanf和printf），则不应该使用这段代码。因为这会导致输入输出之间的不同步。
2、不能混用输入输出函数：
在使用了这段代码后，应避免使用C标准库的输入输出函数（如printf和scanf），因为这些函数与输入输出流的同步已被关闭。简单来说，关闭了同步流，就不能用scanf和printf。
3、不影响程序正确性：
关闭输入输出流的同步不会影响程序的正确性，它只是为了提高程序的执行效率。因此，在一些对输入输出性能要求较高的场景下，可以考虑使用这段代码。
4、关闭了同步流（也就是使用这段代码），不能再用cout<<endl，而应该改用cout<<‘\n’。
因为通常情况下，cout<<endl会输出一个换行符并刷新输出缓冲区，确保内容立即显示。但是，当使用了上述代码时，cout<<endl不再具有自动刷新缓冲区的功能。
三、
bitset：
1个字节 byte 8个 bit能分别存储8位的0/1
随机访问时，bitset更快；连续访问时，bool更快。
例
bitset<1000001>a;
a.reset();
常用基本操作：
a.set(): 将整个 bitset 设置成 true 。 b.set(pos，val=true): 将某一位设置成 true/false。 a.reset(): 将整个 bitset 设置成 false 。 b.reset(pos): 将某-位设置成 false。相当于 set(pos，false)。 a. flip(): 翻转每一位。(0↔1，相当于异或一个全是1的 bitset ) b.flip(pos): 翻转某一位。
count(): 返回 true 的数量。 size(): 返回 bitset 的大小。 test(pos): 它和 vector 中的 at()的作用是一样的，和[]运算符的区别就是越界检查, any(): 若存在某一位是 true 则返回 true ，否则返回 false 。 none(): 若所有位都是 false 则返回 true，否则返回 false 。 all(): C++11，若所有位都是 true 则返回 true，否则返回 false 。
四、
多维数组和多个数组：
多维数组：O(n)
多个数组：O(m*n)
例如二维和一维，二维数组使用方便，但效率不及使用多个一维数组。
五、
加类型局部变量的声明甚至会比不加的更慢
不加声明：auto 加声明：int,string,queue<pair<int,int>>……
在auto出现之前，
C++需要先推导等号右侧表达式的类型，
然后检查它与变量的类型是否可以转换（例如兼容转换、向下类型转换和自定义类型转换）。
在auto出现之后，
C++在推导出等号右侧表达式的类型之后，
直接指定给变量。
检查的过程变成了指定的过程，时间上可以认为差别不大。
转自：在C++11中，auto关键字的大量使用，会影响编译速度吗？
六、
empty()还是size()？
为何empty()比较好？ 主要是他们之间的效率有一定差距：
empty对任意的容器都是常数时间 对于有点list实现，size需要线性时间
转自：C++学习——empty()还是size()_size和empty那个快-CSDN博客
2、字符串：
string → int：
<1> 十进制算术运算
string s = "123";
int num = 0;
for (int i=0; i<s.size(); ++i)
{
num = 10 * num + (s[i] - '0');
}<2> 使用标准库中的 atoi 函数 （Ascii to integer）
string s = "123";
int num = atoi(s.c_str());
int → string：
<1>
int num = 123;
string s = to_string(num);
判断字符串长度：
size_t strlen(const char *str);
字符串逆序：
reverse(str.begin(), str.end());
拼接：
append函数
int main()
{
string str;
string str2 = "Writing ";
string str3 = "print 10 and then 5 more";
// used in the same order as described above:
str.append(str2); // "Writing "
str.append(str3, 6, 3); // "10 "
str.append(str3, 5); // "10 and then 5 more"
str.append("dots are cool", 5); // "dots "
str.append("here: "); // "here: "
str.append(10, '.'); // ".........."
str.append(str3.begin() + 8, str3.end()); // " and then 5 more"
cout << str << '\n';
return 0;
}正向查找find函数
s.find（str，pos）
string中find()返回值是字母在母串中的下标位置。 如果没有找到，那么会返回一个特别的标记npos，一般写作string::npos。
string s, c;
int main() {
s = "apple";
c = "l";
int index = s.find(c);
if (index != string::npos)
cout << index << endl;
} // 输出为3s.find（str，pos）
find(str,pos)是用来寻找从pos开始(包括pos处字符)匹配str的位置。
string s, c;
int main() {
s = "laaaal";
c = "l";
int index = s.find(c,3); //从字符串s下标3的位置开始寻找
if (index != string::npos)
cout << index << endl;
} // 输出为5s.find_first_of（str） 和 s.find_last_of（str）
string s, c;
int main() {
s = "laaaal";
c = "l";
cout << "first index:" << s.find_first_of(c) << endl;
cout << "last index:" << s.find_last_of(c) << endl;
}
/*
输出：
first index:0
last index:5
*/查找目标字符串在字符串出现的总次数
int main()
{
int n = 0, sum = 0;
string s1("qwertyqwertyqwerty");
string s2("ert");
string temp = s1;
while (1)
{ //循环：查找到子串就把子串删去
n = temp.find(s2); //返回子串的位置
if (n != -1)
{ //n=-1表示未找到子串
temp = temp.substr(n + s2.length(), temp.length() - s2.length()); //开一个新的字符串变量temp存储删去子串后的字符串
sum++; //出现次数
}
else break;
}
cout << sum;
} // 输出为3逆向查找rfind函数：
s.rfind(str)
从字符串右侧开始匹配str，并返回在字符串中的下标位置
string s = "apple";
cout << s.rfind("l") << endl;
// 输出为3rfind(str，pos)
从pos开始，向前查找符合条件的字符串
strsub函数：
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s="sfsa";
string a=s.substr(0,3);
string b=s.substr();
string c=s.substr(2,3);
cout<<a<<endl;
cout<<b<<endl;
cout<<c<<endl;
return 0;
}
/*
输出：
sfs
sfsa
sa
*/
3、求素数埃氏筛、线性筛：
素数：只能被常数1或自己整除，不能被其他整数整除的正整数。
合数：在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。
埃氏筛：
埃氏筛核心：从2开始删去素数本身倍数，向后找到的第一个数字一定是素数。
const unsigned long long N = 1e9 + 10;
int n, i, j, k = 0;
bitset<N> a;
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); /*输入输出加速*/
a.reset(); /*初始化bitset全为0*/
cin >> n;
for (i = 2; i <= n; i++)
{
if (a[i] == 0)
{
for (j = 2; i * j <= n; j++)
{
a[i * j] = 1;
}
k++; /*计算素食个数*/
cout << i << '\n'; /*输出素数*/
}
}
cout << k; /*输出素数总个数*/
return 0;
}
线性筛：
在实现形式上，埃氏筛是直接用素数遍乘自然数删去自身倍数；
线性筛是先建立一个素数数列，然后用每个自然数遍乘数列中的素数删去素数倍数。
算法简述：
s1：建立标记数列（从2到n的自然数）和素数数列；
s2：第一个数字是2（看标记是素数），把素数2放进素数数列，标记2×2为非素数；
s3：第二个数字是3（看标记是素数），把素数3放入素数数列，标记3×2、3×3为非素数；
s4：第三个数字是4（看标记是合数），标记4×2为非素数，break；
s5：第四个数字是5（看标记是素数），把素数5放入素数数列，标记5×2、5×3、5×5为非素数；
s6：第五个数字是6（看标记是合数），标记6×2为非素数，break；
s7：第六个数字是7（看标记是素数），把素数7放入素数数列，标记7×2、7×3、7×5、7×7为非素数；
……
const unsigned long long N = 1e8, M = 5e8;
int p[M];
bitset<N> a;
int n, i, j, k = 0;
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); //输入输出加速
cin >> n;
a.reset(); /*初始化bitset全为0*/
for (i = 2; i <= n; i++)
{
if (a[i] == 0)
{
p[++k] = i;
cout << i << '\n'; /*输出素数*/
}
for (j = 1; i * p[j] <= n; j++)
{
a[i * p[j]] = 1;
if (i % p[j] == 0)
break;
}
}
cout << k; /*输出素数总个数*/
return 0;
}
4、年份日期：
闰年判定：
闰年：年份能够被4整除但不能被100整除或者能被400整除的为闰年。
bool isryear(int n){
return n%400==0||(n%4==0&&n%100!=0);
}
月份天数：
//也可以将数组第一个位置空出来，即填上一个随意的值，这样就可以将月份和数组下标对应了，方便访问
int pmonths[]={31,28,31,30,31,30,31,31,30,31,30,31}; //平年每月天数
int rmonths[]={31,29,31,30,31,30,31,31,30,31,30,31}; //闰年每年天数
5、二分：
整数二分：
// 整数二分模板：
bool check(int mid)
{
//...;
}
// 查找满足条件的最小值(第一次出现的值)
int binarySearch1(int l, int r)
{
int l, r;
//l = 1, r = n;
int mid = l + r >> 1;
while (l < r)
{
if (check(mid)) /* a[mid] >= x */
r = mid;
else
l = mid + 1;
}
return l;
}
// 查找满足条件的最大值(最后一次出现的值)
int binarySearch2(int l, int r)
{
int l, r;
//l = 1, r = n;
int mid = l + r + 1 >> 1;
while (l < r)
{
if (check(mid)) /* a[mid] <= x */
l = mid;
else
r = mid - 1;
}
return l;
}例题：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int q[N], n, m;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> q[i];
while (m--)
{
int x;
cin >> x;
int l = 1, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (q[mid] >= x)
r = mid;
else
l = mid + 1;
}
if (q[l] != x)
cout << -1 << " ";
else
cout << l << " ";
}
return 0;
}
浮点二分：
bool check(double x)
{/* ... */} // 检查x是否满足某种性质
double binarySearch3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度， 假如要精确至小数点后三位，则差值要求小于1e-5，以此类推......
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid;
}
return l;
}例题：
有一个整数x，试求出√x，保留两位小数
#include<bits/stdc++.h>
using namespace std;
int main()
{
double x;
cin >> x;
double l = 0, r = x;
while (r - l > 1e-4)
{
double mid = (l + r) / 2;
if (mid * mid > x)
r = mid;
else
l = mid;
}
cout << setprecision(2) << fixed << l << endl;
return 0;
}
关于lower_bound()和upper_bound()的常见用法：
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。
在从小到大的排序数组中，
lower_bound( begin,end,num)：
从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num)：
从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
在从大到小的排序数组中，重载lower_bound()和upper_bound()
lower_bound( begin,end,num,greater<type>() ):
从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num,greater<type>() ):
从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
6、排序：
一般直接用sort，sort省事且基本和下面算法速度差不多
快速排序：
模板：
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
归并排序：
模板：
const int N = 1e5 + 10;
int q[N], tmp[N], n;
void merge_sort(int q[], int l, int r)
{
if (l >= r)
return;
int mid = (l + r) >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (q[i] <= q[j])
tmp[k++] = q[i++];
else
tmp[k++] = q[j++];
}
while (i <= mid)
tmp[k++] = q[i++];
while (j <= r)
tmp[k++] = q[j++];
for (i = l, j = 0; i <= r; i++, j++)
q[i] = tmp[j];
}
7、高精度加减乘除算法：
高精度加法：
//加法
vector<int> add(vector<int> &A, vector<int> &B)
{
vector<int>C; //存放结果
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 /= 10; //更新进位
}
if (t)
C.push_back(1);
return C;
}
int main()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i--) //逆序是为了便于从个位开始处理
A.push_back(a[i] - '0'); //字符转换为数值
for (int j = b.size() - 1; j >= 0; j--)
B.push_back(b[j] - '0'); //字符转换为数值
auto C = add(A, B);
for (int i = C.size() - 1; i >= 0; i--)
cout << C[i];
return 0;
}
高精度减法：
//减法
bool cmp(vector<int> &A, vector<int> &B)
{
if (A.size() != B.size())
return A.size() > B.size();
for (int i = 0; i < A.size(); i++)
if (A[i] != B[i])
return A[i] > B[i];
return true;
}
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i++)
{
t = t - A[i];
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()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i--)
A.push_back(a[i] - '0');
for (int j = b.size() - 1; j >= 0; j--)
B.push_back(b[j] - '0');
vector<int> C;
if (cmp(A, B)) //判断A,B大小
{
C = sub(A, B);
}
else
{
C = sub(B,A);
cout << "-"; //相减为负数，要加负号
}
for (int i = C.size() - 1; i >= 0; i--)
cout << C[i];
return 0;
}高精度乘法：
// 高精 * 低精
vector<int> mul(vector<int> &A, int &b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i++)
{
t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (t)
{
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0)
C.pop_back();
return C;
}
//高精度 * 高精度
vector<int> mul(vector<int>& A, vector<int>& B)
{
vector<int> C(A.size() + B.size() + 7, 0); // 初始化为 0，C的size可以大一点
for (int i = 0; i < A.size(); i++)
for (int j = 0; j < B.size(); j++)
C[i + j] += A[i] * B[j];
int t = 0;
for (int i = 0; i < C.size(); i++)
{ // i = C.size() - 1时 t 一定小于 10
t += C[i];
C[i] = t % 10;
t /= 10;
}
while (C.size() > 1 && C.back() == 0)
C.pop_back(); // 必须要去前导 0，因为最高位很可能是 0
return C;
}
高精度除法：
// 高精度 ÷ 低精度
vector<int> div(vector<int>& A, int& b, int& r)
{
vector<int>C;
r = 0;
for (int i = A.size() - 1; i >= 0; i--)
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.back() == 0 && C.size() > 1)
C.pop_back();
return C;
}
// 高精度 ÷ 高精度
bool cmp(vector<int>& A, vector<int>& B)
{
if (A.size() != B.size())
return A.size() > B.size();
for (int i = A.size() - 1; i >= 0; i--)
{
if (A[i] != B[i])
return A[i] > B[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() || t; 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;
}
vector<int> div(vector<int>& A, vector<int>& B, vector<int>& r)
{
vector<int> C;
if (!cmp(A, B))
{
C.push_back(0);
r = A;
return C;
}
int j = B.size();
r.assign(A.end() - j, A.end());
while (j <= A.size())
{
int k = 0;
while (cmp(r, B))
{
vector<int> s = sub(r, B);
r.clear();
r.assign(s.begin(), s.end());
k++;
}
C.push_back(k);
if (j < A.size())
r.insert(r.begin(), A[A.size() - j - 1]);
if (r.size() > 1 && r.back() == 0)
r.pop_back();
j++;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0)
C.pop_back();
return C;
}
int main()
{
string a, b;
cin >> a >> b;
vector<int> A, B, r;
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');
auto C = div(A, B, r);
for (int i = C.size() - 1; i >= 0; i--)
printf("%d", C[i]);
printf("\n");
for (int i = r.size() - 1; i >= 0; i--)
printf("%d", r[i]);
return 0;
}
8、前缀和：
一维前缀和：
// 一维前缀和模板
const long long N = 1e5 + 10;
long long n, m, a[N], sum[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
while (m--)
{
long long l, r;
cin >> l >> r;
cout << sum[r] - sum[l - 1] << endl;
}
return 0;
}
二维前缀和：
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
// S[i, j] = 第i行j列格子左上部分所有元素的和
// 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
模板：
const int N = 1e3 + 10;
int n, m, q, a[N][N], sum[N][N];
int main()
{
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
}
while (q--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] << endl;
}
return 0;
}
9、尺取法（双指针）：
反向扫描：
模板：
// 用 while 实现
int i = 0, j = n - 1;
while (i < j)
{
...
i++;
j--;
}
// 用 for 实现
for (int i =, j = n - 1; i < j; i++, j--)
{
...
}
同向扫描（快慢指针）：
1、寻找区间和（尺取法产生滑动窗口）
例：给定一个长度为 n 的数组 a[ ] 和一个数 s ，在这个数组中寻找一个区间，使这个区间的数组元素之和等于 s 。输出区间的起点和终点位置。
说明：输入样例的第1行是 n ，第2行是数组 a[ ] ，第3行是区间和 s 。输出样例换行分开每种情况。
const int N = 1e5 + 10;
int a[N];
void find(int q[], int n, int s)
{
int i = 0, j = 0, sum = q[0];
while (j < n) // 下面代码中保证 i <= j
{
if (sum >= s)
{
if (sum == s)
cout << i << " " << j << endl;
sum -= q[i];
i++;
if (i > j) // 防止 i 超过 j
{
sum = q[i];
j++;
}
}
if(sum < s)
{
j++;
sum += q[j];
}
}
}
int main()
{
int n, s;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
cin >> s;
find(a, n, s);
return 0;
}2、数组去重：哈希和尺取法
3、多指针：
const int N = 2e5 + 10;
int a[N], n, c;
int main()
{
cin >> n >> c;
for (int i = 1; i <= n; i++)
cin >> a[i];
long long ans = 0;
sort(a + 1, a + 1 + n);
for (int i = 1, j = 1, k = 1; i <= n; i++) // 三指针
{
while (j <= n && a[j] - a[i] < c)
j++;
while (k <= n && a[k] - a[i] <= c)
k++;
if (a[j] - a[i] == c && a[k - 1] - a[i] == c && k >= 2)
ans += k - j;
}
cout << ans;
return 0;
}
10、快速幂：
模板：
// 递归快速幂：
typedef long long ll;
ll fastPow(ll a, ll n, ll m) // (a^n) mod m
{
if (n == 0) // 特判 a = 0, a = 1
return 1;
if (n == 1)
return a;
ll temp = fastPow(a, n >> 1, m); // 分治
if (n & 1)
return (temp * temp % m * a % m) % m; // 奇数个 a(不这么写会爆 long long)
else
return temp * temp % m; // 偶数个 a
}
// 非递归快速幂：
ll fastPow(ll a, ll n, ll m)
{
ll temp = 1;
while(n)
{
if(n & 1) // 如果 n 为奇数
temp *= a; // ans 乘上当前的 a
a *= a; // a 自乘
n >>= 1; // n 除以 2
}
return temp % m;
}
int main()
{
ll a, n, m;
cin >> a >> n >> m;
cout << fastPow(a, n, m);
return 0;
}
11、DFS（深搜）和BFS（宽搜）：
DFS（暴搜）搜索路径：
BFS搜索路径及两者比较：
DFS：
dfs在每次回溯时都要“恢复现场”，同时可以根据题目要求，每走一步判断是否满足条件，以此来减少搜索的数据量（剪枝）
DFS，n皇后问题：
AcWing 843. n-皇后问题 —— 主副斜线的“秘密”
11、最大公约数(GCD)（辗转相除法）、最小公倍数(LCM)：
求最大公约数方法：
最大公约数：
int gcd(int m, int n)
{
return n ? gcd(n, m % n) : m;
}
两个数的乘积等于这两个数的最大公约数与最小公倍数的乘积。
即：假设x和y的最大公约数是m,最小公倍数是n,则xy=mn.
12、动态规划：
······背包问题：
原题链接：0/1背包问题
// 朴素做法：
/*
情况一：
第 i 个物品的体积比容量 j 还大，不能装进容量 j 的背包
那么直接继承前 i-1 个物品装进容量 j 的背包的情况即可： 即 dp[i][j] = dp[i-1][j];
情况二：
第 i 个物品的体积比容量 j 还小，能装进背包，又可以分两种情况：装/不装第 i 个物品。
① 装第 i 个物品。
从前 i-1 个物品的情况推广而来，前 i-1 个物品的价值为 dp[i-1][j]。
第 i 个物品装进背包后，背包容量减少 c[i]，价值增加 w[i]，有 dp[i][j] = dp[i-1][j-c[i]] + w[i]。
② 不装第 i 个物品，有 dp[i][j] = dp[i-1][j]；
取两种情况最大值，状态转移方程为：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]] + w[i])
*/
const int N = 1010;
int dp[N][N];
int v[N], w[N];
int n, m;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= v[i])
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
cout << dp[n][m] << '\n';
}可以优化吗？答案是肯定的：
优化版（交替滚动）：
int dp[2][N]; // 替换 int dp[][]；
int solve(int n ,int m)
{
int now = 0, old = 1; // now指向当前正在计算的一行，old指向旧的一行
for (int i = 1; i <= n; i++)
{
swap(old, now); // 交替滚动，now始终指向最新的一行
for (int j = 0; j <= m; j++) // j 循环反过来也行
{
if (v[i] > j)
dp[now][j] = dp[old][j];
else
dp[now][j] = max(dp[old][j], dp[old][j - v[i]] + w[i]);
}
}
return dp[now][m]; // 返回最新的一行
}进一步优化，只用一维数组（自我滚动）：0/1背包优化问题
int solve(int n,int m)
{
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= v[i]; j--) // j 循环只能反过来循环
{
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
return dp[m];
}//多重背包问题
/*
二进制优化（下方举例说明）：
① 假定物品件数 s = 200
② 二进制形式 k[n] = {1,2,4,8,16,32,64,73} 其所有值相加是 <=200 可以凑出[0~200]的所有数
③ 除开最后一个数不是二进制形式，73 = 200-(1+2+4+8+16+31+64)
④ 其余数，若定 64，其中 64+[0~63]->[0~127]
⑤ 最后一个数 73，其中 73+[0~127]->[0~200]
*/
const int N = 11010, M = 2010; // 此处1000 * log2000 , 向上取整数 N 得11000
int n, m; // n 表示物品总数，m 表示背包容积
int v[N], w[N]; // v[i] 表示第i件物品的体积，w[i] 表示第 i 件物品的价值
int dp[M]; // 组合方案中的最大价值
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
int cnt = 0; // 用来存储所有新的物品
for (int i = 1; i <= n; i++)
{
int a, b, s;
cin >> a >> b >> s; // 输入当前物品的体积，价值，个数
int k = 1; // 此处二进制优化，从 1 开始分（假定选择当前物品的总数为 k ）
for(int k = 1; k <= s; k <<= 1) // 二进制，乘以 2 继续循环
{
v[++cnt] = a * k; // 编号增加，体积 * 物品总数
w[cnt] = b * k;
s -= k; // 从总个数 s 中减去 k 个
}
if (s > 0) // 若总个数 s 还有剩余
{
v[++cnt] = a * s; // 编号增加，体积 * 剩余个数
w[cnt] = b * s;
}
}
n = cnt; // 将 n 更新为 cnt
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
// 此处优化成一维，次数使用倒序，因为原 dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]*k]+w[i]*k)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]); // 其中 v[i] 和 w[i] 已经是选定个数 k 后更新的体积和价值
cout << dp[m] << '\n';
return 0;
}这里采用的优化思维主要是任意一个数都可以利用二进制拆分组合，比如 10=1+2+4+3，7=1+2+4
可能你会想，既然按照这样的数目把原来的物品重新打包，那会不会有遗漏的情况，但其实并不会。
以 7 = 1+2+4 为例，1,2,4 各自的取与不取，已经覆盖了 0~7 的所有情况。
1 2 4 全选是7 1不选是6 2不选是5 只选4 4不选是3 只选2 只选1 全部选 全部不选
确实挺神奇的，这样一来假如原本朴素版需要计算的次数是 2500次的话 ，就压到了 2500 -（1 + 2 + … + 1024）+ 10 ≈ 500次，
数字越大优化就越明显
13、链表：
单链表：
数组模拟单向链表（静态链表）：e[N]代表数组存储的value值，ne[N]代表该结点的下一位指针；
运用：
#include <iostream>
using namespace std;
const int N = 100010;
// 表示头结点的下标
// e[i]表示结点i的值
// ne[i]表示结点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1; // 初始化链表，-1表示空集
idx = 0;
}
// 将x插入到头结点
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
// 将x插入到下标是k的点后面
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
// 将下标是k的点后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
``````
return 0;
}
双链表：
数组模拟双向链表（静态链表）：
#include <iostream>
using namespace std;
const int N = 100010;
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
// 0表示左端点，1表示右端点
l[0] = 1, l[1] = 0;
idx = 2;
}
// 在下标是k的点的右边，插入x
void add(int k, int x)
{
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
}
// 删除第k个点
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main()
{
``````
return 0;
}
14、递归：
编写递归函数，将组成整数的所有数字逐个输出，每个数字后面加上一个减号”-“，例如对于整数123，该函数将输出1-2-3-。编写主函数测试该递归函数。
样例输入：
123
样例输出：
1-2-3-
void f(int n)
{
if (n == 0)
return;
f(n / 10); //举例输入123，则压栈顺序为123,12,3
cout<<n%10<<'-'; //出栈顺序就为1-2-3-
}
int main()
{
int n;
cin >> n;
f(n);
return 0;
}问题描述：
FJ在沙盘上写了这样一些字符串: A1 =“A” A2 =“ABA” A3 =“ABACABA” A4 =“ABACABADABACABA”
输入编号，输出对应字符串
string f(int n)
{
if (n == 1)
return "A";
else
return f(n - 1) + (char)('A' + n - 1) + f(n - 1);
}
int main()
{
int n; cin >> n;
cout << f(n) << endl;
return 0;
}
15、进制转换
十进制转X进制：
void Binary(int n)
{
short t = 0;
if(n != 0)
{
t = n % X;
n = n / X;
Binary(n);
cout<<("%d",t);
}
}