排序
快速排序
思路：快速排序是在未排序数组中找一个基准（最左边的数），将所有比基准数小的数放在基准数左边，大的数放在基准数右边。最后在基准数左边用同样的方法，右边用同样的方法直到为顺序集合
代码
void quick_sort(int l, int r)//快速排序
{
if (l >= r)
return;
int rnd_idx = rand() % (r - l + 1) + l;
int i = l - 1, j = r + 1, x = nums[rnd_idx];//随机取一个中间值
while (i < j)
{
do
i++;
while (x > nums[i]);
do
{
j--;
} while (x < nums[j]);
if (i < j)
swap(nums[i], nums[j]);
}//将整个数组分为小于或等于x 和 大于x两部分
quick_sort(l, j);//在递归
quick_sort(j + 1, r);
}
快速选择算法
定义：
快速选择算法（Quickselect）是一种在未排序的数组中查找第k小/大元素的算法，时间复杂度为O(n)。它的基本思想是选择一个基准值（pivot），将数组分为两部分，一部分小于等于基准值，一部分大于基准值。然后根据k与基准值的大小关系，选择其中一部分进行递归搜索，直到找到第k小/大元素为止。快速选择算法和快速排序算法的思路类似，但是快速选择算法只需要对一部分数组进行快速排序，而不需要对整个数组进行排序。因此，快速选择算法的平均时间复杂度为O(n)，最坏时间复杂度为O(n^2)，但是最坏情况出现的概率很小。快速选择算法的时间复杂度为O(n)，空间复杂度为O(1)
基本步骤
选择一个基准值pivot，可以选择数组中的任意一个元素。
将数组分为两部分，一部分小于等于pivot，一部分大于pivot。
如果k小于等于左边部分的元素个数，那么继续在左边部分中查找第k小元素；否则，在右边部分中查找第k-left个小元素。
重复步骤2和3，直到找到第k小元素为止。
代码
```cpp
ll quick_select(int l, int r, int q)
{
if (l >= r)
return a[l];//最后当l==r时数组的值一定是要找的值
int i = l - 1, j = r + 1, x = a[rand() % (r - l + 1) + l];
while (i < j)
{
while (a[++i] < x)
;
while (a[--j] > x)
;
if (i < j)
swap(a[i], a[j]);
}
int s = j - l + 1;//此时[l,j]数组的这段范围是小于等于 x的[j+1,r]这段范围大于x
if (q <= s)
return quick_select(l, j, q);
else
return quick_select(j + 1, r, q - s);
//最后返回的值是第q小的数最小的数是第一位
}
归并排序
思路：先分在和
归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。
将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。
代码
void merge_sort(int nums[],int l,int r)//归并排序
{
if(l>=r)return;
int mid=(l+r)/2;
merge_sort(nums,l,mid);//把元素组划分为两个子数组，最后数组中只包含一个元素
merge_sort(nums,mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid && j<=r)
{
if(nums[i]<nums[j])tmp[k++]=nums[i++];
else tmp[k++]=nums[j++];
}//比较，将更小的那个赋值给tmp数组
while(i<=mid)tmp[k++]=nums[i++];
while(j<=r)tmp[k++]=nums[j++];
//防止没有赋值完
for(i=l,j=0;i<=r;j++,i++)nums[i]=tmp[j];//将排序好的数组赋值给原数组
}
利用归并排序求逆序对
思路
归并排序是将一个序列分成两个有序的序列，归并两个有序序列，归并后则该序列有序，是基于分治的思想。
根据逆序对的定义，我们也可以使用分治的算法来求解逆序对的数量。如图：
我们将序列分成两部分，我们发现逆序对的数量是三种逆序对数量的和：
左边序列的逆序对
右边序列的逆序对
横跨中间的逆序对
利用归并排序，我们可以分别求解左边序列的逆序对的数量和右边序列的逆序对的数量。但是我们还需要求解横跨中间的逆序对的数量。
![[Pasted image 20240724201959.png]]
意味着在归并两个序列的过程中，我们就可以计算出横跨中间的逆序对的数量。
时间复杂度O(nlogn)，空间复杂度O(N)
代码
ll merge_sort(int l,int r)
{
if(l>=r)
{
return 0;
}
int i = l, mid = (l + r) / 2, j = mid + 1,k=0;
ll res = merge_sort(l, mid) + merge_sort(mid + 1, r);//将区间分为两份，分到最小的时候在开始合并
while (i <= mid && j <= r)
{
if(a[i]<=a[j])
tmp[k++] = a[i++];
else
{
tmp[k++] = a[j++];//这时候数组是排好序的在a[i]后的数一定都大于a[j]；
res += mid - i + 1;//所以逆序数就是在mid到i之间的
}
}
while(i<=mid)tmp[k++]=a[i++];
while(j<=r)tmp[k++] = a[j++];
for (int i = l, j = 0; i <= r;i++)
{
a[i] = tmp[j++];
}
return res;
//最后返回逆序对的值即可
}
二分查找：前提是数组已经排好序
思想
以在一个升序数组中查找一个数为例。它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。
代码
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans;
if (nums.size() == 0) {
ans.push_back(-1);
ans.push_back(-1);
return ans;
}
int left = -1, right = nums.size(), mid;//确定left和right的范围时一定要根据最后退出条件left+1=right，如果最后结果要取right则left就要在数组最小范围减一反之亦然
while (left + 1 != right) {
mid = (left + right) / 2;
if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
// 如果未找到目标值
//最后要判断right是否在数组范围内，不然会出错
if (right == nums.size() || nums[right] != target) {
ans.push_back(-1);
ans.push_back(-1);
return ans;
}
// 目标值的左边界
ans.push_back(right);
// 重置左边界和右边界，查找目标值的右边界
left = -1;
right = nums.size();
while (left + 1 != right) {
mid = (left + right) / 2;
if (nums[mid] > target) {
right = mid;
} else {
left = mid;
}
}
// 添加右边界
ans.push_back(left);
return ans;
}
};
stl c++二分函数
C++ 标准库中实现了查找首个不小于给定值的元素的函数 std::lower_bound 和查找首个大于给定值的元素的函数 std::upper_bound，二者均定义于头文件 <algorithm> 中。
二者均采用二分实现，所以调用前必须保证元素有序。
浮点数二分
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string>
using namespace std;
const int N = 2e5 + 10;
using ll = long long;
ll a[N];
ll tmp[N];
ll cont = 0;
void solve()
{
double n;
cin >> n;
double l=-10000,r=10000,mid;
while(r-l>=1e-8)//如果题目要求保留到第n位小数，则r-l>=1e-(n+2)
{
mid = (l + r) / 2;
if (mid*mid *mid>n)
r = mid;
else
l = mid;
}
printf("%lf", l);
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
高精度
高精度加法
P1601 A+B Problem（高精） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码
vector <int> add(vector <int> &a,vector<int> &b)
{
int t = 0, i = 0;
vector<int> ans;
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];
ans.push_back(t % 10);//两数相加后
t = t / 10;//t进位
}
if(t)//最后t只有可能时是0 、1，如果为1则要在数组后面加一位
ans.push_back(1);
return ans;
}
void solve()
{
string s1, s2;
cin >> s1 >> s2;
vector<int> a, b;
for (int i = s1.size()-1; i >=0;i--)
{
a.push_back(s1[i] - '0');
}
for (int i = s2.size() - 1; i >= 0; i--)
{
b.push_back(s2[i] - '0');
}
vector<int> ans = add(a, b);
for (int i = ans.size()-1;i>=0;i--)
{
cout << ans[i];
}
}
高精度减法
P2142 高精度减法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码
bool cmp(vector<int> a,vector<int>b)//比较a和b的大小，如果a比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)
{
int t = 0, i = 0;
vector<int> ans;
for (int i = 0; i < a.size();i++)//从个位开始
{
t = a[i] - t;
if(i<b.size())
t -= b[i];
ans.push_back((t + 10) % 10);
//此处包含两种情况，如果t<0,则加入(t+10);
//如果t>0则直接加入t
if(t<0)//如果t<0;代表要借位
t = 1;
else
{
t = 0;
}
}
while (ans.size() > 1 && ans.back() == 0)
{
ans.pop_back();
}
return ans;
}
高精度乘法:高精度×低位数类型
vector <int> mul(vector <int> &a,int b)
{
vector<int> ans;
int t = 0;
for (int i = 0; i < a.size() || t;i++)//注意要判断最后t是否为0若不为0则要加入到数组后
{
if(i<a.size())
t += a[i] * b;
ans.push_back(t%10);
t = t / 10;
}
while(ans.back()==0 && ans.size()>1)//最后去除前导0
{
ans.pop_back();
}
return ans;
}
高精度乘法:高精度×高精度类型
高精度练习之乘法 II - 问题 - MYOJ
思路
先将每一位乘了之后再依次相加，相乘时可以找规律
![[Pasted image 20240725202156.png]]
vector<int> mul(vector<int> &a, vector<int> &b)
{
vector<int> ans(a.size()+b.size()+10,0);//一定要多分配数组空间
int t = 0;
for (int i = 0;i<a.size();i++)
for (int j = 0; j < b.size();j++)
{
ans[i + j] += a[i] * b[j];//可以找到数组相乘的规律下标
}
t = 0;
for (int i = 0; i < ans.size();i++)
{
t += ans[i];
ans[i] = t % 10;
t /= 10;
}
while(ans.back()==0 && ans.size()>1)//去前导0
ans.pop_back();
return ans;
}
高精度除法
vector<int> div(vector<int> &a, int b,int &r)//用引用传入余数r
{
vector<int> ans;
for (int i = a.size()-1; i>=0;i--)
{
r = r * 10 + a[i];
ans.push_back(r / b);
r = r % b;
}
reverse(ans.begin(), ans.end());//翻转数组，记得要在翻转后去除前导0
while(ans.back()==0 && ans.size()>1)
ans.pop_back();
return ans;
}
高精度除高精度(absent)
前缀和与差分
前缀与差分的联系
![[Pasted image 20240715101002 1.png]]
一维前缀和
795. 前缀和 - AcWing题库
定义
前缀和可以简单理解为「数列的前n项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。1
C++ 标准库中实现了前缀和函数 std::partial_sum，定义于头文件 <numeric> 中。
用于求从l，r区间的和.
代码
ll a[N];
ll prefix[N];
ll cont = 0;
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)//i从1到n方便求前缀和
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
prefix[i] = prefix[i - 1] + a[i];//求前缀和的公式
}
while (m--)
{
int l, r;
cin >> l >> r;
cout << prefix[r] - prefix[l - 1] << '\n';//求l，r区间的和
}
}
二维前缀和
796. 子矩阵的和 - AcWing题库
![[Pasted image 20240726210537.png]]
代码
int n, m, q;
cin >> n >> m >> q;
for (int i = 1;i <= n;i++)
{
for (int j = 1; j <= m;j++)
{
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
prefix[i][j] = a[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];//求二维前缀和公式
}
}
while(q--)
{
int x1,x2,y1,y2;
cin >> x1 >> y1 >>x2 >> y2;
cout << prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1]<<'\n';//求【x1，y1】 到【x2】【y2】区间的和
}
一维差分
797. 差分 - AcWing题库
思想
差分是一种和前缀和相对的策略，可以当做是求和的逆运算。
diff[i]=a[i]-a[i-1];
本质就是找到一个数组diff对其求前缀和后是a数组
代码
void insert(int l, int r,int h)//精妙之处用一个函数就可以对差分数组进行修改
{
diff[l]+=h;
diff[r + 1] -= h;
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <=n;i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
insert(i, i, a[i]);//【i，i】这个区间修改为a【i】
}
while(m--)
{
int l,r,c;
cin >> l >> r >> c;
insert(l, r, c); //将l，r这个区间加上c
}
for (int i = 1; i <= n;i++)
{
a[i] = a[i - 1] + diff[i];//对diff数组求前缀和重新计算询问后的a数组
}
for (int i = 1; i <= n;i++)
{
cout << a[i]<< " ";
}
}
二维差分
思想
![[Pasted image 20240726212941.png]]
ll a[N][N];
ll diff[N][N];
ll cont = 0;
void insert(int x1, int y1, int x2, int y2, int c)
{
diff[x1][y1] += c;
diff[x1][y2 + 1] -= c;
diff[x2 + 1][y1] -= c;
diff[x2 + 1][y2 + 1] += c;
}
void solve()
{
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
insert(i , j, i, j, a[i][j]);
}
}
while (q--)
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1, y1, x2, y2, c);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
a[i][j] = a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1] + diff[i][j];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cout << a[i][j] << ' ';
}
cout << '\n';
}
}
双指针
数组元素的目标和
(1)二分
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
ll a[N], b[N];
void solve()
{
int n, m, x;
cin >> n >> m >> x;
for (int i = 0; i < n;i++)
{
cin >> a[i];
}
for (int i = 0; i < m;i++)
{
cin >> b[i];
}
for (int i = 0; i < n;i++)
{
int l = 0, r = m, mid;
while(l+1!=r)
{
mid = (l + r) / 2;
if(b[mid]>x-a[i])
{
r = mid;
}
else
{
l = mid;
}
}
if(b[l]+a[i]==x)
{
cout << i << ' ' << l;
return;
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
（2）
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
ll a[N], b[N];
void solve()
{
int n, m, x;
cin >> n >> m >> x;
for (int i = 0; i < n;i++)
{
cin >> a[i];
}
for (int i = 0; i < m;i++)
{
cin >> b[i];
}
for (int i = 0,j=m-1; i < n;i++)
{
while(j>=0 && a[i]+b[j]>x )
j--;
if(j>=0 && b[j]+a[i]==x)
{
cout << i << " " << j;
return;
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
位运算
基本运算符
![[Pasted image 20240810184633.png]]
异或^相同为0不同为1（不进位加法）
1 ⊕ 1 = 0
0 ⊕ 0 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
性质
a+b
==a+b=2 * (a&b)+(a^b)==
求该数是否是二的幂
==x&(x-1) = = 0 则成立==
求一个数二进制的个数
int x,cont=0;
x = 8;
while(x)
{
x &= x - 1;
cont++;
}
cout << cont;
bitset:可以输出一个数的二进制
例如 bitset<8>(7)高位补零
可以输出长度为7的x二进制（高位补0）
lowbit![[Pasted image 20240921182528.png]]
返回该数二进制最后一位1
int lowbit(int x)
{
return x & -x;
}
可以求一个数的二进制有几个
离散化
定义：
离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。
当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。
从上面的例子我们也可以看出，离散化就是使离散的点(差距很大的数值)转换成更加紧密的点。(也即数组下标)这样就可以极大的缩小空间复杂度和时间复杂度，且不改变原来的属性。即我原来比你大，离散化后仍然比你大，只不过差距变小了而已。
802. 区间和 - AcWing题库
代码
const int N = 3e5 + 10;//题目最大范围是1e5如果存下标最大就是n+2m
ll a[N],prefix[N];//
vector<pair<int, int>> cg, query;//cg存改变的值，query存询问的区间
vector<int> alls;//alls存所有区间
int find(int x)//find的本质就是找该数在alls数组里面排序后是第几个数
{
int l = 0, r = alls.size(), mid;
while(l+1!=r)
{
mid = (l + r) / 2;
if(alls[mid]>x)
{
r = mid;
}
else
{
l = mid;
}
}
return r;
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n;i++)
{
int tmp1, tmp2;
cin >> tmp1 >> tmp2;
cg.push_back({tmp1, tmp2});
alls.push_back(tmp1);
}
for (int i = 0; i < m;i++)
{
int tmp1, tmp2;
cin >> tmp1 >> tmp2;
query.push_back({tmp1, tmp2});
alls.push_back(tmp1);
alls.push_back(tmp2);
}
sort(alls.begin(), alls.end());//先排序后去重
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (int i = 0; i < n;i++)
{
int l = find(cg[i].first);//遍历改变的数组，将要改变的下标离散化
a[l] += cg[i].second;
}
for (int i = 1; i <= alls.size();i++)
{
prefix[i] = prefix[i - 1] + a[i];//对a[i]求前缀和
}
for (int i = 0; i < m; i++)
{
int l = find(query[i].first);
int r = find(query[i].second);
cout << prefix[r] - prefix[l - 1] << '\n';
}
}
区间合并
void solve()
{
int n;
cin >> n;
for (int i = 0; i < n;i++)
{
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;//设为2e9确保第一个区间可以赋值上去
vector<pair<int, int>> ans;
for (int i = 0; i < n; i++)
{
if(segs[i].first>ed)
{
if(ed!=-2e9)ans.push_back({st, ed});
ed = segs[i].second;
st = segs[i].first;
}
else
{
ed = max(ed, segs[i].second);//此处注意要与ed比较大小不能直接赋值
}
}
if(ed!=-2e9)
ans.push_back({st, ed});
cout << ans.size();
}
STL
链表
单链表
const int N = 1e5 + 10;
using ll = long long;
ll e[N], ne[N], idx=1;
void init()
{
ne[0] = -1;
}
void insert(int k,int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
void del(int k)
{
ne[k] = ne[ne[k]];
}
void solve()
{
int n;
cin >> n;
init();
for (int i = 0; i < n;i++)
{
string h;
cin >> h;
if(h == "I")
{
int k,x;
cin >>k>>x;
insert(k,x);
}
else if (h == "D")
{
int k;
cin >> k;
del(k);
}
else if(h=="H")
{
int x;
cin >> x;
insert(0, x);
}
}
for (int i = ne[0]; i != -1;i=ne[i])
{
cout << e[i] << ' ';
}
}
双链表
==注意==
注意双链表的初始化以及最后的循环
ll e[N], re[N], le[N], idx = 1, head = 0, tail = 1e5;
void init()
{
re[head] = tail;//
le[tail] = head;
}
for (int i = re[head]; i !=tail;i=re[i])
{
cout << e[i] << ' ';
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <bitset>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
ll e[N], re[N], le[N], idx = 1, head = 0, tail = 1e5;
void init()
{
re[head] = tail;//
le[tail] = head;
}
void insert(int k,int x)
{
e[idx] = x;
re[idx] = re[k];
le[idx] = k;
re[k] = idx;
le[re[idx]] = idx;
idx++;
}
void del(int k)
{
re[le[k]] = re[k];
le[re[k]] = le[k];
}
void solve()
{
int n;
cin >> n;
init();
int k, x;
for (int i = 0; i < n;i++)
{
string s;
cin >> s;
if(s=="R")
{
cin >> x;
insert(le[tail], x);
}
else if(s=="L")
{
cin >> x;
insert(head, x);
}
else if(s=="D")
{
cin >> k;
del(k);
}
else if(s=="IL")
{
cin >> k >> x;
insert(le[k], x);
}
else if(s=="IR")
{
cin >> k >> x;
insert(k, x);
}
}
for (int i = re[head]; i !=tail;i=re[i])
{
cout << e[i] << ' ';
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
栈
表达式求值
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <bitset>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
char c[N];
ll num[N];
map<char, int> p;
int ct = 0, nt = 0;
void cau()
{
/*假设式子是4/3
栈顶为3然后是4
应该是后面的除前面的所以是b/a*/
int a = num[nt--];//注意加减乘除的顺序
int b = num[nt--];
char h = c[ct--];
int ans = 0;
if(h=='*')
ans = a * b;
else if(h=='/')
ans = b/a;
else if(h=='+')
ans = a + b;
else if(h=='-')
ans = b-a;
num[++nt] = ans;
}
void solve()
{
p['-'] = 1;
p['+'] = 1;
p['*'] = 2;
p['/'] = 2;//用map映射算符的优先级顺序
string s;
cin >> s;
string s1;
for (int i = 0; s[i];i++)
{
if(isdigit(s[i]))
{
s1 += s[i];
}
else if(s[i]=='(')
{
if(s1.size()!=0)
{
int tem = atoi(s1.c_str());
num[++nt] = tem;
s1.clear();
}
c[++ct] = s[i];
}
else if(s[i]==')')
{
if (s1.size() != 0)
{
int tem = atoi(s1.c_str());
num[++nt] = tem;
s1.clear();
}
while(c[ct]!='(')
{
cau();
}
ct--;
}
else
{
if (s1.size() != 0)
{
int tem = atoi(s1.c_str());
num[++nt] = tem;
s1.clear();
}
while (p[c[ct]] >= p[s[i]] && ct!=0)
{
cau();
}
c[++ct] = s[i];
}
}
if (s1.size() != 0)//最后s1.size()可能不为0
{
num[++nt] = atoi(s1.c_str());
s1.clear();
}
while(ct!=0)//应该是清空运算符栈顶
cau();
cout << num[nt];
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
单调栈
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <bitset>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
ll stk[N], tt = 0,a[N];
void solve()
{
int n;
cin >> n;
for (int i = 0; i < n;i++)
{
cin >> a[i];
}
for (int i = 0; i < n;i++)
{
while(stk[tt]>=a[i] && tt!=0)//一定要大于等于
{
tt--;
}
if(tt==0)
{
cout << -1 << ' ';
}else
{
cout << stk[tt] << ' ';
}
stk[++tt] = a[i];
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
队列
ll dq[N], head=0,tail=-1,a[N];
void solve()
{
int n,k;
cin >> n>>k;
for (int i = 0; i < n;i++)
{
cin >> a[i];
}
for (int i = 0; i < n;i++)
{
while(a[dq[tail]]>=a[i] && head<=tail)//先判断队尾出队
{
tail--;
}
dq[++tail] = i;//队尾进队
if(dq[head]<i-k+1)//在判断队头进队
{
head++;
}
if(i>=k-1)
{
cout << a[dq[head]]<<' ';
}
}
cout << '\n';
head = 0, tail = -1;
for (int i = 0; i < n; i++)
{
while (a[dq[tail]] <=a[i] && head <= tail)
{
tail--;
}
dq[++tail] = i;
if (dq[head] < i - k + 1)
{
head++;
}
if (i >= k - 1)
{
cout << a[dq[head]] << ' ';
}
}
}
字符串
KMP
思想
就是通过next数组求要找的这个字符串的最长公共前后缀
然后依次匹配，若匹配则j++,若不匹配则用j=ne[j]回退;若找到则输出即可
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <bitset>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
ll ne[N];
void solve()
{
int n, m;
string s1, s2;
cin >> n >> s1 >> m >> s2;
ne[0] = -1;
for (int i = 1, j = -1; i < n;i++)//第一次就是预处理求最大前缀和
{
while(s1[i]!=s1[j+1] && j!=-1)
{
j = ne[j];
}
if(s1[i]==s1[j+1])
{
j++;
}
ne[i] = j;
}
for (int i = 0,j=-1; i < m;i++)
{
while(s1[j+1]!=s2[i] && j!=-1)
{
j = ne[j];
}
if(s2[i]==s1[j+1])
{
j++;
}
if(j==n-1)
{
cout << i - j<<' ';
j = ne[j];
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
Trie
![[Pasted image 20240812095005.png]]
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <bitset>
using namespace std;
const int N = 2e5 + 10;
using ll = long long;
ll t[N][26], idx, p,cont[N];
void insert(string s)
{
p = 0;
for (int i = 0; s[i];i++)
{
int u = s[i] - 'a';
if(!t[p][u])
{
t[p][u] = ++idx;
}
p = t[p][u];
}
cont[p]++;
}
void query(string s)
{
p = 0;
for (int i = 0; s[i];i++)
{
int u = s[i] - 'a';
if(!t[p][u])
{
cout << 0<<'\n';
return;
}
p = t[p][u];
}
cout << cont[p] << '\n';
}
void solve()
{
int n;
cin >> n;
for (int i = 0; i < n;i++)
{
string s;
cin >> s;
if(s=="I")
{
string s1;
cin >> s1;
insert(s1);
}
else
{
string s1;
cin >> s1;
query(s1);
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
最大异或对
143. 最大异或对 - AcWing题库
思路
异或为相同为0，不同为1，所以如果要找最大的异或对即例如一个的二进制为（11011)他的最大异或另一个一定是（00100）先用trie树存然后查找过程中如果没有我期望的数（同一位次上相反的值）就取另一个数，最后输出结果即可
==为什么son数组要开成M：M 是 Trie 树总结点数上限。一共 N 个数，每个数 31 位，从根开始往下存，要 31 个结点，M = 31 * N==
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <bitset>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e7;
using ll = long long;
map<ll, ll> cont;
ll son[M][2], idx, p, a[N];
void insert(int x)
{
p = 0;
for (int i = 30; i >= 0; i--)
{
int k = x >> i & 1;
if (!son[p][k])
{
son[p][k] = ++idx;
}
p = son[p][k];
}
cont[p] = x;
}
int query(int x)
{
p = 0;
int res = 0;
for (int i = 30; i >= 0; i--)
{
int k = x >> i & 1;
if (son[p][!k])
{
p = son[p][!k];
}
else
{
p = son[p][k];
}
}
return cont[p] ^ x;
}
void solve()
{
int n, ans = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
insert(a[i]);
}
for (int i = 0; i < n; i++)
{
ans = max(ans, query(a[i]));
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
并查集
定义：
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。
主要构成：
并查集主要由一个整型数组pre[ ]和两个函数find( )、join( )构成。
数组 pre[ ] 记录了每个点的前驱节点是谁，函数 find(x) 用于查找指定节点 x 属于哪个集合，函数 join(x,y) 用于合并两个节点 x 和 y 。
作用：
并查集的主要作用是求连通分支数（如果一个图中所有点都存在可达关系（直接或间接相连），则此图的连通分支数为1；如果此图有两大子图各自全部可达，则此图的连通分支数为2
主要代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <bitset>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
ll p[N];
int find(int x)//返回其父亲
// 路径压缩，递归的过程中将每个节点都连上最初的那个父亲上
{
if (p[x] != x)//如果他的父亲不是他自己
{
p[x] = find(p[x]);
}
return p[x];
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <=n; i++)
{
p[i] = i;
}
string s;
for (int i = 0; i < m; i++)
{
cin >> s;
if (s == "M")
{
int a, b;
cin >> a >> b;
p[find(a)] = find(b);
}
else
{
int a, b;
cin >> a >> b;
if (find(a) == find(b))
{
cout << "Yes" << '\n';
}
else
{
cout << "No" << '\n';
}
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
带权的并查集
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <bitset>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
ll p[N], d[N];
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);//先一直递归，知道找到第一个点（维护整个树顶的权值）
d[x] += d[p[x]];//归的过程求权值
p[x] = u;
}
return p[x];
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
p[i] = i;
}
int a, b, s, res = 0;
for (int i = 0; i < m; i++)
{
cin >> s >> a >> b;
if (a > n || b > n)
{
res++;
}
else//如果距离根顶的权值是相同的，那就是同类，否则就是吃与被吃的关系
{
int pa = find(a), pb = find(b);
if (s == 1)
{
if (pa == pb)
{
if ((d[a] - d[b]) % 3 != 0)
{
res++;
}
}
else
{
p[pa] = pb;
d[pa] = d[b] - d[a];
}
}
else if (s == 2)
{
if (pa == pb)
{
if (((d[a] - d[b])-2) % 3 != 0)
{
res++;
}
}
else
{
p[pa] = pb;
d[pa] = d[b] - d[a]+2 ;
}
}
}
}
cout << res;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
模拟堆
注意辨析hp，ph数组的含义
以及交换时先存下标，不然交换之后下标对应的值会变
heap_swap(ph[k],asize)之后，h[ph[k]],ph[ph[k]],hp[ph[k]]都变化了！
注意交换操作并不会改变数组下标，也就是size仍然指向数组尾部，ph[k]仍然指向第k个插入位置
这时down和up都需要继续heap_swap，也就是说会继续用到h[ph[k]],ph[ph[k]],hp[ph[k]]，这都变成h[ph[size]]啦就不能这么用啦！！
所以需要单独储存一下ph[k]，down和up的时候继续用它就好啦！
else if(!strcmp(action,"D")){
int k;
cin >> k;
k = ph[k]; //先保存一下ph[k]
heap_swap(k,asize);
asize --;
down(k);
up(k);
}
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string.h>
#include <bitset>
#include <sstream>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
using ull = unsigned long long;
ll h[N], hp[N], ph[N], sz, m; // hp通过堆的下标找到插入第几个数，ph通过插入第几个数找到堆的下标
void head_swap(int a, int b)
{
swap(h[a], h[b]);
swap(hp[a], hp[b]);
swap(ph[hp[a]], ph[hp[b]]);
}
void up(int k) // 传的是堆的下标
{
int u = k;
if (u / 2 >0 && h[u / 2] > h[k])
{
k = u / 2;
}
if (u != k)
{
head_swap(k, u);
up(k);
}
}
void down(int k)
{
int u = k;
if (u * 2 <= sz && h[u * 2] < h[k])
{
k = u * 2;
}
if (u * 2 + 1 <= sz && h[u * 2 + 1] < h[k])
{
k = u * 2 + 1;
}
if (u != k)
{
head_swap(k,u);
down(k);
}
}
void solve()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
string s;
int a, b;
cin >> s;
if (s == "I")
{
cin >> a;
m++;
sz++;
hp[sz] = m;
ph[m] = sz;
h[sz] = a;
up(sz);
}
else if (s == "PM")
{
cout << h[1] << '\n';
}
else if (s == "DM")
{
head_swap(1, sz);
sz--;
down(1);
}
else if (s == "D")
{
int k;
cin >> k;
k = ph[k];//注意保存数组下标
head_swap(k,sz);
sz--;
up(k);
down(k);
}
else if(s=="C")
{
int k, x;
cin >> k >> x;
k = ph[k];
h[k] = x;
up(k);
down(k);
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
哈希表
数字hash
拉链法
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string.h>
#include <bitset>
#include <sstream>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
using ull = unsigned long long;
ll h[N], e[N], ne[N],idx;
int MOD = 1e5 +7;
void insert(int x)
{
int k = (x % MOD + MOD) % MOD;
e[++idx] = x;
ne[idx] = h[k];
h[k] = idx;
}
bool query(int x)
{
int k = (x % MOD + MOD) % MOD;
for (int i = h[k]; i != 0;i=ne[i])
{
if(e[i]==x)
{
return true;
}
}
return false;
}
void solve()
{
int n;
cin >> n;
while(n--)
{
string s;
cin >> s;
if(s=="I")
{
int x;
cin >> x;
insert(x);
}
else
{
int x;
cin >> x;
if(query(x))
{
cout << "Yes" << '\n';
}
else
{
cout << "No" << '\n';
}
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
开放寻址法
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <string.h>
#include <bitset>
#include <sstream>
using namespace std;
const int N = 2e5 + 3;
using ll = long long;
using ull = unsigned long long;
int null = 0x3f3f3f3f;
int h[N];
int MOD = 1e5 +7;
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t]!=x)
{
t++;
if(t==N)
{
t = 0;
}
}
return t;
}
void solve()
{
memset(h, 0x3f, sizeof h);
int n;
cin >> n;
while(n--)
{
string s;
cin >> s;
if(s=="I")
{
int x;
cin >> x;
h[find(x)] = x;
}
else
{
int x;
cin >> x;
if(h[find(x)]==null)
{
cout<<"No"<<'\n';
}
else
{
cout << "Yes" << '\n';
}
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
字符串hash
本质就是对字符串求前缀和，他的p进制
1.不能映射成 0
不然 aa 0；aaaaa 0;
2.get函数的理解
如果一个字符串是12345
求从第2到第3个；23
123*h[r]*-100h*[l-1]左移l到r区间的位置*
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
using namespace std;
const int N = 1e6 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
ll null = 0x3f3f3f3f;
ull p[N], h[N];
string s;
ull get(int l,int r)
{
return h[r] - h[l - 1] * p[r - l + 1];//12345 45要12345-12300
}
void solve()
{
int n, m;
cin >> n >> m;
cin >> s;
p[0] = 1;
for (int i = 1; i <= n;i++)
{
h[i] = h[i - 1] * P + s[i-1];//s下标从0开始
p[i] = p[i - 1] * P;//P数组代表p的几次方;
}
for (int i = 0; i < m;i++)
{
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
if(get(l1,r1)==get(l2,r2))
{
cout << "Yes" << '\n';
}
else
{
cout << "No" << '\n';
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
图论
![[1833_db6dffa81d-37ff39642fd8f74476ddcd99944d1b4.png]]
![[Pasted image 20240903143711.png]]
DFS
数据结构 ： stack
空间o（n）
不具最短性
思想 就是一直深度遍历，知道遍历到不能遍历为止，然后再回溯
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
using namespace std;
const int N = 1e6 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
ll path[N];
bool st[N];
int n;
void dfs(int u)
{
if(u==n)
{
for (int i = 0; i < n;i++)
{
cout << path[i] << ' ';
}
cout << '\n';
return;
}
for (int i = 1; i <= n;i++)//u表示排到第几个数了 然后依次遍历n
{
if(!st[i])//如果st[i]没被加入path中，则加入递归
{
path[u] = i;
st[i] = true;//上半部分是一直递归下半部分的回溯的时候要还原现场
dfs(u + 1);
st[i] = false;
}
}
}
void solve()
{
cin >> n;
dfs(0);
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
using namespace std;
const int N = 1e4 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
char path[N][N];
bool c[N], r[N], dg[N], udg[N];/主要是正对角线和反对角线的表示，然后对角线的数量是N*2/；
int n;
void dfs(int u)
{
if (u == n)//当u到n是打印所有路径，然后回溯，打印完之后一定要回溯
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << path[i][j];
}
cout << '\n';
}
cout << '\n';
return;
}
for (int i = 0; i < n; i++)
{
if (!r[i] && !dg[u + i] && !udg[u - i+n])
{
path[u][i] = 'Q';
r[i] = true;
dg[u + i] = true;
udg[u - i+n] = true;
dfs(u + 1);//上半部分是递归，下半部分是回溯，正对角线是u+i，反对角线是u-i因为有可能是负数，所以改为u-i+n；
r[i] = false;
dg[u + i] = false;
udg[u - i+n] = false;
path[u][i] = '.';
}
}
}
void solve()
{
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
path[i][j] = '.';
}
}
dfs(0);
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
BFS
数据结构 ：queue
空间o（2^n）
具有最短性
伪代码
bfs(s)
{ q = new queue()
q.push(s),
visited[s] = true
while (!q.empty())
{ u = q.pop()
for each edge(u, v)
{ if (!visited[v])
{ q.push(v) visited[v] = true }
}
}
}
思路 就是先将第一个点入队，设定一个初始状态，然后进入循环，判断队列是否为空，然后将第一个点出队，然后遍历该对所有符合条件的点入队，然后设定状态，最后循环结束即可
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
using namespace std;
const int N = 1e3 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
int path[N][N];
ll d[N][N];
int n,m;
queue<pair<int, int>> dq;
void bfs()
{
memset(d, -1, sizeof d);
dq.push({1, 1});
d[1][1] = 0;
int x[4] = {-1, 0, 1, 0};
int y[4] = {0, -1, 0, 1};
while(dq.size())
{
auto it = dq.front();
dq.pop();
for (int i = 0; i < 4;i++)
{
int k = it.first + x[i];
int h = it.second + y[i];
if (path[k][h] == 0 && (k>0 && k<=n) &&(h>0 && h<=m) && d[k][h]==-1)
{
dq.push({k, h});
d[k][h] = d[it.first][it.second] + 1;
}
}
}
cout << d[n][m];
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <=n;i++)
{
for (int j = 1; j <=m;j++)
{
cin >> path[i][j];
}
}
bfs();
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 1e4 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;;
string s;
queue<string> dq;
unordered_map<string, int> d;
int bfs()
{
dq.push(s);
d[s] = 0;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
string end = "12345678x";
while(dq.size())
{
auto t = dq.front();
dq.pop();
if(t==end)//当有一种情况与最终情况一样时，则返回
return d[t];
int dis = d[t];
int k = t.find('x');
int x = k / 3, y = k % 3;
for (int i = 0; i < 4;i++)//遍历所有可能交换的情况
{
int a = x + dx[i];
int b = y + dy[i];
if(a>=0 && a<3 && b>=0 && b<3)
{
swap(t[a * 3 + b], t[k]);
if(!d.count(t))
{
d[t] = dis + 1;
dq.push(t);
}
swap(t[a * 3 + b], t[k]);//最后一定要回溯
因为是当前这个状态可达的状态符合条件就进队
}
}
}
return - 1;
}
void solve()
{
char c;
for (int i = 0; i < 9;i++)
{
cin >> c;
s += c;
}
cout << bfs() << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
图的深度优先遍历(dfs)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100010,M=N*2; // 无向图,邻接表指针2*(n-1)故令M为2N
int n;
int h[N],e[M],ne[M],idx,ans=N; // h[]存储邻接表各个头结点,此处e[],ne[],idx同单链表
bool stl[N]; // 标记当前这个结点是否已访问,作用:使遍历不走回头路,防止子节点搜索父节点
// head, e[M],ne[M],idx; 是一条单链表
// h[N], e[M],ne[M],idx; 是N条单链表组成邻接表
void add(int a,int b) // 头插法
{ // e记录当前点的值,ne下一点的地址,h记录指向的第一个点的地址,idx:当前用到了哪个结点(的下标)
e[idx]=b;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
int dfs(int u) // 返回以u为根的树中所有结点个数(存在变量sum中)
{
int res=0,sum=1; // res存储当前连通块中结点的最大数目
stl[u]=true; // 走过是true没走过是false
for(int i=h[u];i!=-1;i=ne[i]) // 从u为表头的链表开始遍历,中间递归走各个分叉,直到u的链表尾结束
{
int j=e[i];
if(stl[j]==false) // 只有这一点没走过才走这一点所在的分叉
{
int s=dfs(j); // s为中间变量,存储u的各个子树的结点数目
res=max(res,s); // 通过打擂台获得删除u后u子树中最大连通块的结点个数(图中6与3-9比谁结点多)
sum=sum+s; // 以u为根结点的树结点数量=1+它各个子树的结点数量
}
}
res=max(res,n-sum); // 比较删除u后的u子树中最大的连通块(6,3-9中的更大者),和整个树减u子树剩下的连通块(1-2-8-5-7)
ans=min(res,ans); // 在所有最大的连通块结点数目找到最小值
return sum; // 返回以u为根的子树结点的个数(1+u的所有子树结点个数)
}
int main()
{
memset(h,-1,sizeof h); // 将h[]数组初始化成-1,-1表示空结点
scanf("%d",&n);
for(int i=0;i<n-1;i++) // n个结点插n-1次构成树
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a); // 无向图a→b且b→a
}
dfs(1); // 可从树中任意一个点开始遍历
printf("%d",ans); // 输出所有最大的连通块结点数目中的最小值
return 0;
}
图的宽度优先遍历(bfs)
848. 有向图的拓扑序列 - AcWing题库
若一个由图中所有点构成的序列 AA 满足：对于图中的每条边 (x,y)(x,y)，xx 在 AA 中都出现在 yy 之前，则称 AA 是该图的一个拓扑序列。
没有反向边，就如果出现入度为0的点就可以加入到拓扑序列中，如果加入到拓扑序列中，则该点的所有出度的点的边都能删除，删除后更新条件继续找符合条件的点加入到拓扑序列中
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
ll ne[N], e[N], h[N], idx;
ll d[N];
ll dq[N], tt = -1, hh = 0;
int n, m;
void add(int a, int b)
{
idx++;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
}
bool topsort()
{
for (int i = 1; i <= n; i++)
{
if (d[i] == 0)//先将所有入度为0的点加入到队列中
{
dq[++tt] = i;
}
}
while (tt >= hh)
{
int u = dq[hh++];
for (int i = h[u]; i != -1; i = ne[i])//加入到队列中的点
{
int j = e[i];
d[j]--;
if (d[j] == 0)//如果入度为0则加入到队列中
{
dq[++tt] = j;
}
}
}
return tt == n - 1;
}
void solve()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
add(a, b);
d[b]++;
}
if (topsort())
{
for (int i = 0; i < n; i++)//打印拓扑序列即可
{
cout << dq[i]<<' ';
}
}
else
{
cout << -1;
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
最短路
Dijkstra(最短路)(缺点==存在负权边无法使用== ，优点最快的寻路算法)
==dijstra算法基于贪心思想，当有负权边时，局部最优不一定是全局最优==
伪代码
初始化距离数组, dist[1] = 0, dist[i] = inf;
for n次循环 每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离
将不在S中dist_min的点->t
t->S加入最短路集合
用t更新到其他点的距离
朴素版
849. Dijkstra求最短路 I - AcWing题库
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 1e3 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
//千万不能先令st[1]=true；
//其实迭代n-1次第一次是初始化所有1能到达的点dist数组的含义就是该点距离1的位置
//然后就可以求出最短路
//
for (int i = 0; i < n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
{
if (!st[j] && (t == -1 || dist[t] > dist[j]))
{
t = j;
}
}
for (int j = 1; j <= n; j++)
{
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f)
{
return -1;
}
else
{
return dist[n];
}
}
void solve()
{
memset(g, 0x3f, sizeof g);
cin >>
n >> m;
for (int i = 0; i < m; i++)
{
int x, y, z;
cin >> x >> y >> z;
g[x][y] = min(g[x][y], z);
}
cout << dijkstra();
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
堆优化版（只记堆优化版，朴素版更易理解原理）
850. Dijkstra求最短路 II - AcWing题库
伪代码
利用邻接表，优先队列
在priority_queue[HTML_REMOVED], greater[HTML_REMOVED] > heap;中将返回堆顶
利用堆顶来更新其他点，并加入堆中类似宽搜
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 1e6 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
ll e[N], ne[N], h[N], idx,w[N];
int dist[N];//定义int类型
bool st[N];
int n, m;
void add(int x,int y,int z)
{
idx++;
e[idx] = y;
ne[idx] = h[x];
h[x] = idx;
w[idx] = z;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
dist[1] = 0;
pq.push({0, 1});
while(pq.size())
{
auto it = pq.top();
pq.pop();
int dis = it.first, u = it.second;
if(st[u]==true)
{
continue;
}
for (int j = h[u]; j != -1; j = ne[j])
{
int k = e[j];
if(dist[k]>dist[u]+w[j])
{
dist[k]=dist[u]+w[j];
pq.push({dist[k], e[j]});
}
}
st[u] = true;
}
if(dist[n]==0x3f3f3f3f)//dist数组是int类型的定义所以用0x3f3f3f3f比较
{
return -1;
}
else
{
return dist[n];
}
}
void solve()
{
memset(h, -1, sizeof h);
cin>>n>>m;
while(m--)
{
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
}
cout<<dijkstra();
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
bellman-ford(==有边数限制的最短路==，存在负权边)
==最多不超过k条边只能用bellman-ford==
```c++
注意连锁想象需要备份,
struct Edge{inta,b,c} Edge[M];
初始化dist, 松弛dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
松弛k次，每次访问m条边
[853. 有边数限制的最短路 - AcWing题库](https://www.acwing.com/problem/content/855/)
```c++
==backup 数组确定了每次只更新一条边==
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 1e6 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
struct Edge
{
int a, b, c;
} edge[N];
int dis[N], backup[N];
int n, m, k;
void bellman_ford()
{
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;//初始化
for (int i = 0; i < k; i++)
{
memcpy(backup, dis, sizeof dis);
for (int j = 0; j < m; j++)
{
int a = edge[j].a, b = edge[j].b, c = edge[j].c;
dis[b] = min(dis[b], backup[a] + c);
}
}
if (dis[n] > 0x3f3f3f3f / 2)
{
cout << "impossible";
}
else
{
cout << dis[n];
}
}
void solve()
{
cin >> n >> m >> k;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
edge[i] = {a, b, c};
}
bellman_ford();
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
SPFA
最短路
利用队列优化仅加入修改过的地方
for k次
for 所有边利用宽搜模型去优化bellman_ford算法
更新队列中当前点的所有出边
```c++\
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N = 1e5 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
int n, m;
int h[N], e[N], ne[N], w[N],idx;
int dis[N], cnt[N];
bool st[N];
void add(int a,int b,int c)
{
idx++;
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx;
}
void spfa()
{
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
queue[HTML_REMOVED] q;
q.push(1);
st[1] = true;
while(q.size())
{
int u = q.front();
q.pop();
st[u] = false;
for (int i = h[u]; i != -1; i = ne[i])
{
int o = e[i];
if(dis[o]>dis[u]+w[i])
{
dis[o] = dis[u] + w[i];
if(!st[o])//如果该点已经在队列那就不用进队
{ q.push(o);
st[o] = true;
}
}
}
}
if(dis[n]==0x3f3f3f3f)
{
cout << “impossible”;
}
else
{
cout << dis[n];
}
}
void solve()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m;i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
spfa();
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T–)
solve();
return 0;
}
##### 是否存在负环
[852. spfa判断负环 - AcWing题库](https://www.acwing.com/problem/content/854/)
```c++
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
int n, m;
int h[N], e[N], ne[N], w[N],idx;
int dis[N], cnt[N];
bool st[N];
void add(int a,int b,int c)
{
idx++;
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx;
}
bool spfa()
{
queue<int> q;
for (int i = 1; i <= n; i++)//为什么要有这一步，因为不只是判断从一号点出发的负环有可能负环1号点无法到达，因此就要从所有点开始找，就把所有点加入到队列中即可
{
st[i] = true;
q.push(i);
}
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
while(q.size())
{
int u = q.front();
q.pop();
st[u] = false;
for (int i = h[u]; i != -1; i = ne[i])
{
int o = e[i];
if(dis[o]>dis[u]+w[i])
{
dis[o] = dis[u] + w[i];
cnt[o] = cnt[u] + 1;
if(cnt[o]>=n)
{
return true;
}
if(!st[o])
{ q.push(o);
st[o] = true;
}
}
}
}
return false;
}
void solve()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m;i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if(spfa())
{
cout << "Yes";
}
else
{
cout << "No";
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
floyd
用于处理多源最短路算法
伪代码
初始化d
k, i, j 去更新d
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 1e4 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
int g[N][N];
int n, m, k;
int INF = 0x3f3f3f3f;
void floyd()
{
for (int i = 1; i <= n; i++)// 中继节点放最外面
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
g[j][k] = min(g[j][k], g[j][i] + g[i][k]);
}
}
}
}
void solve()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j)
g[i][j] = 0;
else
g[i][j] = INF;
}
}
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
floyd();
while (k--)
{
int x, y;
cin >> x >> y;
if (g[x][y] > INF / 2)
{
cout << "impossible" << '\n';
}
else
{
cout << g[x][y] << '\n';
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
最小生成树
Prim算法(稠密图)
基本思路
分为两个集合，以确定生成树的集合和为确定的集合，依次选择离集合最小的一条边，依次更新dis数组的值，然后将其加入到集合中，
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 500 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
int g[N][N];
int dis[N]; // 距离已选中的集合的距离
bool st[N];
int n, m, k;
void prim()
{
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
int res = 0;
for (int i = 0; i < n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
{
if (!st[j] && (t == -1 || dis[t] > dis[j]))
{
t = j;
}
}
if (dis[t] == 0x3f3f3f3f)
{
cout << "impossible" << '\n';
return;
}
res += dis[t];
st[t] = true;
for (int j = 1; j <= n; j++)
{
dis[j] = min(dis[j], g[t][j]);
}
}
cout << res;
}
void solve()
{
memset(g, 0x3f, sizeof g);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
prim();
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
Kruskal（稀疏图）
思路
将所有边按照权值的大小进行升序排序，然后从小到大一一判断。
如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。
直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。
筛选出来的边和所有的顶点构成此连通网的最小生成树。
判断是否会产生回路的方法为：使用并查集。
在初始状态下给各个个顶点在不同的集合中。、
遍历过程的每条边，判断这两个顶点的是否在一个集合中。
如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边不要。如果不在一个集合中，则要这条边。
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
int n, m, k;
ll p[N];
struct Edge{
int a, b, c;
} edge[N];
int find(int x)
{
if(p[x]!=x)
{
p[x] = find(p[x]);
}
return p[x];
}
bool cmp(Edge x,Edge y)
{
return x.c < y.c;
}
void solve()
{
int cont = 0, res = 0;
cin >> n >> m;
for (int i = 0; i < m;i++)
{
int a, b, c;
cin >> a >> b >> c;
edge[i] = {a, b, c};
}
sort(edge, edge + m, cmp);
for (int i = 1; i <=n;i++)
{
p[i] = i;
}
for (int i = 0; i < m;i++)
{
int a = edge[i].a, b = edge[i].b;
int pa = find(a), pb = find(b);
if(pa!=pb)
{
cont++;
res += edge[i].c;
p[pa] = pb;
}
}
if(cont==n-1)
{
cout << res;
}
else
{
cout << "impossible";
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
二分图
![[Pasted image 20241003180734.png]]
![[Pasted image 20241003180258.png]]
染色法判定二分图
860. 染色法判定二分图 - AcWing题库
思路
开始对任意一未染色的顶点染色。
判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。
若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
ll idx, e[N], ne[N], h[N];
ll color[N];
void add(int a, int b)
{
idx++;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
}
bool dfs(int u, int cor)
{
color[u] = cor;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!color[j])
{
if (!dfs(j, 3 - cor))//将1换成2 将2换成1
{
return false;
}
}
else if (color[j] == cor)
{
return false;
}
}
return true;
}
void solve()
{
memset(h, -1, sizeof h);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
for (int i = 1; i <= n; i++)
{
if (!color[i])
{
if (!dfs(i, 1))
{
cout << "No";
return;
}
}
}
cout << "Yes";
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
二分图的最大匹配
![[uwE7FNHfzxn5RZY.gif]]思路
1.遍历左边所有点
2dfs遍历该点所有可达的右边的点，若该点已被遍历过则跳过，否则有两种情况匹配成功，1，该右边的点没有匹配，2，该右边的点已匹配，存在一种情况右边的点可以与另一个点匹配，然后将该点换过去，然后继续递归3然后找到匹配的点即可
==st数组的作用==再递归的过程中 st设为true之后就不必再重复搜索
860. 染色法判定二分图 - AcWing题库
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
ll idx, e[N], ne[N], h[N];
ll match[N];//通过右半部的下标访问已经匹配的左半部的下标
ll st[N];
int n1, n2, m;
void add(int a, int b)
{
idx++;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
}
bool find(int u)
{
for (int i = h[u]; i != -1;i=ne[i])
{
int j = e[i];
if(!st[j])
{
st[j] = true;
if(match[j]==0 || find(match[j]))
{
match[j] = u;
return true;
}
}
}
return false;
}
void solve()
{
memset(h, -1, sizeof h);
cin >> n1 >> n2>> m;
for (int i = 0; i < m;i++)
{
int a, b;
cin >> a >> b;
add(a, b);
}
ll res = 0;
for (int i = 1; i <= n1;i++)
{
memset(st, false, sizeof st);
if(find(i))
res++;
}
cout << res;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
数论基础 - OI Wiki
质数
定义 为在大于1的自然数中，除了1和它本身以外不再有其他因数，素数有无穷多个。
试除法判定质数
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
bool isprime(int a)
{
if(a==1)
return false;
else
{
for (int i = 2; i <= a/i;i++)
{
if(a%i==0)
{
return false;
}
}
}
return true;
}
void solve()
{
int n;
cin>>n;
for (int i = 0; i < n;i++)
{
int a;
cin >> a;
if(isprime(a))
{
cout << "Yes"<<'\n';
}
else
{
cout << "No" << '\n';
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
试除法分解质因数
867. 分解质因数 - AcWing题库
1没有质因数质数，质数最大是二
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <bitset>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 10;
const int P = 131;
using ll = long long;
using ull = unsigned long long;
void zhiyin(int a)
{
for (int i = 2; i <= a/ i;i++)
{
if(a%i==0)
{
int s = 0;
while(a%i ==0)
{
a /= i;
s++;
}
cout << i << ' ' << s << '\n';
}
}
if(a>1)
cout << a << " 1"<<'\n';
}
void solve()
{
int n;
cin>>n;
for (int i = 0; i < n;i++)
{
int a;
cin >> a;
zhiyin(a);
cout << '\n';
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
T = 1;
while (T--)
solve();
return 0;
}
