贪婪算法（Greedy Algorithm） 1. 基本思想 每一步都做当前看来最优的选择（即局部最优），希望通过一系列局部最优，达到整体最优。 特点是只顾眼前（每次选择最优），不回溯。 2. 贪婪问题分类 绝对贪婪问题： 每一步的局部最优选择，最终一定得到全局最优解。 例子：活动安排问题、最小生成树问题。 相对贪婪问题： 贪婪算法得到的解不是全局…

分治算法 分治思想： 分治算法是一种将一个复杂问题分解成多个较小的子问题，通过递归解决子问题，再将子问题的解合并起来，得到原问题的解。分治思想的核心是通过将问题规模减小、分解和组合来简化问题的解决。 分治算法的基本步骤： 分解：将问题划分为多个规模较小、结构与原问题类似的子问题。 解决：递归地解决这些子问题，当子问题的规模足够小或问题简单时，可以直…

读入带空格的字符串 char str[1024]; scanf("%[^\n]",&str); // 读取到'\n'为止，不读入'\n' getchar(); // 清除'\n' int num; string str; cin >> num; // 读取数字 …

原文链接：https://rentry.org/5p2wa89m/edit 首先是蓝桥杯的注意事项： 比赛前试好鼠标、键盘等设备，有问题要举手告诉监考老师 先想清楚思路怎么做再写代码，防止题目读假了。 请将题目通读完以后，再开始深入思考开始写你认为最容易的一道题。 为了方便，可以使用万能头文件 **#include ** 一维 int 型数组记最大…

acwing799最长连续不重复子序列 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n; int q[N]; int cnt[N]; int main() { std::ios::sync_with_stdio(0); std::cin.tie…

算法概述 算法的5大特性 确定性:算法的每一步骤必须有明确的定义，无二义性。即在相同输入下，每次执行都应得到相同的结果。 能行性:算法的每一步都必须是可实现的，即在有限时间内能用有限资源完成。 输入：算法可以有零个或多个输入，输入是算法处理的初始数据。 输出：算法必须有一个或多个输出，输出是算法处理的结果。 有穷性/有限性：算法必须在执行有限步骤后…

原题单链接：https://www.luogu.com.cn/training/111#problems AcWing789. 数的范围 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, q, a[N]; int bs1(i…

原题单链接：https://rentry.org/ozd34yrn 例题 重述问题 找到最后一步 去掉最后一步，是否能划分出子问题 考虑边界 746. 使用最小花费爬楼梯 const int N=1010; class Solution { public: int mem[N]; int dfs(vector<int>& cos…

#include <bits/stdc++.h> using namespace std; const int N = 10010; int fa[N]; inline void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i; } inline int find(int …

#include<bits/stdc++.h> using namespace std; const int N = 10010; int a[N], s[N]; int n; int main(){ cin >> n; for (int i = 1; i <= n; i ++ ){ cin >> a[i]…