没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
试读
50页
NOIP竞赛辅导专题CSP计算机等级考试辅导提高组普及组复赛辅导.pdf原创资料下载,CSP考级,CSP非专业级别的能力认证,CSP考级辅导资料,算法入门资料,青少年编程集训资料,信息学奥赛,信息学奥林匹克竞赛,NOIP普及/提高组重新命名为CSP-J/S,NOIP普及组,CSP-S(提高级)对标到提高组。这样也可以就两轮比赛加以解释,即CSP-J1为普及组初赛,CSP-J2为普及组复赛,CSP-S1为提高组初赛,CSP-S2为提高组复赛。
资源推荐
资源详情
资源评论
NOIP 竞赛辅导专题 CSP 计算机等级考试辅导提高组
普及组复赛辅导
目录:
1 各类数据范围
1.1 0x3F3F3F3F 的来源
1.2 数组可以开多大
2 优化技巧
3 并查集
3.1 模板
3.2 练习题
4 链式前向星
5 STL
5.1 栈、队列、优先队列、双端队
列
5.2 map 容器
5.3 string 操作
5.4 vector 向量
5.5 set
6 贪心算法
6.1 活动安排问题
6.2 最小区间覆盖问题
6.3 练习题
7 归并排序
7.1 归并排序求逆序数
8 前缀和
8.1 简介
8.2 题目
9 差分数组
9.1 定义
9.2 性质
9.3 例题
10 树状数组
10.1 简介
10.2 实现
10.3 树状数组扩展
10.4 二维树状数组
10.5 题目练习
10.6 总结
11 字典树
11.1 字典树可以解决的问题
11.2 一题入门
11.3 练习题
12 DP 入门
13 DP 强化
13.1 钱币找零问题
14 二进制优化 DP
15 单调队列优化 DP
16 多路 DP
16.1 例题
17 区间 DP
18 数位 DP
19 二分答案
20 二进制操作
21 状态压缩 DP
22 树形 DP
23 期望/概率 DP
23.1 概率模型
23.2 入门题目
23.3 赠券收集问题
23.4 概率/期望 DP-高难度
24 DP 优化总结
25 单调栈
25.1 简介
25.2 应用
25.3 练习题
26 组合数学
26.1 N 个球放入 M 个盒子问题
26.2 整数拆分
27 数论数学
27.1 逆序数
28 最优思想
28.1 无序数组的最大差值
29 数据结构
1 各类数据范围
1.1 0x3F3F3F3F 的来源
(1)int 类型的最大值:
MAX = 0x7fffffff; MIN = 0x8fffffff;
MAX = (1<<31) – 1; MIN = -(1<<31);
十进制:MAX 约为 2*10^9,如果超过了 10^9,就需要 long long 存储。
用上述的方法表示最大和最小很多场景下不能使用,比如:
1)无穷大加一个常数还是无穷大的情况。
if(d[u] + w[u][v] < d[v]) d[v]=d[u]+w[u][v]; 最短路径算法的松弛操作。
2)无穷大加无穷大还是无穷大的情况。
如何解决?
很多人喜欢用 0x3f3f3f3f 来表示最大值,下面给出原因。
1)0x3f3f3f3f 的十进制是 1061109567,也就是 10^9 级别的(和 0x7fffffff
一个数量级),而一般场合下的数据都是小于 10^9 的,所以它可以作为无穷大使用而不
致出现数据大于无穷大的情形。
2)由于一般的数据都不会大于 10^9,所以当我们把无穷大加上一个数据时,它并
不会溢出,这就满足了“无穷大加一个有穷的数依然是无穷大”,如果多个相加则这种方
法也不可以,最好的方法是用某个东西代替无穷大,这又增加了编程难度。
3)如果我们想要将某个数组清零,我们通常会使用 memset(a,0,sizeof(a))这样
的代码来实现(方便而高效)。但是当我们想将某个数组全部赋值为无穷大时,就只能自
己写循环来初始化,因为 memset 是按字节操作的,它能够对数组清零是因为 0 的每个字
节都是 0,现在我们将无穷大设为 0x3f3f3f3f,0x3f3f3f3f 的每个字节都是 0x3f,所
以要把一段内存全部置为无穷大,我们只需要 memset(a,0x3f,sizeof(a))。
所以在通常的场合下,0x3f3f3f3f 真的是一个非常棒的选择。
(2)long long 最大值
MAX = (1<<63)-1; MIN = -(1<<63);
MAX = 9*10^18;
1.2 数组可以开多大
没有确切的答案,全局变量最好开 10^6 以内
int a[1000000];
有时候确定数组大小很麻烦
因此用 vector 是一个很好的选择。
2 优化技巧
输入优化
https://blog.csdn.net/Lj_victor/article/details/81590816
3 并查集
并查集(Union/Find)从名字可以看出,主要涉及两种基本操作:合并和查找。初始
时并查集中的元素是不相交的,经过一系列的基本操作(Union),最终合并成多个集合。
在每次合并之前,或者合并之后,最基本的就是判断两个元素是否在一个集合中,这
就涉及到查找操作。
3.1 模板
(1)简单并查集
int f[MAXN]; //并查集数组
//查询节点属于哪个集合
int find(int x){
while(f[x] != x){//一直找到根
x = f[x];
}
return x;
}
//合并两个节点,合并前需要自己判断是否属于同一集合
void merge(int x,int y) {
x = find(x);
y = find(y);
f[x] = y;
}
//main 函数中需要进行初始化
for(int i = 1; i <= n; i++)
f[i] = i; //开始是各个节点成一个集合
对应上图来理解。
(2)启发式合并+路径压缩优化
int find(int x){
int temp = x;//保存子节点,为路径压缩使用
while(f[x] > 0){//一直找到根
x= f[x];
}
//路径压缩
int t;
while(temp != x){
t = f[temp];
f[temp] = x;
temp = t;
}
return x;
}
void union(int x,int y) {
int fx = find(x);
int fy = find(y);
if(fx != fy){
//启发式合并,少的往多的合并
if(-f[fx] < -f[fy]){
f[fy] += f[fx];
f[fx] = fy;
}else{
f[fx] += f[fy];
f[fy] = fx;
}
}
}
3.2 练习题
入门级:
HDU1232 畅通工程
Kruscal 最小生成树算法
POJ 1182 食物链
https://blog.csdn.net/niushuai666/article/details/698168
剩余49页未读,继续阅读
资源评论
随风浪仔
- 粉丝: 707
- 资源: 2706
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 305建筑结构水电欧式6套(14.5x20.2)\施工图\D型施工图\空调05首层空调平面图(一).dwg
- 305建筑结构水电欧式6套(14.5x20.2)\施工图\D型施工图\空调04架空层空调平面图(二).dwg
- 现代通信组网相关的教程&案例&相关项目知识点总结与回顾.docx
- 305建筑结构水电欧式6套(14.5x20.2)\施工图\D型施工图\空调03架空层空调平面图(一).dwg
- wpf 异步加载图片完成后再显示
- 305建筑结构水电欧式6套(14.5x20.2)\施工图\D型施工图\空调02设计说明.dwg
- 305建筑结构水电欧式6套(14.5x20.2)\施工图\D型施工图\空调0001材料表.dwg
- 305建筑结构水电欧式6套(14.5x20.2)\施工图\D型施工图\空调00图纸目录.dwg
- 305建筑结构水电欧式6套(14.5x20.2)\施工图\D型施工图\结构\别墅平面图.dwg
- 305建筑结构水电欧式6套(14.5x20.2)\施工图\D型施工图\结构\别墅D补充说明.dwg
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功