没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
内容概要:本文档详细介绍了编程竞赛中常见的基础算法,重点讲解了C++输入输出优化方法,以及常用的数据结构如堆、哈希表、图、二叉树等的具体实现。具体内容包括高效读取和打印大量数据的方法,多维数组的操作技巧,各种典型算法的应用场景及实现细节,如前缀和、差分、深度优先搜索、广度优先搜索等。 适合人群:具备基本编程技能的大学生、编程爱好者以及参加ACM等相关竞赛的学生。 使用场景及目标:帮助初学者理解和掌握编程竞赛的基础知识点和技术细节,提升解决问题的能力和代码效率。同时,文档中的实例和练习题可以帮助读者巩固所学内容。 阅读建议:在阅读过程中,建议读者跟随示例代码进行实践操作,理论结合实际,逐步提高编程能力和算法水平。
资源推荐
资源详情
资源评论






























基础算法.md
2023-09-16
1 / 172
Tips
输⼊输出
输⼊输出⼤于等于1e6使⽤scanf,否则使⽤cin
加速cin,但仍没有scanf快速
1.取消同步:
ios::sync_with_stdio(false);
std::cin.tie(0);
2.取消后不能使⽤scanf,只能cin
特殊样例的读⼊
#include <iostream>
#include <vector>
#include <sstream> // stringstream 分割字符串
#include <istream>
#include <string>
using namespace std;
// 数组以空格分割,已知只有三行,每行个数未知
// Sample Input
// 1 2 3 4 5
// 11 12 13 14 15
// 21 22 23 24 25
void test1()
{
vector<vector<int>> res(3);
for(int i = 0; i < 3; ++ i)
{
int a;
// 空白字符:空格,换行,tab
// cin 读入数据 1如果第一个读到空白字符,将忽略并清除这个空白字符
// 2如果第一个读到了非空白字符,将读入整个字符串或者字符,直到遇到空
白字符
// (但这个空白字符不会被清除,残留在缓冲区)或eof
while(cin >> a)
{
// if(a == '') break;
cout << "current:" << a << endl;
res[i].push_back(a);

基础算法.md
2023-09-16
2 / 172
}
}
cout << "res:" << endl;
for(auto &v : res)
for(auto &e : v){
cout << e << " ";
}
cout << endl;
}
// 未知数组长度,用 ',' 隔开
// Sample Input
// [1,2,3,4,5,6,7]
// [0,2,3,4,5,7,3]
void test2()
{
vector<int> v1,v2;
string s1,s2;
cin >> s1 >> s2;
cout << "s2=" << s2 << endl;
s1 = s1.substr(1,s1.size() - 2);
s2 = s2.substr(1,s2.size() - 2);
stringstream ss;
ss << s1;
string temp;
while (getline(ss,temp,','))
{
v1.push_back(stoi(temp));
}
ss.clear();
ss << s2;
while (getline(ss,temp,','))
{
v2.push_back(stoi(temp));
}
for(auto &e : v1) cout << e << " ";
cout << endl;
for(auto &e: v2) cout << e << " ";
cout << endl;
}
读⼊⼀个字符

基础算法.md
2023-09-16
3 / 172
使⽤
char op[2];
scanf("%s",&op); // 忽略回车等字符
⽽不是(因为会读⼊回车等字符)
char op;
scanf("%s",&op);
printf输出string
string s = "abc";
printf("%s",s.c_str()); // c_str()返回string s的首地址
清空没有clear函数的stl容器
queue ,priority queue ,stack 没有clear函数
q = queue<int>(); // 想要清空q,直接重新构造一个
c++默认⼤根堆
从⼩到⼤插⼊需要修改堆的次数少,因此greater是⼩根堆
priority_queue<int, vector<int>, less<int>>s;//less表示按照递减(从大到小)的顺序插入元
素 实现为大根堆(默认)
priority_queue<int, vector<int>, greater<int>>s;//greater表示按照递增(从小到大)的
顺序插入元素 实现为小根堆
数组越界什么错误都可能发⽣,把数组开⼤⼀些
segmentation fault
Time Limit Exceeded
时间复杂度表

基础算法.md
2023-09-16
4 / 172
计算速度:C++ ⼀般1s计算$10^{7}$到$10^{8}$次
从⼤到⼩排序
定义⼀个函数
bool cmp(int x,int y)
{
return x > y;
}
使⽤时将其作为第三个参数

基础算法.md
2023-09-16
5 / 172
sort(arr,arr + 10,cmp);
或者直接
sort(arr, arr + 5, greater<int>());
⼀.基础算法
class1
⼆分查找
循环结束时,left必须等于right
两种模板,每次迭代时将区间分为两个部分,这两个部分的边界值很重要,决定了mid的计算⽅式
将区间更新为[mid:right]和[left,mid-1],此时mid向上取整
将区间更新为[mid+1:right]和[left,mid],此时mid向下取整
关于>=还是>,在含有等号的判断语句中,不能更新mid-1或者mid+1
//1.向上取整
public int search1(int[] nums, int target) {
int left = 0,right = nums.length - 1, mid = -1;
while(left < right){
mid = left + right + 1 >> 1;
if(target >= nums[mid]) left = mid; // =号的判断,target等于当前值,将当前下标
返回
else right = mid - 1; //收缩右边界,如果有多个答案,最终找到的是从右向左的第一个
答案
}
return nums[left] == target ? left:-1;
}
//2.向下取整
public int search2(int[] nums, int target) {
int left = 0,right = nums.length - 1, mid = -1;
while(left < right){
mid = left + right >> 1;
if(target > nums[mid]) left = mid + 1; //收缩左边界,最终找到从左向右第一个答
案
else right = mid;
}
return nums[left] == target ? left:-1;
}
剩余172页未读,继续阅读
资源评论



TechMasterPlus
- 粉丝: 4693
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助


最新资源
- 桩基钢筋加工(劳务分包)协议书.doc
- 单片机原理与接口技术试题及答案.doc
- 给水企业供水调度管理信息化初探.docx
- 用于慢病管理的网络化健康信息技术.ppt
- 基于广义回归神经网络的黄金价格预测.docx
- 城市污水雨水管网的设计计算(毕业设计).doc
- 大数据技术在智慧物流中的应用研究.docx
- 全现浇结构塔楼造价指标.doc
- 浙江计算机网络专业技术历真题(附标准答案).doc
- 监理人员进场一览表1.doc
- hs-icf外墙外保温建筑节能体系技术规程概要.doc
- 人工智能医疗应用场景解析.pptx
- 劳动合同(固定期限).docx
- 4层百货框架结构计算书及施工组织设计.doc
- 新型智慧城市解决方案V3.pptx
- 计算机基础上机指导.doc
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈



安全验证
文档复制为VIP权益,开通VIP直接复制
