freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
一、动态规划
1.背包DP
n件价值vi重量wi将容量为m的背包放入物品中
dp[i]表示不同重量下的最大值
for(int i=0;i<n;i ){ for(int j=m;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]] v[i]); } } cout<<dp[m]<<endl;
dp[i]表示不同价值下的最小重量
memset(dp,INF,sizeof(dp)); dp[0]=0; for(int i=0;i<n;i ){ for(int j=M;j>=v[i];j--){ dp[j]=min(dp[j],dp[j-v[i]] w[i]); } } long long i,ans; for(i=0;i<M;i ) if(dp[i]<=t) ans=i; cout<<ans<<endl;
for(int i=0;i<n;i ){ for(int j=w[i];j<=m;j ){ dp[j]=max(dp[j-w[i]] v[i],dp[j]); } }
二进制优化
时间复杂：O(nmlog(si))
for(int i=0;i<n;i ){ int tv,tw,tm; cin>>tv>>tw>>tm; int c=1; while(tm>c){ w[cnt] = c*tw; v[cnt ] = c*tv; tm -= c; c<<=1; } w[cnt] = tm*tw; ////补充不足指数的差值 v[cnt ] = tm*tv; } for(int i=0; i<cnt; i ){ for(int j=t; j>=w[i]; j--){ dp[j]=max(dp[j],dp[j-w[i]] v[i]); } }
优化单调队列
时间复杂度：O(nm)
for(int i=1;i<=m;i ){ cin>>w>>v>>num; for(int d=0;d<w;d ){ ///模拟余数 head=tail=1; //初值 for(int j=0;j<=(n-d)/w;j ){ //（n-d）/w指目前有多少余数 int o=f[j*w d]-v*j;///进入队列的值 while(q[tail-1]<=o&&head<tail)tail--;///弹出队尾 q[tail]=o;//进队 p[tail ]=j;//下标 while(j-p[head]>num&&head<tail)head ;///弹出队头 f[j*w d]=max(f[j*w d],q[head] v*j);//找最大值 } } }
void solve(){ //将 n 二分，前半部分的所有可能值都存储在中 pair 中(数位01设置选择) int n1 = n / 2; int num1 = 1 << n1; for(int i = 0; i < num1; i ) { long long sw = 0, sv = 0; for(int j = 0; j < n1; j ) { if((i >> j) & 1) { sw = w[j]; sv = v[j]; } } pi[i] = make_pair(sw, sv); } //单调排序，筛除 w[i]>=w[j]但v[i]<=v[j]的 pair sort(pi, pi num1); int m = 1; for(int i = 1; i < num1; i ) { if(pi[m-1].second < pi[i].second) { pi[m ] = pi[i]; } } //处理另一半 n ，寻找满足 w 时 最大的 v int n2 = n - n1; int num2 = 1 << n2; long long ans = 0; for(int i = 0; i < num2; i ) { long long sw = 0, sv = 0; for(int j = 0; j < n2; j ) { if((i >> j) & 1) { sw = w[n1 j]; sv = v[n1 j]; } } if(sw <= W) { long long tv = (lower_bound(pi, pi m, make_pair(W - sw, INF)) - 1)->second; ans = max(ans, sv tv); } } cout<<ans<<endl; }
区间DP
for (int i = 0; i <= a.size(); i ) dp[i][0] = i; for (int j = 0; j <= b.size(); j ) dp[0][j] = j; for(int i=1;i<=a.size();i ){ for(int j=1;j<=b.size();j ){ if (a[i-1]==b[j-1]) { dp[i][j] = dp[i - 1][j - 1]; // 不需要编辑 } else { int insert1 = dp[i][j - 1] 1; // A 插入 B 第j个字符 int insert2 = dp[i - 1][j] 1; // B 插入 A 第一个字符 int replace = dp[i - 1][j - 1] 1; // A 替换成 B 第j个字符 dp[i][j] = min(replace, min(insert1, insert2)); } } } cout<<dp[a.size()][b.size()]<<endl;
for(int len=1;len<n;len ){ for(int l=1;l len<=n;l ){ int r = l len; dp[l][r]=INF; for(int k=l;k<r;k ){ dp[l][r]=min(dp[l][r],dp[l][k] dp[k 1][r] s[r]-s[l-1]); } } } cout<<dp[1][n]<<endl;
2.数位DP
获取x，单独存储在a[i]中
int solve(int x){ int pos=0; while(x){ a[pos ]=x; x/=10; } return dfs(pos-1,-1,0,true); }
深度优先搜索（DFS）
int dfs(int pos,int pre,int sta,bool limit){ if(pos==-1) return 1; if(!limit && dp[pos][sta]!=-1) return dp[pos][sta]; int up=limit ? a[pos] : 9; int tmp=0; for(int i=0;i<=up;i ) { if(pre==6 && i==2)continue; if(i==4) continue;///保证枚举的合法性 tmp =dfs(pos-1,i,i==6,limit && i==a[pos]); } if(!limit) dp[pos][sta]=tmp; return tmp; }
3.ST表
二维数组 st[i][j] 表示从序列第 i 数字开始，包括自己的后数 2^(j - 1)次数，最大值(或最小值)
即：序列间隔 [i, i 2^(j - 1)] 最大值(或最小值)
int n,log[N],st[N][40],a[N]; void init(){ log[0]=-1;
for(int i=1;i<=n;i++){
log[i]=((i&(i-1))==0)?log[i-1]+1:log[i-1];
st[i][0]=a[i];
}
for(int j=1;j<=log[n];j++)
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
查询：
int query(int l,int r){
int k=log[r-l+1];
return max(st[l][k],st[r-(1<<k)+1][k]);
}
二、搜索
1.回溯算法
1) 回溯的实现
递归
举例：针对N叉树的递归回溯方法
void backtrack(int t){
if(t>n) output(x); //叶子节点，输出结果，x是可行解
else for(int i=0;i<k;i++){ //当前节点的所有子节点
x[t]=value[i]; //每个子节点的值赋值给x
//满足约束条件和限界条件
if(constraint(t)&&bound(t)) backtrack(t+1);
}
}
递推
举例：针对N叉树的递归回溯方法
void backtrack(){
int t=1;
while(t){
if(exitsubnode(t)){ //若当前节点的存在子节点
for(int i=0;i<k;i++){ //遍历当前节点的所有子节点
x[t]=value[i];
//满足边界条件和限界条件
if(constraint(t)&&bound(t)){
//如果在节点t处得到了一个解
if(solution(t)) output(x);//输出可行解
else t++; //继续向下搜索
}
}
}
else t--; //若不存在子节点，则返回上一层
}
}
2) 子集树和排列树
子集树
所给的问题是从n个元素的集合S中找出满足某种性质的子集，相应的解空间成为子集树。 如0-1背包问题，从所给重量、价值不同的物品中挑选几个物品放入背包，使得在满足背包不超重的情况下，背包内物品价值最大。它的解空间就是一个典型的子集树。
void backtrack(int t){
if(t>n) output(x);
else for(int i=0;i<k;i++){
x[t]=value[i];
if(constraint(t)&&bound(t)) backtrack(t+1);
}
}
排列树
所给的问题是确定n个元素满足某种性质的排列，相应的解空间就是排列树。 如旅行售货员问题，一个售货员把几个城市旅行一遍，要求走的路程最小。它的解就是几个城市的排列，解空间就是排列树。
void backtrack(int t){
if(t>n) output(x);
else for(int i=t;i<n;i++){
swap(x[t],x[i]);
if(constraint(t)&&bound(t)) backtrack(t+1);
swap(x[t],x[i]);
}
}
2.BFS（广度优先搜索）
/**
-
广度优先搜索
-
@param Vs 起点
-
@param Vd 终点
*/
bool BFS(Node& Vs, Node& Vd){
queue<node> Q;
Node Vn, Vw;
int i;
//初始状态将起点放进队列Q
Q.push(Vs);
hash(Vw) = true;//设置节点已经访问过了！
while (!Q.empty()){
Vn = Q.front();
Q.pop();
while(Vw = Vn通过某规则能够到达的节点){
if (Vw == Vd){//找到终点了！
//把路径记录，这里没给出解法
return true;//返回
}
if (isValid(Vw) && !visit[Vw]){
//Vw是一个合法的节点并且为白色节点
Q.push(Vw);//加入队列Q
hash(Vw) = true;//设置节点颜色
}
}
}
return false;//无解
}
3.DFS
三、数据结构
vector<int> v; sort(v.begin(),v.end(),cmp); //排序 reverse(v.begin(),v.end()); //翻转 rotate(v.begin(),v.begin()+midnum,v.end()) //旋转 swap_ranges(v.begin(),v.begin()+midnum,v.end()) //区域交换 v.erase(unique(v.begin(),v.end()),v.end()) //去重
在STL类的使用中，有时会需要遍历，若包含的数据类型为自定义结构体，则需重载运算符
自定义结构体操作符：
struct node{
int x,y;
bool operator < (const node& o) const{
if(x==o.x) return y<o.y;
return x<o.x;
}
};
泛型：
template<typename T>
struct node{
T x,y;
node(T x=0,y=0):x(x),y(y){}
}
node<T> operator + (const node<T>& A,const node<T>& B){
return node<T>(A.x+B.x,A.y+B.y);
}
-
正向迭代器：容器类名::iterator 迭代器名;
-
常量正向迭代器：容器类名::const_iterator 迭代器名;
-
反向迭代器：容器类名::reverse_iterator 迭代器名;
-
常量反向迭代器：容器类名::const_reverse_iterator 迭代器名;
1.Vector
//头文件 #include<vector> //创建vector对象 vector<int> vec; //尾部插入对象 vec.push_back(a); //使用下标访问结点 cout<<vec[0]; //在第i个元素前插入某元素 vec.insert(vec.begin(),a); //在头部插入 vec.insert(vec.begin()+i,a); //删除第i+1个元素 vec.erase(vec.begin()+i); //删除[i,j-1]的全部元素（下标从i开始，到j结束，不包括j） vec.erase(vec.begin()+i,vec.end()+j); //返回集合的大小 vec.size(); //清空集合 vec.clear();
2.Map
#include<map>
map<char,int> s;
s.size();
//访问
s['a'] = 1;
s.at('b')=2;
for(auto& x : s) cout<<x.first()<<':'<<x.second();
//插入
使用下标访问不存在的元素，将会在map容器中添加一个新的元素；
使用下标访问存在的元素，将会覆盖map容器中的该元素
//删除
if (s.find(key) != mymap.end()) s.erase (key);
s.erase(0); //删除key为0的元素
s.erase(s.begin()); //删除迭代器指向的位置元素
// 查询map是否为空
bool empty();
// 查询map中键值对的数量
size_t size();
// 查询map所能包含的最大键值对数量，和系统和应用库有关。
// 此外，这并不意味着用户一定可以存这么多，很可能还没达到就已经开辟内存失败了
size_t max_size();
// 查询关键字为key的元素的个数，在map里结果非0即1
size_t count( const Key& key ) const; //
//map插入pair类型
s.in
3.Set
multiset可遗留元素，即同一元素
set<int> s;
s.insert(1); //插入元素
s.begin() //返回set容器第一个元素的迭代器
s.end() //返回一个指向当前set末尾元素的下一位置的迭代器
s.rbegin() //返回的值和end()相同
s.rend() //返回的值和begin()相同
s.clear() //删除set容器中的所有的元素
s.empty() //判断set容器是否为空
s.size() //返回当前set容器中的元素个数
s.max_size() //返回set容器可能包含的元素最大个数
//排序后返回某值
for(int i = 1 ; i <= 5; ++i)
{
s.insert(i);
}
pair<set<int>::const_iterator,set<int>::const_iterator> pr;
pr = s.equal_range(3);
cout<<"第一个大于等于 3 的数是 ："<<*pr.first<<endl; //输出3
cout<<"第一个大于 3的数是 ： "<<*pr.second<<endl; //输出4
//删除
erase(iterator) ,删除定位器iterator指向的值
erase(first,second),删除定位器first和second之间的值
erase(key),删除键值key_value的值
//查找
find(key) ，返回给定值值得定位器，如果没找到则返回end()。
count(key) f
lower_bound(key) ，返回第一个大于等于key_value的定位器
upper_bound(key)，返回最后一个大于等于key_value的定位器
/*
s.insert(key)有返回值：pair<set<int>::iterator,bool>
if (s.insert(key).second){
set<int>::iterator p = s.insert(key).first;
//则*p==key;
}
//若存在返回false,不存在返回true
*/
//查找小于等于key的数
set<int>::iterator it;
it=--s.upper_bound(key);
4.Stack
1）stack类
//头文件
#include<stack>
//栈的声明
stack<char> s;
//入栈
s.push('a');
//若非空，则出栈
while(!s.empty()){
s.pop();
}
//返回栈中元素个数
s.size();
//返回栈顶元素
s.top();
//栈的清空
while(!s.empty()) s.pop();
2）卡特兰数
一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
设h(n)为卡特兰数的第n项，令h(0)=1,h(1)=1，卡特兰数满足递推式 ：
$$ h(n)=h(n-1)*(4*n-2)/(n+1) $$
$$ h(n+1)=h(n) * (4*n + 2) / (n + 2) $$
递推关系的解为：
$$ h(n)=C(2n,n)/(n+1) (n=0,1,2,...) $$
递推关系的另类解为：
$$ h(n)=C(2n,n) - C(2n,n-1) (n=0,1,2,...) $$
3）单调栈
1、新建一个空栈，将 A[1] 压入栈中，此时 A[1] 位于栈顶。
2、A[i] 与栈顶元素比较。如果A[i] 大，那么将其入栈。如果两者相等，跳过，继续下一个元素。
如果A[i]小于当前栈顶元素，说明已经找到第一个位于栈顶右边的比它小的值（此时这个较小的元素还未入栈），在它的左边（在栈内就是它脚下的元素）即为第一个左边比它小的值。此时需要这样做：
以栈顶元素为最小高度计算最大矩形面积，并更新现在的最大面积，宽度为左边界到右边界。
弹出栈顶元素。
重复第2步。
3.扫描完后，一般情况下会剩下一个单调递增的堆栈，那么一个一个出栈计算面积就可以了。左边依旧还是栈顶下面那个值，右边这个时候就不存在了，最后一个栈状态的栈顶即为右边界。
例：直方图最大矩形
int n,h[MAXN];
long long mxs(){
stack<int> s;
int i=0;
long long ans=0,tmp;
while(i<n){
if(s.empty()||h[i]>=h[s.top()]){
s.push(i++);
}
else{
int tp=s.top();
s.pop();
tmp=h[tp]*(s.empty() ? i : i - s.top() - 1);
ans=max(ans,tmp);
}
}
while(!s.empty()){
int tp = s.top();
s.pop();
tmp=h[tp]*(s.empty() ? i : i - s.top() - 1);
ans=max(ans, tmp);
}
return ans;
}
5.Queue
1）queue类
//头文件 #include<queue> //声明队列 queue<int> q; //入队，将x元素放入队列末端 q,push(x); //出队，弹出队列的第一个元素 q.pop(); //返回队列首尾元素 q.front(); q.back(); //返回队列中元素数量 q.size(); //queue里面的元素是pair类型 queue< pair<int,i> > q;
2）优先队列 ：priority_queue类
priority_queue模版类有三个模版参数：元素类型，容器类型，比较算子。
后两个可省略，默认容器为vector，默认算子为less，即非递增排列（出队时序列尾的元素出队）。
//升序队列 priority_queue < int,vector<int>,greater<int> > q; //降序队列 priority_queue < int,vector<int>,less<int> >q;
基础方法：
top 访问队头元素 empty 队列是否为空 size 返回队列内元素个数 push 插入元素到队尾 (并排序) emplace 原地构造一个元素并插入队列 pop 弹出队头元素 swap 交换内容
如: priority_queue<pair<int,int>>q; priority_queue< int,vector<int>,operator<int> >q;
自定义类算子写法：
T类中以n的大小单调递增排列
bool operator < (const T&t1,const T&t2){
return t1.n<t2.n;
}
3）单调队列
举例：滑动窗口
给定一个数列，从左至右输出每个长度为m的数列段内的最小数和最大数。
struct node
{
long long int h,p;
}v[1010000]; //h表示值，p表示位置 可以理解为下标
获取最小值维护单调递增队列
void getmin(){
int i,head=1,trail=0;
// 默认起始位置为1 因为插入是v[++trail]故初始化为0
for(i=0;i<m-1;i++){
while(trail>=head&&h[i]<=v[trail].h) trail--;
v[++trail].h=h[i],v[trail].p=i+1;
}
for(;i<n;i++){
while(t>=head&&h[i]<=v[trail].h) trail--;
v[++trail].h=h[i],v[end].p=i+1;
while(v[head].p<=i-m+1) head++;
mn[i-m+1]=v[head].h;
}
}
获取最大值维护单调递减队列
void getmax(){
int i,head=1,trail=0;
for(i=0;i<m-1;i++){
while(trail>=head&&h[i]>=v[trail].h) trail--;
v[++trail].h=h[i],v[trail].p=i+1;
}
for(;i<n;i++){
while(trail>=head&&h[i]>=v[trail].h) trail--;
v[++trail].h=h[i],v[trail].p=i+1;
while(v[head].p<=i-m+1) head++;
mx[i-m+1]=v[head].h;
}
}
4)deque
deque<int> t; t.size();//返回容器中元素的个数 t.empty();//判断容器是否为空 t.resize(num); deque.resize(num, elem); t.push_back(elem);//在容器尾部添加一个数据 t.push_front(elem);//在容器头部插入一个数据 t.pop_back();//删除容器最后一个数据 t.pop_front();//删除容器第一个数据 t.at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。 t.front();//返回第一个数据 t.back();//返回最后一个数据 t.insert(pos,elem);//在pos位置插入一个elem元素，返回新数据的位置。 t.insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。 t.clear();//移除容器的所有数据 t.erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。 t.erase(pos);//删除pos位置的数据，返回下一个数据的位置。
6.List
#include <list> list<int>lst1; //创建空list list<int> lst2(5); //创建含有5个元素的list list<int>lst3(3,2); //创建含有3个元素的list list<int>lst4(lst2); //使用lst2初始化lst4 list<int>lst5(lst2.begin(),lst2.end()); //同lst4 l1.assign(n,val); 给list赋值 l1.assign(l2.begin(),l2.end()); l1.back() 返回最后一个元素 l1.begin() 返回指向第一个元素的迭代器 l1.clear() 删除所有元素 l1.empty() 如果list是空的则返回true l1.end() 返回末尾的迭代器 l1.erase() 删除一个元素 l1.front() 返回第一个元素 l1.insert() 插入一个元素到list中 l1.insert(l1.begin(),100); 在l1的开始位置插入100。 l1.insert(l1.begin(),2,200); 在l1的开始位置插入2个100。 l1.insert(l1.begin(),l2.begin(),l2.end()); l1.max_size() 返回list能容纳的最大元素数量 l1.merge(l2，greater<int>()) 合并两个list，l2将清空 l1.pop_back() 删除最后一个元素 l1.pop_front() 删除第一个元素 l1.push_back(val) 在list的末尾添加一个元素 l1.push_front(val) 在list的头部添加一个元素 l1.rbegin() 返回指向第一个元素的逆向迭代器 l1.remove() 从list删除元素 l1.erase(it) 根据迭代器删除指定位置 l1.remove_if() 按指定条件删除元素 l1.resize(n) 改变list的大小,超出n的元素将被删除 l1.reverse() 把list的元素倒转 l1.size() 返回list中的元素个数 l1.sort() 给list排序 l1.splice() 合并两个list l1.swap(l2) 交换两个list swap(l1,l2) l1.unique() 删除list中重复的元素 list<int>::iterator i=l1.begin(); advance(i,n) 将i向后挪n位 元素被插入到 pos 所指向的元素之前 l1.splice(const_iterator pos,list& other) l1.splice(const_iterator pos,list& other,const_iterator it) 将other的第it元素转移到*this的第pos位置,操作后容器 other 变为空 l1.splice(const_iterator pos,list& other,const_iterator first ,const_iterator second)
7.树
树的重心：
定义：或。
1）二叉树
结构体写法
class TreeNode{
private:
int val;
TreeNode *left;
TreeNode *right;
public:
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}
vector<int> orderTraversal(TreeNode* root) {
vector<int> res;
order(root,res);
return res;
}
二叉树的先序遍历
void preorder(TreeNode* root, vector<int>& res) {
if(!root) return ;
res.push_back(root->val);
preorder(root->left,res);
preorder(root->right,res);
}
二叉树的中序遍历
void inorder(TreeNode* root, vector<int>& res) {
if(!root) return ;
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
二叉树的后序遍历
void proorder(TreeNode* root, vector<int>& res) {
if(!root) return ;
proorder(root->left,res);
porder(root->right,res);
res.push_back(root->val);
}
最大深度
int maxDepth(TreeNode* root) {
if(!root) return 0;
else if(!root->left) return maxDepth(root->right)+1;
else if(!root->right) return maxDepth(root->left)+1;
else return max(maxDepth(root->left),maxDepth(root->right))+1;
}
最小深度
int maxDepth(TreeNode* root) {
if(!root) return 0;
else if(!root->left) return maxDepth(root->right)+1;
else if(!root->right) return maxDepth(root->left)+1;
else return min(maxDepth(root->left),maxDepth(root->right))+1;
}
数组写法
int n,t[100]; int deep[100]; int v[10000000],d,w[100];
for(int i=0;i<n-1;i++){
cin>>x>>y;
if(v[t[x]*2]){
t[y]=t[x]*2+1;
v[t[y]]=1;
}
else{
t[y]=t[x]*2;
v[t[y]]=1;
}
deep[y]=deep[x]+1;
d=max(d,deep[y]);
w[deep[y]]++;
}
2）线段树
调用：build(1,n,1)
#define lson l,mid,i<<1
#define rson mid+1,r,i<<1|1
int sum[N<<2];
#define pushup(i) sum[i]=sum[i<<1]+sum[i<<1|1]
void build(int l,int r,int i){
if(l==r){
cin>>sum[i];
re
}
int mid=(l+r)>>1;
build(lson);
build(rson);
pushup(i);
}
void pushdown(int o,int k)
{
sum[o*2]=(sum[o*2]*mul[o]+add[o]*(k-(k>>1)))%p;
sum[o*2+1]=(sum[o*2+1]*mul[o]+add[o]*(k>>1))%p;
//更新的顺序：先乘法标记的更新，再加上累加标记的更新。并且累加标记的更新还要注意累加的次数，一个是(k-(k>>1))，另一个是（k>>1）。
mul[o*2]=mul[o*2]*mul[o]%p
mul[o*2+1]=mul[o*2+1]*mul[o]%p;
//乘法标记也要更新的。千万别忘记
add[o*2]=(add[o*2]*mul[o]+add[o])%p;
add[o*2+1]=(add[o*2+1]*mul[o]+add[o])%p;
//加法标记更新的时候要先考虑乘法标记的更新。
mul[o]=1;
add[o]=0;
//标记清空。
}
void add(int k, int v, int l, int r, int i){//i是线段树数组中的下标，k,l,r是元素数组中的下标
if (l == r){
sum[i] += v;
return;
}
int mid = (l + r) >> 1;
if (k <= mid) add(k, v, lson);
else add(k, v, rson);
pushup(i);
}
区间自加
void jia(int l,int r,int o)//三个参数，l和r代表当前在查找的区间的两个端点，o代表当前查找的区间的根结点
{
if(x<=l&&r<=y)//如果区间完全被覆盖
{
add[o]=(add[o]+v)%p;//对lazy标记直接累加v，并且模p（一步一模可以避免最后long long溢出的问题）
sum[o]=(sum[o]+v*(r-l+1))%p;//对于该点的累加和也要相应加上每一个单点的改变量
return;//lazy标记的初衷，直接退出
}
pushdown(o,r-l+1);//传递lazy标记
int mid=(l+r)>>1;//获取区间中点
if(x<=mid)
jia(le);//如果x在中点左边，就说明有必要搜索左子树
if(y>mid)
jia(re);//如果y在中点右边，就说明有必要搜索右子树
sum[o]=(sum[o*2]+sum[o*2+1])%p;
//是时候更新根结点的累加和了。
区间乘法
void cheng(int l,int r,int o)
{
if(x<=l&&r<=y)
//如果区间完全包含
{
add[o]=(add[o]*v)%p;
mul[o]=(mul[o]*v)%p;
sum[o]=(sum[o]*v)%p;
//累加和、乘法标记、加法标记全部更新。
return;//更新完就直接返回，不用多说话。
}
pushdown(o,r-l+1);//传递标记
int mid=(l+r)>>1;
if(x<=mid)
cheng(le);
if(y>mid)
cheng(re);
sum[o]=(sum[o*2]+sum[o*2+1])%p;
//这一段同上文加法。
}
int query(int x, int y, int l, int r, int i){
if (x <= l && r <= y){
return sum[i];
}
int mid = (l + r) >> 1;
int ans = 0;
if (x <= mid) ans += query(x, y, lson);
if (y > mid) ans += query(x, y, rson);
return ans;
}
3）树状数组
#define lowbit(x) -x&x
单点修改+区间查询
void update(int x,int y){
for(int i=x;i<=n;i+=lowbit(i))
a[i] += y;
}
long long getsum(int x){
long long sum = 0;
for(int i=x;i;i-=lowbit(i))
sum += a[i];
return sum;
}
//getsum(r)-getsum(l-1)
区间修改
void add(int p, int x){
while(p <= n) sum[p] += x, p += p & -p;
}
void range_add(int l, int r, int x){
add(l, x), add(r + 1, -x);
}
区间修改+区间查询
void add(int u,int x){
for(int i=u;i<=n;i+=lowbit(i)){
b[i]+=x;
c[i]+=(ll)u*x;
}
}
ll query(int x){
ll res=0;
for(int i=x;i;i-=lowbit(i))
res+=(x+1)*b[i]-c[i];
return res;
}
8.堆
快速建立的前提条件是已知所有数据
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
cnt=n;
for(int i=n/2;i;i--) down(i);
实现插入、查询最值、弹出最值
#define MAXN 1e6+50
int h[MAXN];
int sz=0;
void up(int p){
while(p>>1&&h[p]<h[p>>1]){
swap(h[p],h[p>>1]);
p>>=1;
}
}
void down(int p){
int t=p;
if(p<<1 <= sz && h[p<<1] < h[t]) t=p<<1;
if((p<<1|1) <= sz && h[p<<1|1] < h[t]) t=p<<1|1;
if(t!=p){
swap(h[p],h[t]);
down(t);
}
}
void insert(int x){
h[++sz] = x;
up(sz);
}
int top(){
return h[1];
}
void pop(){
h[1] = h[sz--];
down(1);
}
四、字符串基础
1.基础函数
输入：
while(getline(cin,s),s!="0")
字符串常见函数
//字符串的翻转 /strrev(s); //cstring reverse(s.begin(),s.end()); //algorithm,无返回值 string(s.rbegin(),s.rend()); //删除子串 s.erase(pos); s.erase(pos,end); s.insert(pos,str); //插入子串 s.find(str,pos); //查找子串 //找不到返回string::npos s.substr(pos,lenth); //截取子串 s.replace(pos,lenth,str); //替换z
类型的转换
//字符串转换为char* s.c_str() //字符串转整形 int atoi(const char *nptr); int stoi(string str); //字符串转浮点数 double stof(string str); //整形、浮点数转字符串 string str = to_string(v)
字符串的比较
#include <iostream>
using namespace std;
int main(){
string str1="hello";
cout<<str1.compare("helloo")<<endl;//返回-1；
cout<<str1.compare("hello")<<endl;//返回0 ；
cout<<str1.compare("hell")<<endl;//返回1；
}
//char数组的比较
#include <iostream>
#include <cstring>
using namespace std;
int main(){
char* str1="hello";
char* str2="hell";
char *str3="helloo";
char *str4="hello";
//原型extern int strcmp(const char *s1,const char *s2);
cout<<strcmp(str1,str2)<<endl;//返回1；
cout<<strcmp(str1,str3)<<endl;//返回-1；
cout<<strcmp(str1,str4)<<endl;//返回0.
}
字符串截取
str.substr(i,j); //从i一直截取j个字符
str.substr(i); //从i一直截取到末尾
//char数组的截取
//从str2开始，截取num个字符到str1中
strncpy(str1,str2,num);
2.hash算法
不取模
#define BASE 37
#define PRIME 233317
long long gethash(char *s){
long long n=strlen(s);
long long hash=0;
for(long long i=0;i<n;i++){
hash=(hash*BASE+s[i])+PRIME;
}
return hash;
}
取模
#define BASE 37
#define PRIME 233317
long long gethash(char *s,int mod){
long long n=strlen(s);
long long hash=0;
for(long long i=0;i<n;i++){
hash=(hash*BASE+s[i])%mod+PRIME;
}
return hash%mod;
}
3.KMP算法
确定next数组
char p[MAXN],s[MAXN];
int nxt[MAXN],slen,plen;
void getnext(){
slen=strlen(s),plen=strlen(p);
nxt[0] = -1;
int i = 0, j = -1;
while (i < plen){
if (j == -1 || p[i] == p[j]){
nxt[++i] = ++j;
}
else{
j=nxt[j];
}
}
}
主函数
getnext();
int i=0,j=0,ans=0;
while(i<slen){
if(j==-1||s[i]==p[j]){
i++;
j++;
}
else{
j=nxt[j];
}
if(j==plen){
j=0;
ans++;
//cout<<i-plen<<endl;
//i--;
//j=nxt[plen-1];
}
}
4.Manacher算法
求回文子串
#include<bits/stdc++.h>
using namespace std;
const int mx = 10000;
char ss[mx + 5], s[(mx << 1) + 5]; /// ss为源串，s为处理后的字符串
int len[(mx << 1) + 5];
void debug()
{
int i;
for (i = 1; s[i]; ++i) printf("%c ", s[i]);
puts("");
for (i = 1; s[i]; ++i) printf("%d ", len[i]);
puts("");
}
void init(){
memset(s, 0, sizeof(s));
s[0] = '#';
for (i = 0; ss[i]; ++i) s[(i << 1) + 1] = '#', s[(i << 1) + 2] = ss[i];
s[(i << 1) + 1] = '#';
memset(len, 0, sizeof(len));
}
int main()
{
int right, mid, i, maxlen;
while (gets(ss))
{
init();
maxlen = right = mid = 0;
for (i = 1; s[i]; ++i)
{
len[i] = (i < right ? min(len[(mid << 1) - i], right - i) : 1);
/* 取min的原因：记点i关于mid的对称点为i'，
若以i'为中心的回文串范围超过了以mid为中心的回文串的范围
(此时有i + len[(mid << 1) - i] >= right，注意len是包括中心的半长度)
则len[i]应取right - i(总不能超过边界吧) */
while (s[i + len[i]] == s[i - len[i]]) ++len[i];
maxlen = max(maxlen, len[i]);
if (right < i + len[i]) mid = i, right = i + len[i];
}
printf("%d\n", maxlen - 1);
debug();
}
return 0;
}
// 判断源串中的某一子串 ss[l...r] 是否为回文串
inline bool Query(int l, int r)
{
return len[l + r + 2] - 1 >= r - l + 1;
}
5.LCS（最长公共子序列）
string s,t;
int ls,lt,dp[MAXN];
void init(){
int x;
ls=s.size(),lt=t.size();
memset(dp, 0, sizeof(dp));
for(int i=0;i<ls;i++){
x=0;
for(int j=0;j<lt;j++){
int tmp=dp[j];
if(s[i]==t[j]) dp[j]=x+1;
else if(dp[j-1]>dp[j]) dp[j]=dp[j-1];
x=tmp;
}
}
}
主函数
init(); cout<<dp[lt-1]<<endl;
6.LIS（最长上升子序列）
时间复杂度：O(n^2)
int a[MAXN],dp[MAXN],n,ans;
void lis(){
ans=0;
for(int i = 0; i<n; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(a[j] < a[i])
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(dp[i], ans);
}
}
时间复杂度：O(nlogn)
#define INF 0x3f3f3f3f
int arr[N],g[N],n;
int lis(){
// memset(g,INF,sizeof(g));
fill(g, g+n, INF);
int ans=-1;
for(int i=0; i<n; i++){
int j = lower_bound(g, g+n, arr[i]) - g;
ans=max(ans,j+1);
g[j] = arr[i];
}
return ans;
}
7.后缀数组
sa[l] = 排序第 l 的后缀的开始位置
rank[i] = 后缀 suf(i) 的排名
故：rank[sa[l]] = l; sa[rank[i]] = i;
int ht[MAXN]; //维护rk相邻的两个后缀的lcp（最长公共前缀）
int sa[MAXN]; //记录排名为i的后缀初始位置
int rk[MAXN],rk2[MAXN]; //rk指下标为i的后缀的排名
bool cmp(int i,int j){
if(rk[i]!=rk[j])
return rk[i]<rk[j]; //比前一半
int ri=(i+k<=n ? rk[i+k] : -1);
int rj=(j+k<=n ? rk[j+k] : -1);
return ri<rj; //比后一半
}
void getsa(int n,char *str){
//str应从1开始
for(int i=1;i<=n;i++)
sa[i]=i,rk[i]=str[i]; //开始长度为1的rk
for(int k=1;k<=n;k++){ //k是当前比的后缀长度
sort(sa+1,sa+1+n,cmp);
rk2[sa[1]]=1;
for(int i=2;i<=n;i++)
rk2[sa[i]]=rk2[sa[i-1]];
for(inr i=1;i<=n;i++)
rk[i]=rk2[i]; //更新rk
}
}
void getht(int n,char *str){
for(int i=1;i<=n;i++)
rk[sa[i]]=i;
int h=0; //先算出每个后缀的rank
int h=0; //前一次算的两个后缀的lcp
ht[1] = 0；
for(int i=1;i<=n;i++){
int j=sa[rk[i]-1]; //i后缀的前一名
if(h>0) h--; //除去开头的位置，至少h-1的位置相同
for(;j+h<=n&&i+h<=n;h++) if(str[j+h]!=str[i+h]) break;
ht[rk[i]]
}
}
$$ LCP(i, j) = min(height[k] ,min(i, j) < k <= max(i, j)) $$
8.求前后字典序排列
给出某一序列，求按字典序排列的前一序列
bool cmp(int x,int y){
return x>y;
}
string getpre(string str){
int n=str.length();
bool judge=false; //用于判断序列是否存在 ，也可返回
string s=str;
int i,j;
for(i=n-2;i>=0;i--){
if(s[i]>s[i+1]){
judge=true;
break;
}
}
for(j=n-1;j>i;j--) if(s[j]<s[i]) break;
char tmp=s[i];
s[i]=s[j],s[j]=tmp;
sort(s.begin()+i+1,s.end(),cmp);
return s;
}
求按字典序排列的后一序列
string getpro(string str){
int n=str.length();
bool judge=false; //用于判断序列是否存在 ，也可返回
string s=str;
int i,j;
for(i=n-2;i>=0;i--){
if(s[i]<s[i+1]){
judge=true;
break;
}
}
for(j=n-1;j>i;j--) if(s[j]>s[i]) break;
char tmp=s[i];
s[i]=s[j],s[j]=tmp;
sort(s.begin()+i+1,s.end());
return s;
}
五、图论
建图
1）链式前向星
struct edge{
int to, w, next;
}e[maxn];
int head[MAXN],cnt;
void init(){
memset(head,-1,sizeof(head));
cnt=0;
}
void addedge(int u, int v, int w){
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt++;//更新以u为起点上一条边的编号
}
遍历函数
for(int i = 1; i <= n; i++){//n个起点
cout << i << endl;
for(int j = head[i]; j != -1; j = edge[j].next){//遍历以i为起点的边
cout << edge[j].to << " " << edge[j].w << endl;
}
cout << endl;
}
1.最短路
1）
多源最短路
for(int k=1;k<=n;k++){
for(int x=1;x<=n;x++){
for(int y=1;y<=n;y++){
f[x][y]=min(f[x][y],f[x][k]+f[k][y]);
}
}
}
Wallshall算法
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
if(m[j][i]==1&&j!=i) for(int k=0;k<n;k++){
if(m[i][k]) m[j][k]=1;
}
}
}
或
void wallshell() {
for (int t = 0;t < n;t++) {
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
m[i][j] = m[i][j] || (m[i][t] && m[t][j]);
}
}
}
}
2）
单源最短路，O(V*E)
#define INF 0x3f3f3f3f
int vis[N],dis[N];
int m[N][N],n,t;//n个点，t条边;
void init(){
memset(m,Inf,sizeof(m));
for(int i=0;i<n;i++){
m[i][i]=0;
}
}
void dijkstra(int u){
for(int i=0;i<n;i++){
dis[i]=m[u][i];
vis[i]=0;
}
vis[u]=1;
for(int j=0;j<n-1;j++){
int mn=INF,tmp;
for(int i=0;i<n;i++){
if(!vis[i]&&dis[i]<mn){
mn=dis[i];
tmp=i;
}
}
vis[tmp]=1;
for(int i=0;i<n;i++){
if(m[tmp][i]+dis[tmp]<dis[i]){
dis[i]=m[tmp][i]+dis[tmp];
}
}
}
}
堆优化，O(logV*E)
3）SPFA算法
可用于带有负权边的计算，若死循环则途中存在闭环。O(nm)
注：此算法采用链式前向星建图
int mark[MAXN]; //记录每个点如队列的次数
bool SPFA(int s){
for(int i = 0;i < n;i ++){
mark[i] = 0;dis[i] = INF;vis[i] = 0;
}
queue<int> q;
q.push(s); //我们只需要判断负环，随便找一个起点就好
dis[s] = 0;
vis[s] = 1; //入队列
mark[s] ++;
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = 0; //出队列
for(int i = head[u];i != -1;i = e[i].next){
int v = e[i].to;
if(dis[v] > dis[u] + e[i].w){
dis[v] = dis[u] + e[i].w;
if(!vis[v]){ //不在队列中的时候出队
q.push(v);mark[v] ++;vis[v] = 1;
}
//某点进入队列的次数超过N次则存在负环
if(mark[v] >= n) return false;
}
}
}
return true;
}
3.DFS序
void dfs(int x,int pre,int d){//L,R表示一个子树的范围
L[x]=++tot;
dep[x]=d;
for(int i=0;i<e[x].size();i++){
int y=e[x][i];
if(y==pre)continue;
dfs(y,x,d+1);
}
R[x]=tot;
}
4.拓扑排序
int in[N];
vector<int> out[MAXN];
int topology(){
queue<int> q;
//vector<int> ans;
for(int i=0;i<n;i++){
if(in[i]==0) q.push(i);
}
while(!q.empty()){
int f=q.front();
q.pop();
//ans.push_back(f);
for(int i=0;i<out[f].size();i++){
int x=out[f][i];
in[x]--;
if(in[x]==0) q.push(x);
}
}
}
//不方便使用vector时
bool topotopology(){
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(in[j]==0){
ans=j;
vis[cnt++]=j;
in[j]--;
break;
}
}
for(j=0;j<n;j++)
if(out[ans][j]) in[j]--;
}
if(cnt==n) return true;
else return false;
}
5.并查集
int root[N];
int n,m,q;
void init(){
for(int i=1;i<=n;i++){
root[i]=i;
}
}
int find(int x){
return x==root[x] ? x : root[x]=find(root[x]);
}
void merge(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
root[fy]=fx;
}
}
6.欧拉路与欧拉回路
1.无向图：连通图中，若奇数数度节点个数为0或2，则存在欧拉路。
2.有向图：连通图中，若出度比入度大1的节点和入度比出度大1的节点都为1或0，则存在欧拉路。
1.无向图：连通图中，若每个顶点的度数都是偶数，则存在欧拉回路。
2.有向图：连通图中，若每个顶点的入度都等于出度，则存在欧拉回路。
Fleury算法
void dfs( int u ) {
sta.push(u);
for( register int i = head[u]; i; i = line[i].nxt ) {
if( vis[i] ) continue;
vis[i] = vis[ i ^ 1 ] = true;
dfs( line[i].to );
break;
}
}
void fleury( int st ) {
sta.push(st);
while(!sta.empty() ) {
int flag = 0, u = sta.top(); sta.pop();
for( register int i = head[u]; i; i = line[i].nxt) {
if( vis[i] ) continue;
flag = 1; break;
}
if( !flag ) printf( "%d\n", u );
else dfs(u);
}
}
7.二分图
最大匹配的匹配边的数目
选取最少的点，使任意一条边至少有一个端点被选择，满足该集合的点的数目
选取最多的点，使任意所选两点均不相连，满足该集合的点的数目
选取最少条路径，使得每个顶点属于至少是其中某条边的端点，满足该集合的边的数目。
二分图中，最大匹配数 = 最小点覆盖数 最大独立数+最小点覆盖数=顶点数 对于不存在孤立点的图，最小边覆盖数+最大匹配数= 顶点数
匈牙利算法
求最大匹配数
int girl[MAXN]; bool line[MAXN][MAXN],used[MAXN]; int n,m;
主函数：
bool find(int x){
int ij;
for (j=1;j<=m;j++){ //扫描每个妹子
if (line[x][j]==true && used[j]==false){
//如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题，但是没有成功，所以就不用瞎费工夫了）
used[j]=true;
if (girl[j]==0 || find(girl[j])) {
//名花无主或者能腾出个位置来，这里使用递归
girl[j]=x;
return true;
}
}
}
return false;
}
主程序：
for (i=1;i<=n;i++){
memset(used,false,sizeof(used));
if find(i) all+=1;
}
KM算法
求二分图最大权完美匹配
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAXN 305;
#define INF 0x3f3f3f3f
int love[MAXN][MAXN]; // 记录每个妹子和每个男生的好感度
int ex_girl[MAXN]; // 每个妹子的期望值
int ex_boy[MAXN]; // 每个男生的期望值
bool vis_girl[MAXN]; // 记录每一轮匹配匹配过的女生
bool vis_boy[MAXN]; // 记录每一轮匹配匹配过的男生
int match[MAXN]; // 记录每个男生匹配到的妹子 如果没有则为-1
int slack[MAXN]; // 记录每个汉子如果能被妹子倾心最少还需要多少期望值
int N;
bool dfs(int girl)
{
vis_girl[girl] = true;
for (int boy = 0; boy < N; ++boy) {
if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
if (gap == 0) { // 如果符合要求
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) { // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap); // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸
}
}
return false;
}
int KM()
{
memset(match, -1, sizeof match); // 初始每个男生都没有匹配的女生
memset(ex_boy, 0, sizeof ex_boy); // 初始每个男生的期望值为0
// 每个女生的初始期望值是与她相连的男生最大的好感度
for (int i = 0; i < N; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < N; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}
// 尝试为每一个女生解决归宿问题
for (int i = 0; i < N; ++i) {
fill(slack, slack + N, INF); // 因为要取最小值 初始化为无穷大
while (1) {
// 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
// 记录每轮匹配中男生女生是否被尝试匹配过
memset(vis_girl, false, sizeof vis_girl);
memset(vis_boy, false, sizeof vis_boy);
if (dfs(i)) break; // 找到归宿 退出
// 如果不能找到 就降低期望值
// 最小可降低的期望值
int d = INF;
for (int j = 0; j < N; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);
for (int j = 0; j < N; ++j) {
// 所有访问过的女生降低期望值
if (vis_girl[j]) ex_girl[j] -= d;
// 所有访问过的男生增加期望值
if (vis_boy[j]) ex_boy[j] += d;
// 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
else slack[j] -= d;
}
}
}
// 匹配完成 求出所有配对的好感度的和
int res = 0;
for (int i = 0; i < N; ++i)
res += love[ match[i] ][i];
return res;
}
int main()
{
while (~scanf("%d", &N)) {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
scanf("%d", &love[i][j]);
printf("%d\n", KM());
}
return 0;
}
8.Tarjan算法
求强连通分量
int dfn[MAXN],low[MAXN],scc[MAXN],stk[MAXN]; //stk是栈的模拟
int index,sccnum,top;
void tarjan(int root){
if(dfn[root]) return ;
dfn[root]=low[root]=++index;
stk[++top]=root;
for(int i=head[root];i!=-1;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){ //如果结点v未访问过
tarjan(v);
low[root]=min(low[root],low[v]);
}
else if(!scc[v]){ //如果还在栈内
low[root]=min(low[root],dfn[v]);
}
}
if(low[root]==dfn[root]){ //后代不能找到更浅的点
sccnum++;
while(true){
int x=stk[top--];
scc[x]=sccnum;
if(x==root) break;
}
}
}
int dfn[MAXN],low[MAXN],scc[MAXN],stk[MAXN]; //stk是栈的模拟
int index,sccnum,top;
int num[MAXN]; //统计每个强连通分量有几个结点
void tarjan(int root){
if(dfn[root]) return ;
dfn[root]=low[root]=++index;
stk[++top]=root;
for(int i=head[root];i!=-1;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){ //如果结点v未访问过
tarjan(v);
low[root]=min(low[root],low[v]);
}
else if(!scc[v]){ //如果还在栈内
low[root]=min(low[root],dfn[v]);
}
}
if(low[root]==dfn[root]){ //后代不能找到更浅的点
sccnum++;
while(true){
int x=stk[top--];
scc[x]=sccnum;
num[sccnum]++;
if(x==root) break;
}
}
}
9.LCA（最近公共祖先）
初始化
void init(){
cnt = 1;
for(int i=0;i<N;i++){
root[i]=i;
vis[i]=0;
}
}
需要并查集，主函数逆向建树
int root[N],vis[N],to[N],cnt;
int find(int x){
if(root[x]==x) return x;
else return root[x]=find(root[x]);
}
int dfs(){
int a=1,b=1;
root[1]=find(1);
int i;
for(i=1;i!=root[1];i=to[i]){
vis[i]=a;
a++;
}
vis[root[1]]=a;
for(i=2;1;i=to[i]){
if(vis[i]){
a=vis[i];
break;
}
b++;
}
if(a==b) return 0;
else if(a<b) return 1;
else return 2;
//return i;
}
10.最小生成树
点数n，边数m Prim算法O(n^2) Kruscal算法O(mlogm) 稠密图推荐使用Prim算法 稀疏图推荐使用Kruskal算法
此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。
-
图的所有顶点集合为VV；初始令集合u={s},v=V−uu={s},v=V−u;
-
在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
-
重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。
由于不断向集合u中加点，所以最小代价边必须同步更新；需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息，：
此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
-
把图中的所有边按代价从小到大排序；
-
把图中的n个顶点看成独立的n棵树组成的森林；
-
按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
-
重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。
六、数论
a 被 b 整除，a是大的那个数（一般来讲），记为：b|a
1.快速幂
思想：
求pow(a,b)时，将b化为二进制考虑，从而大幅减少时间复杂度。快速幂的时间复杂的为O(log2n)一般的幂乘运算为O(n)。
不取模：
//不取模,a的b次幂
long long dpow(long long a,long long b){
long long ans=1;
while(b){
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
求后n位：（取模）
取模运算可求得运算结果后n位：
//取模
long long dpow(long long a,long long b,long long mod){
long long ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans%mod;
}
求前n位：
求对数运算可求得运算结果前n位：
double t=b*log10(1.0*a);//求以10位底数的指数 double r=t-(int)t;//求指数的小数部分 int result=(int)(pow(10,n+r));//求前n位
2.快速乘
inline long long qmul(long long a, long long b, long long mod){
long long res = 0;
while( b > 0 ){
if( b&1 ) res = (res + a) % mod;
a = ( a + a ) % mod;
b >>= 1;
}
return res;
}
使用long double优化：
inline long long qmul(long long x, long long y, long long mod){
return ( x * y - (long long) ( (long double) x / mod*y )*mod + mod ) % mod;
}
3.素数
#define MAXN 10000005
bool isprime[MAXN];
void prime(){
memset(isprime,true,sizeof(isprime));//初始化都是素数
isprime[1]=isprime[0]=false;
for (long long i=2; i<=MAXN; i++) {
if (isprime[i]) {
//如果i是素数，让i的所有倍数都不是素数
for(long long int j = i*i; j <= MAXN; j += i){
isprime[j] = false;
}
}
}
}
long long eular[MAXN];
void initeular(){
for(int i=2;i<MAXN;i++){
if(!euler[i])
for(int j=i;j<MAXN;j+=i){
if(!euler[j]) euler[j]=j;
euler[j]=euler[j]/i*(i-1);
}
}
}
$$ φ(n)=n*(1-1/p_1)*(1-1/p_2)*……*(1-1/p_n) $$
long long eular(long long n){
long long ans = n;
for(int i=2; i*i <= n; ++i){
if(n%i == 0){
ans = ans/i*(i-1);
while(n%i == 0)
n/=i;
}
}
if(n > 1) ans = ans/n*(n-1);
return ans;
}
需调用快速幂和快速乘
bool Miller_Rabin(ll num){
if(num == 2) return true; //2为质数
if(!(num&1)||num<2) return false;//筛掉偶数和小于2的数
ll s = 0,t = num-1; //流程中的s和t，2的s次方*t = num-1
while(!(t&1)){ //当t为偶数的时候，可以继续分解
s++;
t>>=1;
}
for (int i = 1; i <= 10; i++) { //进行十次测试即可得到比较准确的判断
ll a = rand()%(num-1)+1; //流程中的随机整数a，在1到num-1之间
ll x = dpow(a,t,num); //x为二次探测的解
for(int j = 1;j <= s;j++){ //x平方s次可以得到a的num-1次方
ll test = qmul(x,x,num); //test为x平方后对num取模
if(test == 1 && x != 1 && x != num-1) return false; //如果平方取模结果为1，但是作为解的x不是1或者num-1，说明num不是质数，返回
x = test;
}
if(x != 1) return false; //费马小定理作最后检测，a的num-1次方对num取模不等于1，一定不是质数
}
return true; //腥风血雨后仍坚持到最后，基本就是真正的质数了
}
4.分数规划
给定一系列整数a1,a2,……,an以及b1,b2,……,bn
求解一组xi(1 <= i <= n,xi = 0或1)使得下式最大化
$$ ∑[1…n](ai*xi)/∑[1…n](bi*xi) $$
解法：
在值域[L,R]内二分mid，判断是否存在一组解xi使得
$$ ∑[1…n](ai*xi)/∑[1…n](bi*xi)>=mid $$
若是则说明二分值 mid 比能求得的最大值小，令L = mid;
否则说明二分值 mid 大于能求得的最大值，令R = mid；
直到二分值达到精度要求。
判断方法：
$$ 若ai-mid*bi<0则令xi=0，否则xi=1 $$
int a[maxn],b[maxn];
double tt[maxn];
d ans;
int check(double x){
double sum=0;
for(int i=1;i<=n;++i)
tt[i]=a[i]-x*b[i];//每组ai-mid*bi
sort(tt+1,tt+1+n);
for(int i=n;i>=k+1;--i) sum+=tt[i];//检查前n-k组的和
return sum>=0;
}
主函数：
double L=0,R=1,mid;
while(R-L>1e-4)//注意精度要求
{
mid=(L+R)/2;
if(check(mid))L=mid;
else R=mid;
}
5.GCD（最大公约数）
int gcd(int a,int b){
return b? gcd(b,a%b):a;
}
long long lcm=a/gcd(a,b)*b;
x、y为任意的整数
$$ 若gcd(a,b)=d，则ax+by=k*d，且一定存在x、y使k=1 $$
即：
$$ 若ax+by=d有解，则d一定是gcd(a,b)的倍数 $$
$$ 推论：方程ax+yb=1，只有当整数a,b互质时，方程才有整数解。 $$
扩展欧几里得算法是用在已知a,b求解一组整数解x,y，使其满足裴蜀等式:
$$ ax+by=gcd(a,b)=d $$
int exgcd(int a,int b,long long &x,long long &y){
if(b==0) return x=1,y=0,a;
//d的值实际上就是gcd(a,b)，如果不需要的话可以不求
int d=exgcd(b,a%b,y,x);
return y-=a/b*x,d;
}
求逆元：
long long inv(long long a,long long m){
long long x,y;
long long d=exgcd(a,m,x,y);
return d==1 ?(x+m)%m:-1;//不互质就没有逆元
}
6.模与同余
$$ (a + b) \% n = (a \% n + b \% n) \% n\\ (a - b) \% n = (a \% n - b \% n) \% n\\ (a * b) \% n = (a \% n * b \% n) \% n\\ a^b{\ }\%n=((a\%n)^b){\ }\%n{\ }(可用于降幂) $$
$$ 如果(a-b)被m整除，那么记作a≡b(mod{\ }{\ }m)，即a与b对模m同余 $$
$$ 如果p是质数，a为自然数，gcd(a,p)=1，则a^{p-1}≡1(mod{\ }{\ }p) $$
$$ p是质数，0<x<p，则x^2≡1(mod.p)的解为x=1,x=p-1 $$
7.乘法逆元
int inv[MAXN];
inv[0] = inv[1] = 1;
for (int i = 2; i <= n; i ++) {
inv[i] = (1LL * (p - p / i) * inv[p % i]) % p;
}
既求某个数的阶乘的逆元
inv[i] 相当于是除以 i 的阶乘
ll fac[MAXN], inv[M]; fac[0] = inv[0] = 1; for(int i = 1; i <=maxn; i++) fac[i] = fac[i - 1] * i % mod; inv[maxn] = pow(fac[maxn], mod - 2); for(int i = maxn - 1; i > 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
7.中国剩余定理
m_1、m_2、……、m_n互质
$$ x≡r_1(mod{\ }{\ }m_1)\\ x≡r_2(mod{\ }{\ }m_2)\\ ⋅⋅⋅\\ x≡r_n(mod{\ }{\ }m_n) $$
long long mod[N],rmd[N],M = 1;//mod[i]即为mi,rmd表示余数
void exgcd(long long a,long long b,long long &x,long long &y){
if(b == 0) { x = 1,y = 0; return;}
exgcd(b,a%b,y,x);
y = y- a/b*x;
}
long long crt(int n){
long long ans;
for (int i = 0;i < n;i++) {
M*=mod[i];
}
for (int i = 0;i < n;i++) {
long long Mi = M / mod[i],inv,y; // Mi为所有模数乘积除以第i个模数，inv为 Mi在模 mi意义下的逆元
exgcd(Mi, mod[i], inv, y);
inv = inv % mod[i];
ans = (ans + rmd[i] * Mi * inv) % M;
}
return (ans+M)%M;
}
$$ 令M=m_1{\ }×{\ }m_2{\ }×⋯×{\ }m_n=∏m_i\\ 定义M_i=M/m_i,∀i∈\{1,2,⋯,n\}\\ 再设t_i为M_i对模m_i的逆元,即M_it_i≡1(mod{\ }{\ }m_i)\\ 构造特解x_0=∑r_iM_it_i，故通解为x=x_0+k·M $$
在m_1,m_2,……,m_n不互质的情况下求解x
long long mod[N],rmd[N];
long long excrt(int n){
//ans表示前i-1个方程式的特解，M为前i-1个方程式的模数的最小公倍数(i从2开始)
long long ans = rmd[0],M = mod[0],k,tmp;
for(int i = 1;i < n;i++){
long long mi = mod[i];
long long res = ((rmd[i] - ans)%mi + mi)%mi; //res=r2-r1,ans=r1
long long gcd = exgcd(M,mi,k,tmp);
if(res % gcd != 0) return -1;
k = qmul(k,res/gcd,mi);
ans += k * M;
M = mi /gcd * M; //M=lcm(M,mi)
ans = (ans%M+M)%M;
}
return ans;
}
$$ 将两个同余式合并，即x=r_1+t_1m_1=r_2+t_2m_2\\ 则有k_1p_1-k_2p_2=(r_2-r_1)/d,其中d=gcd(m_1,m_2)\\ 当且仅当 d | (r_2-r_1)时有解,因此x的一个特解x^*=r_1+k_1m_1\\ x在一组等价类内的通解为x^*+lcm(m_1,m_2)\\ 因此n个同余式的x的解为x=ans+M $$
七、数学
1.组合数与排列数
组合恒等式
$$ C(n,m)=C(n,n-m)=C(n-1,m-1)+C(n-1,m) $$
打表：
long long c[MAXN][MAXN]; //c[huge][small]
void getc(){
c[0][0]=1;
for(int i=1;i<=n;i++){
c[i][0]=1,c[i][1]=i;
for(int j=1;j<=m;j++){
c[i][j]=c[i-1][j-1]+c[i-1][j];
c[i][j]%=MOD;
}
}
}
const ll N = 5010;
ll fac[N * N];
void init() {
fac[0] = 1;
for (int i = 1; i < N * N; i++) {
fac[i] = (1LL * i * fac[i - 1]) % mod;
}
}
ll getc(ll a, ll b) {
return (ll)fac[a] * pow(fac[a - b], mod - 2) % mod * pow(fac[b], mod - 2) % mod;
}
ll Lucas(ll n, ll m) {
if (n < mod && m < mod)
return getc(n, m);
if (m == 0)
return 1;
return getc(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod;
}
1.n个球相同，m个盒子不同，盒子不可空，方案数为：
$$ C(n-1,m-1) $$
2.n个球相同，m个盒子不同，盒子可空，方案数为：
$$ C(n+m-1,m-1) $$
3：n个球相同，m个盒子相同，盒子不可空。(数的拆分)
$$ ans=dp[n][m]=dp[n-1][m-1]+dp[n-m][m] $$
4：n个球相同，m个盒子相同，盒子可空。
$$ ans=dp[n][1]+...+dp[n][min(n,m)] $$
2.Striling数
表示将n个不同的元素构成m个圆排列的数目
表示将n个不同的元素分成m个集合的方案数
集合内不考虑次序
递推式：
$$ S(n,m)=m*S(n-1,m)+S(n-1,m-1); $$
//#define MOD 1000000007 //注意取模
long long S[MAXN][MAXN]; //从1到 n，从1到 m
void getS(){
for(int i=0;i<=m;i++) S[0][i]=0;
for(int i=1;i<=n;i++){
S[i][1]=1;
for(int j=2;j<=m;j++){
S[i][j]=j*S[i-1][j]+S[i-1][j-1];
S[i][j]%=MOD;
}
}
}
性质
（1）n个不同的球，放入m个的盒子，盒子为空。
方案数：
$$ S(n,m) $$
这个跟第二类Stirling数的定义一致。
（2）n个不同的球，放入m个的盒子，盒子为空。
方案数：
$$ m!*S(n,m) $$
因盒子有区别，乘上盒子的排列即可。
（3）n个不同的球，放入m个的盒子，盒子为空。
方案数：
枚举非空盒的数目便可。
（4）n个不同的球，放入m个的盒子，盒子为空。
①方