freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

一、动态规划

1.背包DP

n件价值vi重量wi将容量为m的背包放入物品中

01背包

dp[i]表示不同重量下的最大值

for(int i=0;i=w[i];j--){             dp[j]=max(dp[j],dp[j-w[i]] v[i]);      }  }  cout< 
    
dp[i]表示不同价值下的最小重量
 
    
memset(dp,INF,sizeof(dp));  dp[0]=0;  for(int i=0;i=v[i];j--){    dp[j]=min(dp[j],dp[j-v[i]] w[i]);   }  }  long long i,ans;  for(i=0;i 
    
完全背包
 
    
for(int i=0;i 
    
多重背包
 
    
二进制优化
 
    
时间复杂：O(nmlog(si))
 
    
for(int i=0;i>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=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;dnum&&head 
    
 
    
超大背包
 
    
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< 
    
区间DP
 
    
编辑距离（Levenshtein距离）
 
    
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< 
    
石子合并
 
    
for(int len=1;len 
    
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< 
    
查询：
 
    
int query(int l,int r){
    int k=log[r-l+1];
    return max(st[l][k],st[r-(1< 
    
 
    
二、搜索
 
    
1.回溯算法
 
    
1) 回溯的实现
 
    
递归
 
    
举例：针对N叉树的递归回溯方法
 
    
void backtrack(int t){
	if(t>n) output(x);   //叶子节点，输出结果，x是可行解
	else for(int i=0;i 
    
递推
 
    
举例：针对N叉树的递归回溯方法
 
    
void backtrack(){
	int t=1;
	while(t){
		if(exitsubnode(t)){   //若当前节点的存在子节点  
			for(int i=0;i 
    
2) 子集树和排列树
 
    
子集树
 
    
所给的问题是从n个元素的集合S中找出满足某种性质的子集，相应的解空间成为子集树。 ​ 如0-1背包问题，从所给重量、价值不同的物品中挑选几个物品放入背包，使得在满足背包不超重的情况下，背包内物品价值最大。它的解空间就是一个典型的子集树。
 
    
void backtrack(int t){
	if(t>n) output(x);
	else for(int i=0;i 
    
排列树
 
    
所给的问题是确定n个元素满足某种性质的排列，相应的解空间就是排列树。 ​ 如旅行售货员问题，一个售货员把几个城市旅行一遍，要求走的路程最小。它的解就是几个城市的排列，解空间就是排列树。
 
    
void backtrack(int t){
	if(t>n) output(x);
	else for(int i=t;i 
    
2.BFS（广度优先搜索）
 
    
/**
 
    
 
     
 
广度优先搜索
 
 
     
 
@param Vs 起点
 
 
     
 
@param Vd 终点
 
*/
 
 
    
 
    
bool BFS(Node& Vs, Node& Vd){  
    queue 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
 
    
 
    
三、数据结构
 
    
STL函数
 
    
vector 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 
    
泛型：
 
    
template
struct node{
	T x,y;
	node(T x=0,y=0):x(x),y(y){}
}
node operator + (const node& A,const node& B){
	return node(A.x+B.x,A.y+B.y);
}
 
    
迭代器
 
    
 
     
 
正向迭代器：容器类名::iterator 迭代器名;
 
 
     
 
常量正向迭代器：容器类名::const_iterator 迭代器名;
 
 
     
 
反向迭代器：容器类名::reverse_iterator 迭代器名;
 
 
     
 
常量反向迭代器：容器类名::const_reverse_iterator 迭代器名;
 
 
    
 
    
1.Vector
 
    
//头文件
#include

//创建vector对象
vector vec;

//尾部插入对象
vec.push_back(a);

//使用下标访问结点
cout< 
    
2.Map
 
    
#include