蓝桥杯学习笔记
AI-摘要
YouduAI GPT
AI初始化中...
介绍自己
生成本文简介
推荐相关文章
前往主页
前往tianli博客
个人代码库: 蓝桥杯代码仓库
在备考蓝桥杯的过程中，我的编程能力得到了显著提升。通过系统的学习和练习，我接触到了许多之前未曾了解的算法和数据结构，这些知识不仅拓宽了我的技术视野，也为我未来的职业发展奠定了坚实的基础。
第一章：语言基础
2. 竞赛常用库函数
1) sort 对 vector<int>排序用法，自定比较函数
#include<bits/stdc++.h>
using namespace std;
bool cmp(const int& u, const int& v) {
return u > v;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// 初始化 v
vector<int> v = { 5, 1, 3, 9, 11 };
// 对数组进行排序， 降序排序，默认是升序，所以需要自定义比较函数
sort(v.begin(), v.end(), cmp);
// 输出
for (int i = 0; i < v.size(); i++) { cout << v[i] << ' '; }
system("pause");
return 0;
}2) nth_element 找出第几大的数
#include<bits/stdc++.h>
using namespace std;
int main() {
// 初始化一个整数向量v，包含一些无序的整数
vector<int> v = { 5, 1, 7, 3, 10, 18, 9 };
// 使用nth_element函数找出第四大的数
// nth_element将第4个位置（索引为3）的元素调整到它最终应该在的位置
// 使得从开始到该位置的所有元素都不大于这个元素，而后面的元素都不小于这个元素
nth_element(v.begin(), v.begin() + 3, v.end());
// 输出调整后的向量v中的元素
for (auto& i : v) cout << i << ' ';
// 暂停程序，等待用户操作
system("pause");
return 0;
}3) max_element，min_element找出数组的最大值和最小值
#include<bits/stdc++.h> // 包含所有标准库头文件
using namespace std; // 使用标准命名空间
using ll = long long; // 定义长整型别名
const int N = 1e4 + 9; // 定义常量N，值为10009
int a[N]; // 定义数组a，大小为N
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 优化输入输出速度
int n; cin >> n; // 读取整数n
for (int i = 1; i <= n; i++) cin >> a[i]; // 读取n个整数到数组a中
// 输出数组a中的最大值和最小值
cout << *max_element(a + 1, a + 1 + n) << endl;
cout << *min_element(a + 1, a + 1 + n) << endl;
ll sum = 0; // 初始化sum为0
for (int i = 1; i <= n; i++) sum += a[i]; // 计算数组a的元素总和
// 输出平均值，保留两位小数
cout << fixed << setprecision(2) << 1.0 * sum / n << endl;
system("pause"); // 暂停程序，等待用户操作
return 0; // 返回0，表示程序正常结束
}
4）二分查找binary_search，lower_bound和upper_bound用法和实际应用
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> v = { 5, 1, 8, 3, 10, 18, 9 };
sort(v.begin(), v.end());
for (auto& i : v) cout << i << ' ';
// binary_search
cout << endl << "please input target: ";
int target;
cin >> target;
bool found = binary_search(v.begin(), v.end(), target);
if (found) cout << "target found\n";
else cout << "target not found\n";
// lower_bound(st, ed, x), 第一个大于等于x的元素地址
cout << lower_bound(v.begin(), v.end(), 8) - v.begin() << endl;
// upper_bound(st, ed, x), 第一个大于x的元素地址
cout << upper_bound(v.begin(), v.end(), 8) - v.begin() << endl;
// 实际应用，用 upper_bound - lower_bound 可以找出数组中某个元素重复的次数以及所在的区间
system("pause");
return 0;
}5）用lower_bound函数找出数组内的某个数的下标
#include<bits/stdc++.h>
using namespace std;
int main() {
// 初始化一个大小为200的整数数组data
int data[200];
// 使用公式4 * i + 6填充数组data，其中i从0到199
for (int i = 0; i < 200; i++) data[i] = 4 * i + 6;
// 读取用户输入的目标值target
int target; cin >> target;
// 使用lower_bound函数在数组data中查找第一个不小于target的元素的位置
// lower_bound返回一个指向该位置的指针，通过减去data的起始地址得到索引
cout << lower_bound(data, data + 200, target) - data << endl;
// 暂停程序，等待用户操作
system("pause");
return 0;
}6）使用库函数实现字母大小写转换
#include<bits/stdc++.h>
using namespace std;
char convertedCh(char ch) {
if (islower(ch)) ch = toupper(ch);
else ch = tolower(ch);
return ch;
}
int main() {
string s; getline(cin, s);
for (auto& i : s) i = convertedCh(i);
cout << s << endl;
system("pause");
return 0;
}7）next_permutation，prev_permutation函数
使用next_permutation，prev_permutation函数生成一个序列的下一个和上一个字典序排列。
#include<bits/stdc++.h>
using namespace std;
int main() {
// 初始化一个整数向量nums，包含元素1, 2, 3
vector<int> nums = { 1, 2, 3 };
cout << "initial permutation: ";
// 输出初始排列
for (int num : nums) cout << num << ' ';
cout << endl;
// 使用next_permutation函数生成下一个字典序排列
// next_permutation会将nums重新排列为下一个更大的排列，直到没有更大的排列为止
while (next_permutation(nums.begin(), nums.end())) {
cout << "next permutation: ";
// 输出每次生成的下一个排列
for (int num : nums) cout << num << " ";
cout << endl;
}
// 初始化另一个整数向量nums2，包含元素3, 2, 1
vector<int> nums2 = { 3, 2, 1 };
cout << "initial permutation: ";
// 输出初始排列
for (int num : nums2) cout << num << ' ';
cout << endl;
// 使用prev_permutation函数生成上一个字典序排列
// prev_permutation会将nums2重新排列为上一个更小的排列，直到没有更小的排列为止
while (prev_permutation(nums2.begin(), nums2.end())) {
cout << "prev permutation: ";
// 输出每次生成的上一个排列
for (int num : nums2) cout << num << " ";
cout << endl;
}
// 暂停程序，等待用户操作
system("pause");
return 0;
}
/* 输出结果
initial permutation: 1 2 3
next permutation: 1 3 2
next permutation: 2 1 3
next permutation: 2 3 1
next permutation: 3 1 2
next permutation: 3 2 1
initial permutation: 3 2 1
prev permutation: 3 1 2
prev permutation: 2 3 1
prev permutation: 2 1 3
prev permutation: 1 3 2
prev permutation: 1 2 3
请按任意键继续. . .
*/8）其他基础常用函数
#include<bits/stdc++.h> // 包含几乎所有标准库头文件，方便快速编写代码，但在实际项目中不推荐使用
using namespace std;
int main() {
// 声明一个大小为5的整数数组a
int a[5];
// 使用memset函数将数组a的所有字节设置为0x3f（即二进制的00111111）
memset(a, 0x3f, sizeof(a)); // 00111111
// 输出数组a中每个元素的二进制表示形式
for (int i = 0; i < 5; i++) cout << bitset<32>(a[i]) << endl;
// swap(a,b) 注释掉的代码，用于交换两个变量的值
// reverse(v.begin(), v.end()) 注释掉的代码，用于反转容器v的元素顺序
// unique() 去除相邻重复元素，返回去重后范围的尾后迭代器
// 并不是删除重复元素，而是将重复元素移到后面
int arr[] = { 1,1,2,2,3 };
// 输出数组arr中的每个元素
for (int i = 0; i < 5; i++) cout << arr[i];
cout << endl;
// 使用unique函数去除数组arr中的相邻重复元素，并获取去重后的有效长度n
int n = unique(arr, arr + 5) - arr;
// 再次输出数组arr中的每个元素，注意此时数组arr中重复元素被移到了后面
for (int i = 0; i < 5; i++) cout << arr[i];
cout << endl;
// system("pause") 在Windows系统中暂停程序，等待用户按键继续
system("pause");
return 0;
}3. STL
1）Pair
pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，所以可以直接使用pair的成员变量。
#include<bits/stdc++.h>
using namespace std;
struct Person
{
string name;
int age;
};
int main() {
pair<char, string> p1('a', "hello, world");
cout << p1.first << " ," << p1.second << endl;
// pair嵌套使用
pair<int, pair<int, int>> p2(3, make_pair(4, 5));
cout << p2.first << ", " << p2.second.first << ", " << p2.second.second << endl;
// 结合构造体和vector容器一起使用
vector<Person> people;
people.push_back({ "wxy",18 });
people.push_back({ "lb",19 });
people.push_back({ "zf",28 });
for (auto& i : people) cout << "name: " << i.name << ", " << "age: " << i.age << endl;
vector<pair<Person, int>> sourse;
sourse.push_back({ people[0],81 });
sourse.push_back({ people[1],89 });
sourse.push_back({ people[2],99 });
for (auto& i : sourse) cout << "name: " << i.first.name << ", age: " << i.first.age << ", sourse: " << i.second << endl;
system("pause");
return 0;
}
2）Vector
是一个动态数组容器，属于标准模板库（STL）的一部分。它提供了一种灵活且高效的方式来存储和操作一组元素，具有动态大小调整、连续内存存储、随机访问和迭代访问等特点。通过下标运算符[]或at()方法可以随机访问元素，使用迭代器或范围for循环可以遍历元素。vector支持添加、删除、插入和清空等操作，并能够自动管理内存，当需要更多空间时会自动重新分配内存并复制原有元素 详细见
常用函数：获取长度 size()； 末尾元素添加 push_back()；末尾元素删除 pop_back()；指定位置插入元素insert() ；指定位置删除元素erase()；检查是否为空函数 empty()； 调整大小函数 resize()。还可以使用 begin()，end()函数遍历元素(获取的是初始或末尾元素的迭代器)
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> numbers = { 5,2,8,5,1,2,9,8 };
// 输出原始容器
for (const auto& number : numbers) cout << number << " ";
cout << endl;
// 末尾新增元素
numbers.push_back(6);
// 容器排序
sort(numbers.begin(), numbers.end());
// 输出排序后的容器
for (const auto& number : numbers) cout << number << " ";
cout << endl;
// 去除重复元素，unique(numbers.begin(), numbers.end())返回的是去重后的重复集合的首地址
numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());
// 输出去重后的容器
for (const auto& number : numbers) cout << number << " ";
cout << endl;
// 想容器中插入元素, 在指定位置插入元素，该位置原有的元素整体往后移
numbers.insert(numbers.begin() + 2, 3);
// 输出插入元素后的容器
for (const auto& number : numbers) cout << number << " ";
cout << endl;
system("pause");
return 0;
}3）List
是一种双向链表容器，属于标准模板库（STL）的一部分。它提供了一种灵活且高效的方式来存储和操作一组元素，具有动态大小调整、双向迭代器、随机访问和迭代访问等特点。通过迭代器可以遍历元素，使用front()和back()方法可以访问链表的首尾元素。list支持添加、删除、插入和清空等操作，并能够自动管理内存，当需要更多空间时会自动重新分配内存并复制原有元素。详细见
List常用函数。由于是双向的迭代器，所以相比于vector多了几个对头部操作的函数，其他的基本一致
#include<bits/stdc++.h>
using namespace std;
int main() {
cout << "用得少，基本用不到，作为了解学习\n";
// 尾部插入元素
list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
// 链表头部插入元素
mylist.push_front(0);
// 遍历输出
for(int num:mylist){
cout << num << endl;
}
system("pause");
return 0;
}4）Stack
stack是一个标准模板库（STL）容器适配器，用于实现栈数据结构。它提供了一种后进先出（LIFO）的数据管理方式。stack支持基本的栈操作，如压入元素（push）、弹出元素（pop）、访问栈顶元素（top）、检查栈是否为空（empty）以及获取栈的大小（size）。它通常用于需要按特定顺序处理元素的场景，例如函数调用、表达式求值和深度优先搜索等算法。注意：stack是STL中唯一一个后进先出的迭代器，其他都是先进先出（FIFO）且 stack 不能遍历
小tips：如果将一个数组的元素依次放入栈，再依次取出，则可以将数组翻转
常用函数
代码示例：
#include<bits/stdc++.h>
using namespace std;
int main() {
cout << "仅做了解即可\n";
stack<int> myStack;
// 插入元素
myStack.push(10);
myStack.push(20);
myStack.push(30);
myStack.push(40);
// 获取元素
cout << "栈顶元素" << myStack.top() << endl;
// 弹出栈顶元素
myStack.pop();
// 弹出栈顶元素后再获取栈顶元素
cout << "弹出第一个元素后的栈顶元素为: " << myStack.top() << endl;
// 检查栈是否为空
if(myStack.empty()) cout << "栈为空" << endl;
else cout << "栈不为空" << endl;
// 获取栈的大小
cout << "栈的大小为: " << myStack.size() << endl;
system("pause");
return 0;
}5）Queue
1、queue
常用函数，注意：queue只能操作头部和尾部的元素，无法操作中间的元素
代码示例
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int m; cin >> m;
queue<string> V, N;
while (m--) {
string op; cin >> op;
if (op == "IN") {
string name, q; cin >> name >> q;
if (q == "V") V.push(name);
else N.push(name);
}
else {
string q; cin >> q;
if (q == "V") V.pop();
else N.pop();
}
}
// 输出测试,
cout << "输出结果: " << endl;
while (V.size()) {
cout << V.front() << endl;
V.pop();
}
while (N.size()) {
cout << N.front() << endl;
N.pop();
}
system("pause");
return 0;
}
/* 输入样例 输出 M 次操作后 VIP 窗口队列和普通窗口队列中的姓名(从头到尾)，先输出 VIP 窗口队列后输出普通窗口队列。
5
IN xiaoming N
IN Adel V
IN laozhao N
OUT N
IN CLZ V
*/2、priority_queue
priority_queue 与普通队列不同，priority_queue中的元素是按照一定的优先级进行排序的
默认情况下，priority_queue按照元素的值从大到小进行排序，即最大元素位于队列的前面
当然也可以自定义比较函数实现从小到大
优先级队列是一个十分重要的数据结构，考察评率极高，下面是优先队列常用函数
代码示例：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n; cin >> n;
// priority_queue 优先队列，自动排序，默认大的在栈顶
priority_queue<ll, vector<ll>, greater<ll>> pq; // greater<ll>自带的重载，实现小根堆，小的在栈顶
for (int i = 1; i <= n; i++) {
ll x; cin >> x;
pq.push(x);
}
ll ans = 0;
while (pq.size() >= 2) {
// 取出两个小栈顶，并弹出
ll x = pq.top(); pq.pop();
ll y = pq.top(); pq.pop();
ans += x + y; // 将两个小栈顶相加再推入优先队列
pq.push(x + y);
}
cout << ans << endl;
system("pause");
return 0;
}
// 关于优先队列详解见 https://blog.csdn.net/qq_42978535/article/details/1426972243、deque
deque双端队列，可以实现两端进行高效的插入和删除（两端能进能出）
常用函数： deque可以实现对中间元素进行操作，当然用的比较少，仅做了解即可
6）Set
1、set集合
set是一种容器，用于存储一组唯一的元素，并按照一定的排序规则进行排序。set中的元素默认是按照升序排序的，默认情况下它使用元素的比较运算符(<)来进行排序。注意：set的元素都是唯一的，不允许重复元素存在，当插入一个重复元素时，set会自动忽略该元素
常用函数示例：
代码示例（修改set比较方法的常见手段）
#include<bits/stdc++.h>
using namespace std;
struct MyCompare
{
bool operator()(const int& a, const int& b) const {
// 自定义比较逻辑
return a > b; // 改为降序
}
};
int main() {
// set<int> mySet; // 默认升序
set<int, greater<int>> mySet; // 使用自带的greater改为降序
set<int, MyCompare> mySet2; // 在 mySet2里面自定义比较函数MyCompare
mySet.insert(25); mySet2.insert(25);
mySet.insert(17); mySet2.insert(17);
mySet.insert(39); mySet2.insert(39);
mySet.insert(42); mySet2.insert(42);
for(const auto& elem : mySet) cout << elem << " ";
cout << endl;
for(const auto& elem2 : mySet2) cout << elem2 << " ";
system("pause");
return 0;
}set常用操作
#include<bits/stdc++.h>
using namespace std;
int main() {
set<int> myset;
// 插入元素
myset.insert(5);
myset.insert(2);
myset.insert(8);
myset.insert(2); // 重复元素
// 遍历集合
cout << "set element: ";
for(const auto& elem : myset) cout << elem << " ";
cout << endl;
// 查找元素
int target = 5;
auto it = myset.find(target); // 找到则返回该元素迭代器，找不到则返回end()
if(it != myset.end()) cout << target << " found in the set. " << endl;
else cout << target << " not found in the set. " << endl;
// 移除元素
int remValue = 2;
myset.erase(remValue);
// 再次遍历
for(const auto& elem : myset) cout << elem << " ";
cout << endl;
// 清空集合
myset.clear();
// 判断集合是否为空
if(myset.empty()) cout << "set is empty" << endl;
else cout << "set is not empty" << endl;
system("pause");
return 0;
}2、multiset多重集合
大体与set类似，不同之处在于multiset容器允许存储相同的元素
常用函数，注意： erase() 函数，由于存在相同的元素，所以在删除某个元素时，需不需将容器内与其等值的元素全部删除，可以使用 st.erase(st.find(x)) 来实现删除单个元素
multiset常见操作示例
#include<bits/stdc++.h>
using namespace std;
int main() {
multiset<int> myset;
// 插入元素
myset.insert(5);
myset.insert(2);
myset.insert(8);
myset.insert(2); // 重复元素
// 遍历集合
cout << "set element: ";
for(const auto& elem : myset) cout << elem << " ";
cout << endl;
// 查找元素
int target = 5;
auto it = myset.find(target); // 找到则返回该元素迭代器，找不到则返回end()
if(it != myset.end()) cout << target << " found in the set. " << endl;
else cout << target << " not found in the set. " << endl;
// 移除元素
int remValue = 2;
// myset.erase(remValue); // 删除所有的2
myset.erase(myset.find(2)); // 删除单个2
// 再次遍历
for(const auto& elem : myset) cout << elem << " ";
cout << endl;
// 清空集合
myset.clear();
// 判断集合是否为空
if(myset.empty()) cout << "set is empty" << endl;
else cout << "set is not empty" << endl;
system("pause");
return 0;
}3、unordered_set 无序集合
unordered_set是一种容器，用于存储一组唯一的元素，并且没有特定的顺序。unordered set容器使用哈希表来实现元素的存储和访问，因此元素的插入、删除和査找的时间复杂度都是常数时间，即0(1)，当然，这个其实并不绝对，最坏也可能到 O(n)。所以一般情况下，很少使用 无序集合
7）Map
1、map
map是一种关联容器，用于存储一组键值对(key-value pairs)，其中每个键(key)都是唯一的。
map容器根据键来自动进行排序，并且可以通过键快速查找对应的值。
map容器使用红黑树(Red-Black Tree)数据结构来实现，具有较快的插入、删除和査找操作的时间复杂度0(logn) map需要重点掌握
常用函数
代码示例
#include<bits/stdc++.h>
using namespace std;
int main() {
map<int, string> mymap = {{1,"Apple"}, {2, "Banana"}, {3, "Orange"}};
// 插入元素
mymap.insert(make_pair(4, "Xiaomi"));
mymap.insert({5, "H3C"});
// 遍历并打印map中的元素
for(const auto& pair : mymap)
cout << "Key: " << pair.first << ", Value: " << pair.second << endl;
// 删除元素
mymap.erase(3);
// 判断元素是否存在 (key为3存不存在)
if(mymap.count(3) == 0) cout << "key 3 not found" << endl;
else cout << "key 3 founded" << endl;
// 清空元素
mymap.clear();
// 判断 map 是否为空
if(mymap.empty()) cout << "map is empty" << endl;
else cout << "map is not empty";
system("pause");
return 0;
}2、multimap
相比于map，不同之处在于可以存在多个相同的键 multimap几乎不用
代码示例：
#include<bits/stdc++.h>
using namespace std;
int main() {
multimap<int, string> mymap = {{1,"Apple"}, {2, "Banana"}, {2, "Orange"}};
// 插入元素
mymap.insert(make_pair(3, "Xiaomi"));
mymap.insert({3, "H3C"});
// 查找和访问元素
auto range = mymap.equal_range(2);
for(auto it = range.first; it != range.second; it++){
cout << "key: " << it->first << ", value: " << it->second << endl;
}
// 遍历并打印map中的元素
cout << "------------------" << endl;
for(const auto& pair : mymap)
cout << "Key: " << pair.first << ", Value: " << pair.second << endl;
// 删除元素
mymap.erase(mymap.find(3)); // 只会删除一个，如果直接写3则删除所有key为3的键值对
// 判断元素是否存在 (key为3存不存在)
if(mymap.count(3) == 0) cout << "key 3 not found" << endl;
else cout << "key 3 founded" << endl;
// 清空元素
mymap.clear();
// 判断 map 是否为空
if(mymap.empty()) cout << "map is empty" << endl;
else cout << "map is not empty";
system("pause");
return 0;
}3、unordered_map
无序，插入删除速度更快，但这个一般不用（复杂度不稳定）
8）例题
1、考察优先队列 priority_queue
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
// 小蓝吃糖果
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n; cin >> n;
priority_queue<int> pq;
ll sum = 0;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
pq.push(x);
sum += x;
}
ll mx = pq.top();
if (sum - mx >= mx - 1) cout << "Yes" << '\n';
else cout << "No" << '\n';
return 0;
}
/*
不能连续两次吃一种，为了消除种类最多的糖果，可以采用下面隔一个吃最多的那种
可以发现规律， 把4消耗完，中间需要缓冲的次数为 4 - 1，其他种类总数大于或者等于3即可存在刚好吃完的场景
4 2 1 1
3 2 1 2
3 1 1 1
2 1 1 2
2 0 1 1
1 0 1 3
1 0 0 1
0 0 0
4 3 1 1
3 3 1 2
3 2 1 1
2 2 1 2
2 1 1 1
1 1 1 2
1 0 1 1
0 0 1 3
0 0 0
4 3 3 1
3 3 3 2
3 2 3 1
2 2 3 3
2 2 2 1
1 2 2 2
1 1 2 3
1 1 1 1
0 1 1 2
0 0 1 3
0 0 0
*/2、考察栈 stack，小蓝的括号串
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
stack<char> stk;
char s[N];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n; cin >> n;
cin >> s + 1;
bool ans = true;
for (int i = 1; i <= n; i++) {
if (s[i] == '(') stk.push(s[i]);
else {
if (stk.size()) stk.pop();
else ans = false;
}
}
if (stk.size()) ans = false;
cout << (ans ? "Yes" : "No") << endl;
system("pause");
return 0;
}3、1531 快递分拣，考察 map vector
#include<bits/stdc++.h>
using namespace std;
map<string, vector<string>> mp;
vector<string> citys;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n; cin >> n;
for (int i = 1; i <= n; i++) {
string a, b; cin >> a >> b;
if (!mp.count(b)) citys.push_back(b);
mp[b].push_back(a);
}
cout << "-----------------------------------------------" << endl;
for (const auto& city : citys) {
cout << city << ' ' << mp[city].size() << endl;
for (const auto& i : mp[city]) cout << i << endl;
}
system("pause");
return 0;
}第二章 基础语法
1、基础算法
1. 枚举
枚举算法是一种基本的算法思想，它通过穷举所有可能的情况来解决问题。它的基本思想是将问题的解空间中的每个可能的解都枚举出来，并进行验证和比较，找到满足问题条件的最优解或者所有解。
枚举算法适用于问题规模较小、解空间可穷举的情况。它的优点是简单直观，不需要复杂的数学推导，易于实现。但是，由于需要穷举所有可能的情况，对于问题规模较大的情况，枚举算法的时间复杂度可能会非常高，效率较低。
1. 找超半数
// 在 n×m 的矩阵中，找出超半数 https://www.lanqiao.cn/problems/3227/learning/
#include<bits/stdc++.h>
using namespace std;
map<int, int> mp;
int main(){
ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
int m,n;
cin >> m >> n;
for(int i = 0; i < m * n; i++){
int x; cin >> x;
mp[x]++;
}
for(const auto& p : mp){
if(p.second * 2 > m * n ) cout << p.first << endl;
}
return 0;
}
/*
3 3
1 2 3
2 2 2
1 2 2
*/2. 模拟
1.模拟算法通过模拟实际情况来解决问题，容易理解但实现复杂，需要注意细节。 2.模拟题不涉及太难的算法，由许多简单的部分组成，考察选手的细心程度和逻辑思维。 3.为了逻辑清晰，常使用小函数来帮助解题，如整数和字符串的相互转化、日期和特殊条件的判断。 4.模拟算法不卡时间复杂度，主要考察细心程度。
1、扫雷问题
// 扫雷 https://www.lanqiao.cn/problems/549/learning/
#include<bits/stdc++.h>
using namespace std;
const int N = 150;
int mp[N][N], ans[N][N];
int main(){
int n, m; cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> mp[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(mp[i][j] == 1){
ans[i][j] = 9;
continue;
}
for(int _i = max(1, i - 1); _i <= min(n, i + 1); _i++){
for(int _j = max(1, j - 1); _j <= min(m, j + 1); _j++){
if(mp[_i][_j]) ans[i][j]++;
}
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout << ans[i][j] << " ";
}
cout << endl;
}
return 0;
}
/* 测试用例
3 4
0 1 0 0
1 0 1 0
0 0 1 0
*/2、灌溉问题
// https://www.lanqiao.cn/problems/551/learning/ 灌溉问题
#include<bits/stdc++.h>
using namespace std;
const int N = 120;
bool a[N][N], b[N][N];
int main() {
int n, m; cin >> n >> m;
int t; cin >> t;
for(int i = 1; i <= t; i++){
int x,y; cin >> x >> y;
a[x][y] = 1;
}
int k; cin >> k;
while(k--){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
// 为什么要再开一个b ???
if(a[i][j]) b[i][j] = b[i][j-1] = b[i][j+1] = b[i-1][j] = b[i+1][j] = 1;
// if(a[i][j]) a[i][j-1] = a[i][j+1] = a[i-1][j] = a[i+1][j] = 1; // error
}
}
// 将b复制回a
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
a[i][j] = b[i][j];
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j]) ans++;
}
}
cout << ans << endl;
return 0;
}3、回文日期问题
2、排序
3、省赛技巧与复习
基础复习完后，以刷题为主，后续可能不再更新这篇笔记
算法小记
1. 离散数组
// 离散化数组
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int a[N];
vector<int> L;
int getidx(int x){ // 找元素下标
return lower_bound(L.begin(), L.end(), x) - L.begin();
}
int main() {
int n; cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) L.push_back(a[i]);
sort(L.begin(), L.end()); // 排序
L.erase(unique(L.begin(), L.end()), L.end()); // 去重
cout << "离散化数组为: ";
for(const auto &i : L) cout << i << ' ';
cout << "\n";
int v; cin >> v;
cout << getidx(v) << "\n";
return 0;
}
/* test samples
7
108 312 21321 3213 8888 343 8888
*/2. DFS(回溯法模版)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int a[N]; // 存储排列结果
bool vis[N]; // 标记数字是否被访问过
int n; // 排列的大小
// 回溯函数，dep表示当前处理到第几个数字
void dfs(int dep) {
if (dep == n + 1) { // 如果已经处理完所有数字
for (int i = 1; i <= n; i++) { // 输出排列
cout << a[i] << " \n"[i==n];
}
return;
}
for (int i = 1; i <= n; i++) { // 尝试将1到n的每个数字放入当前位置
if (vis[i]) continue; // 如果该数字已经被使用，跳过
vis[i] = true; // 标记该数字为已使用
a[dep] = i; // 将数字放入当前位置
dfs(dep + 1); // 递归处理下一个位置
vis[i] = false; // 回溯，恢复状态
}
}
int main() {
cin >> n; // 输入排列的大小
dfs(1); // 从第一个位置开始递归
return 0;
}2.1 回溯法经典样题1
// lanqiao1508 N皇后问题
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int n, ans;
int vis[N][N];
void dfs(int dep){
if(dep == n + 1){
ans++;
return;
}
for(int i = 1; i <= n; i++){ // 为什么下面只标记同一行，因为每次搜寻时只会在同一行(深度)寻找一个皇后
if(vis[dep][i]) continue; // 所以只需要排除某行某个元素的同一列即可
// 修改状态
for(int _i = 1; _i <= n; _i++) vis[_i][i]++; // 标记同一列
// 表壳 X 形模版
for(int _i = dep, _j = i; _i >= 1 && _j >= 1; _i--, _j--) vis[_i][_j]++; // 标记左上对角线
for(int _i = dep, _j = i; _i <= n && _j >= 1; _i++, _j--) vis[_i][_j]++; // 标记右上对角线
for(int _i = dep, _j = i; _i >= 1 && _j <= n; _i--, _j++) vis[_i][_j]++; // 标记左下对角线
for(int _i = dep, _j = i; _i <= n && _j <= n; _i++, _j++) vis[_i][_j]++; // 标记右下对角线
// 搜查下一深度
dfs(dep + 1);
// 恢复现场
for(int _i = 1; _i <= n; _i++) vis[_i][i]--;
for(int _i = dep, _j = i; _i >= 1 && _j >= 1; _i--, _j--) vis[_i][_j]--;
for(int _i = dep, _j = i; _i <= n && _j >= 1; _i++, _j--) vis[_i][_j]--;
for(int _i = dep, _j = i; _i >= 1 && _j <= n; _i--, _j++) vis[_i][_j]--;
for(int _i = dep, _j = i; _i <= n && _j <= n; _i++, _j++) vis[_i][_j]--;
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
dfs(1);
cout << ans << '\n';
return 0;
}
/* test samples
5
*/2.2回溯法经典样体2
// lanqiao182 小朋友崇拜圈
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], dfn[N], idx, mindfn;
int dfs(int x){
dfn[x] = ++idx;
if(dfn[a[x]]){
if(dfn[a[x]] >= mindfn) return dfn[x] - dfn[a[x]] + 1;
return 0;
}
return dfs(a[x]);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int ans = 0;
for(int i = 1; i <= n; i++){
if(!dfn[i]){
mindfn = idx + 1;
ans = max(ans, dfs(i));
}
}
cout << ans << endl;
return 0;
}
/* test samples
9
3 4 2 5 3 8 4 6 9
*/2.2回溯法经典样体3
// lanqiao178 全球变暖
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
char mp[N][N];
int n, scc, col[N][N];
bool vis[N*N];
// 移动向量
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void dfs(int x, int y){
col[x][y] = scc;
for(int i = 0; i < 4; i++){
int nx = x + dx[i], ny = y + dy[i];
if( col[nx][ny] || mp[nx][ny] == '.') continue; // 不需要判断nx, ny是否在地图里面，因为地图边缘都是海洋
dfs(nx ,ny);
}
}
int main(){
ios::sync_with_stdio, cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> mp[i] + 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(col[i][j] || mp[i][j] == '.') continue;
scc++; // scc表示当前颜色编号
dfs(i, j);
}
}
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(mp[i][j] == '.') continue;
bool tag = true;
for(int k = 0; k < 4; k++){
int x = i + dx[k], y = j + dy[k];
if(mp[x][y] == '.') tag = false;
}
if(tag){
if(!vis[col[i][j]]) ans++;
vis[col[i][j]] = true;
}
}
}
cout << scc - ans << '\n';
return 0;
}
/* test samples
7
.......
.##....
.##....
....##.
..####.
...###.
.......
*/3. DFS剪枝
- 感谢你赐予我前进的力量
-
微信 
支付宝
赞赏者名单
因为你们的支持让我意识到写文章的价值🙏
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
最近发布