主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
提高组初赛通过指南
最后更新于 2025-08-27 19:49:59
作者
MilkyCoffee
分类
个人记录
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
计算机科学请移步：[Link](https://www.luogu.com.cn/blog/317198/pu-ji-zu-chu-sai-tong-guo-zhi-na) 这篇博文与计算机科学除知识点外的不同点： - 博主更强了 - 废话更少了 - 考点更精了 在您阅读这篇文章之前，请您将计算机科学部分指南通读（不背也没有太大关系，据博主观察这种题虽然考的概率极高但是 $60\%$ 均是常识，但是有些年份会有及其毒瘤的题目，比如考你非常偏僻的缩写是什么意思）。 待填坑，可能会投日报。 附：按照目前进度，可以考虑 $7.10$ 之前更新完毕。 本文可以进行在原有内容上的创编与改造，但是必须附上原文链接。 正文： ---- CSP-S / NOIp 的初赛分两种题目，近几年来是 1 至 15 题为选择题，16 至 20 为其他题目，而后五道大题需要 OI 经验，在这方面能力欠佳的同学可以配合 [能力全面提升综合题单](https://www.luogu.com.cn/training/9391) 和 OI-wiki 进行知识的学习，在这里将会列举出选择题常考的知识点。 选择题： - 数学类 / 数论 - 进制 $m$ 进制通常以 $(num)_m$ 的形式表示，其中自个位数起，第 $i$ 个数的值为 $m^{i-1} \times num$ 的第 $i$ 个数所表示的值。 例题： ``` 请选出以下最大的数（） ``` `A.`$(550)_{10}$ `B.` $(777)_{8}$ `C.` $2^{10}$ `D.` $(22F)_{16}$ 正确答案：C；解析：$(550)_{10}=550,(777)_{8}=511,2^{10}=1024,(22F)_{16}=559$ - 位运算 详见 OI-wiki : [Link](https://oi-wiki.org/math/bit/) 例题： ``` 二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑或运算的结果是（）。 ``` `A. 11 1111 1101 1111 B. 11 1111 1111 1101 C. 10 1111 1111 1111 D. 11 1111 1111 1111` - 中国剩余定理 详见 OI-wiki : [Link](https://oi-wiki.org/math/crt/) 例题： ``` 一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数 n 在以下哪个区间？已知 n<60。（ ） ``` `A.30<n<40 B.40<n<50 C.50<n<60 D.20<n<30` 正确答案：C；解析：班级人数为 $53$ ，按照 $CRT$ 的求解过程计算或者一眼秒出答案验算正确即可。 - 杂项-数学（简单） CSP 2020 提高组初赛 第 $11$ 题：计算即可。 CSP 2020 提高组初赛 第 $13$ 题：$4 \times 4 \times 3 \times 3 \div 2 = 72$ CSP 2019 提高组初赛 第 $6$ 题：排列组合 - 无脑计算类 - 分辨率 初赛时题目会给出 xx 位真彩色图像（也就是存储一个像素需要多少 $bit$）然后硬算即可。 例题： ``` 现有一段 8 分钟的视频文件，它的播放速度是每秒 24 帧图像，每帧图像是 一幅分辨率为 2048×1024像素的 32 位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？（ ）。 ``` `A. 30G B. 90G C. 150G D. 450G` 正确答案：C；解析：$8*60*24*2048*1024*32/8/1024/1024/1024=90$ - 基础语法类 CSP 2019 提高组 初赛 第 $1$ 题：运用存储数据类型的知识进行计算即可。 - OI 类 - 数据结构 - 栈 具体算法参考 OI-wiki : [Link](https://oi-wiki.org/ds/stack/) 例题： ``` 今有一空栈 S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为（ ）。 ``` `A.b B.a C.d D.c` 正确答案：B；解析：。 - 哈希 具体算法参考 OI-wiki : [Link](https://oi-wiki.org/ds/hash/) 例题： ``` 将(2, 7, 10, 18)分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数h(x)=（ ），将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。 ``` `A. ` $x^2\ mod\ 11$ `B. ` $2x\ mod\ 11$ `C. ` $x mod 11$ `D. ` $\llcorner x/2 \lrcorner mod 11$ 正确答案：D；解析：挨个计算看结果是否冲突即可。 - 搜索 - dfs（深度优先搜索） 详见 OI-wiki ：[Link](https://oi-wiki.org/search/dfs/) 无实际例题。 正确答案：；解析：。 - bfs（广度优先搜索） 详见 OI-wiki ：[Link](https://oi-wiki.org/search/bfs/) 例题： ``` 广度优先搜索时，一定需要用到的数据结构是( ) ``` `A.栈 B.二叉树 C.队列 D.哈希表` 正确答案：C；解析：。 - 二叉搜索树 这类题型往年没有考过，但是今年可能会考。 详见 OI-wiki ：[Link](https://oi-wiki.org/ds/bst/) - 图论 - 构成 连通无向图构成条件 : 边 $=$ 顶点数 $* ($顶点数 $- 1) / 2$ 例题： ``` G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有 （）个顶点。 ``` `A.10 B.9 C.11 D.8` 正确选项：B；解析：由上方的公式可得，边为 $28$ 的联通无向图顶点数为 $8$ ，加上一个单独的点构成非联通无向图，顶点数为 $9$。 - 存储方式 设图具有 $n$ 个点，$m$ 条边。 - 邻接表 运用搜索遍历图：$O(n+m)$；空间复杂度：$O(m)$；查询是否存在由 $u$ 发出的某条边：$O(d^+(u))$，二分优化后为 $O(log(d^+(u)))$；遍历点 $u$ 的所有出边：$O(d^+(u))$ 应用：稀疏图或适用。 - 邻接矩阵 运用搜索遍历图：$O(n^2)$；空间复杂度：$O(n^2)$；查询是否存在某条边：$O(1)$；遍历一个点的所有出边：$O(n)$ 应用：稠密图。 - 链式前向星 运用搜索遍历图：$O(n+m)$；空间复杂度：$O(m)$；查询是否存在 $u$ 发出的某条边：$O(d^+(u))$；遍历一个点的所有出边：$O(d^+(u))$ 应用：网络流或通用。 例题： ``` 具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。 ``` `A.` $O(n+e)$ `B.` $O(n^2)$ `C.` $O(e^2)$ `D.` $O(n)$ 正确答案：A；解析：。 - 最短路径 - Floyd - 额外条件：无负环 - 空间复杂度：$O(n^2)$ - 时间复杂度：$O(n^3)$ - 不属于贪心 - Bellman-Ford - 额外条件：无负环 - 空间复杂度：随存储方式而定 - 时间复杂度：$O(nm)$ - 不属于贪心 - SPFA - 额外条件：无负环，Bellman-Ford 的优化 - 空间复杂度：随存储方式而定 - 时间复杂度：大多数情况下跑的很快，但是可以被网格图卡到 $O(nm)$ - 不属于贪心 - dijkstra - 额外条件：无负环 - 空间复杂度：随存储方式而定 - 时间复杂度：暴力是 $O(n^2)$，用堆 $O(m\ log\ n)$，用优先队列 $O(m\ log\ m)$，用 ZKW 线段树 $O(m\ log\ n)$，用 Fibonacci 堆 $O(n\ log\ n + m)$ - 属于贪心 例题： ``` 对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。 ``` `A.` $O((m+n^2)log\ n)$ `B.` $O(mn+n^3)$ `C.` $O((m+n)log\ n)$ `D.` $O(n^2)$ 正确答案：D；解析：。 - 二分图 具体算法参考 OI-wiki : [Link](https://oi-wiki.org/graph/bi-graph/) 例题： ``` 二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，24 个顶点的二分图至多有（ ）条边。 ``` `A.144 B.100 C.48 D.122` 正确答案：A；解析：按照二分图的定义进行计算即可，$12 \times 12 = 144$ - 动态规划 ~~具体请看 OI-wiki~~ 这部分的经验主要由练习题目等获得。 例题（由于有图片就不直接写出来了）:https://ti.luogu.com.cn/problemset/1031 第十五题 正确答案：A；解析：根据图片，显然。 - 排序 选择、冒泡、插入排序的时间复杂度为 $O(n^2)$；计数排序的时间复杂度为 $O(n+w)$；基数排序的时间复杂度为 $O(nk\ log\ n)$，空间复杂度为 $O(n+k)$；快速排序的时间复杂度为 $O(n\ log\ n)$ 至 $O(n^2)$；归并排序的时间复杂度为 $O(n\ log\ n)$，空间复杂度为 $O(n)$；一般认为桶排序的时间复杂度为 $O(n)$ 其中，选择、快速排序为不稳定的排序方式。 - 杂项 注：这里收录一些不完全属于某种算法的题目与知识点。 - 表达式求值 具体请见 OI-wiki：[Link](https://oi-wiki.org/misc/expression/)，但因为 OI-wiki 描述的相当不清晰，下面进行简单的释义： - 前缀表达式：符号-数A-数B（波兰表达式） - 中缀表达式：数A-符号-数B - 后缀表达式：数A-数B-符号（逆波兰表达式） 对于表达式转换的题目，可以依照算式优先级从优先级小的向优先级大的一次进行转换（例题解析帮助理解，是个人的方法，可能不是很科学）。 例题： ``` 表达式 a*(b+c)-d 的后缀表达形式为（ ）。 ``` `A.abc*+d- B.-+*abcd C.abcd*+- D.abc+*d-` 正确答案：D；解析：如下 ``` 原式可化为：(a*(b+c))d- = a(b+c)*d- = abc+*d- ，所以选择 D 选项。 ``` - CSP 2020 提高组初始 第六题：考察贪心的应用，即使你不知道 ACD 选项，也一定清楚 0-1 背包不可以使用贪心算法。
正在渲染内容...
点赞
34
收藏
0
