信友队暑期集训总结（普及2）

常规
1

大纲

  • STL 掌握情况：99%

    • 栈 stack

      • top,push,pop

    • 队列 deque

      • front,back,push,pop
      • 优先队列 priority_queue
      • 双向队列 deque
        • push\_front,push\_back,pop\_front,push\_back

    • set

      • multiset
        • erase,find,insert
        • erase(find(x)) 删一个 / erase(x) 全删光
        • unordered_multiset
      • unordered_set

    • map

      • unordered_map

    • vector

      • push\_back
      • 特性：实时扩容

    • pair

      • first,second

    • 迭代器(iterator)访问

      • for(auto it=x.begin();it!=x.end();it++)
      • for(auto it:x)

  • 贪心 掌握情况：99%

    • 使用条件
      • 局部最优策略能导致产生全局最优解。
      • 具备无后效性

  • 二分 掌握情况：99%

    • 使用条件
      • 单调性
    • 模版
    int l=1,r=n;
while(l<=r){
	int mid=l+r>>1;
	if(judge(mid)){
		ans=mid;
		r=mid-1;
	}
	else l=mid+1;
}

  • 搜索 掌握情况：95%

    • dfs
      • 搜索全部的解
      • 模版
      void dfs(int step){
	if(/*跳出循环的条件*/){
		return;
	}
	for(/*对现有条件进行罗列*/){
		if(/*判断是否合法*/){
    	//将条件修改
    	dfs(/*新的step*/)
    	//回溯
	}    
}
    • bfs
      • 适合搜索最短径路的解
      • 模版
      void bfs(){
	while(!q.empty()){
		/*取出队首*/=q.top()
		q.pop()
		for(/*条件*/){
			if(/*合法*/){
				//标记
				q.push(/*新的情况*/)
			}
		}
	}
}
    • （最优性/可行性）剪枝
      • 最优性剪枝：已经比当前最优解不优了，回溯
      • 可行性剪枝：发现分支已经无法到达递归边界，回溯
        • 奇偶性剪枝 例题：骨头的诱惑
    • 记忆化搜索
      • 搜索过这个状态了，再往下搜会重复，所以不继续搜

  • 动态规划（$dp$） 掌握情况：80%

    • 使用条件
      • 最优子结构性质
      • 无后效性
    • 背包

      • 01 背包（拿或不拿） f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+v[i])

      • 多重背包（物品有各自的数量） 二进制优化(W=2^0+2^1+2^2+...+2^k+t) 后转化成01背包

      • 完全背包（无穷多物品数量） f[i][j]=max(f[i-1][j],f[i][j-c[i]]+v[i]) 遍历倒序

      • 一维优化：01倒序，完全正序（因为正序遍历会重复取）

    • 最长上升/下降/不上升/不下降子序列
      • 模版（求最长上升子序列） if(a[i]>a[j]) f[i]=max(f[i],f[j]+1)
      • Dilworth 定理：每组单调不增的最少组数=最长上升子序列长度（其他同理）
    • 区间dp
      • 通过合并小区间的最优解进而得出整个大区间上最优解
      • 模版
      for(int len=2;len<=n;len++){
	for(int l=1;l+len-1<=n;l++){
		int r=l+len-1;
		for(int k=l;k<=r;k++){
			dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+/*价值*/;
		}
	}
}
    • 贪心背包

  • 数论 掌握情况：98%

    • 同余
      • a mod c = b mod $c$，则 a \equiv b mod c
    • 质数、因数
      • 埃式筛、欧式筛求质数/最小质因子
        • 模版
        for(int i=2;i<=N;i++){
	if(is_prime[i]==0){
		min_prime[i]=i;
		if(i<sqrt(1e7)){
			for(int j=i*i;j<=N-1;j+=i){
				is_prime[j]=1;
				if(min_prime[j]==0){
					min_prime[j]=i;
				}
			}
		}
	}
}
      • gcd/lcm
        • 辗转相除法/辗转相减
          • 模版（辗转相除）
          if(b!=0) return gcd(b,a%b);
else return a;
        • lcm(a,b)=\frac{a \times b}{gcd(a,b)}
    • 快速幂（快速计算 a^b%c)
      • 龟速乘：把快速幂的乘化成加。
      • 模版
      long long mi(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;
		y>>=1;
	}
	return ans;
}
    • 组合数
      • C^m_n=\frac{n!}{m! \times (n-m)!}
      • 递推法：$C[i][j]=C[i-1][j]+C[i-1][j-1]$

  • 图论 掌握情况：99%

    • 树（一种特殊的图）
      • 性质：
        1. N 个结点，$N-1$ 条边
        2. 一个结点最多有一个入度。只有一个节点入度为0。
        3. 遍历序列唯一
      • 二叉树（一种特殊的树）
        • 遍历：前/中/后序遍历（根左右/左根右/左右根）
        • 完全/满/搜索/排序 二叉树（特殊的二叉树）
      • 哈夫曼树
        • 定义：带权路径长度（结点到树根之间的路径长度与结点上权的乘积）最小的二叉树
        • 应用：哈夫曼编码，出现频率小的在下方
    • 图的遍历：dfs（带环图不适用）/bfs
    • 一些变化
      • 树上贪心 例题：能量树
      • 奇偶最短路 例题：加工零件

  • 容易犯的低级错误汇总

    • i写成j，n写成m
    • 精度问题
      • long long n，但是输入scanf("%d",n)
      • long long ans=0ll;（一大坑点！！！）

改进

动态规划的掌握度较低（大部分是递推式推导的部分）。方法：多总结状态设计方法和思路+多做题。

8 个赞