【信息学奥赛一本通】 第一章 基础算法

登录以参加训练计划

《信息学奥赛一本通》(C++版)自2013年出版以来,深受中小学生信息学奥赛入门级选手的青睐,每次改版使该书内容能够不断改进和完善。《信息学奥赛一本通》定位为入门级精品教程,通俗易懂、内容精练、快速入门。

学习程序设计的关键是方法和思想,尤其在中小学起步阶段,教学的重点应该放在培养学生浓厚的编程兴趣、良好的编程习惯和科学算法思想上,要避免繁杂的概念和次要知识,抓住核心的、主要的知识点开展教学。同时,一定量的上机训练也是体会和掌握程序设计的必由之路,所以,教练选择讲解的例题和带有实战背景的训练习题就显得尤为重要。基于此,我们组织信息学金牌教练编写《信息学奥赛一本通·训练指导教程》。

本书紧密围绕“程序=算法+数据结构”这一核心思想,结合《信息学奥赛一本通》的重点和难点,对大量经典的、实战性的习题进行深入剖析,从每个题目的题义分析到算法设计,从朴素算法到算法的适当优化和比较分析,从每个变量的解释到采用的数据结构的含义和操作,让读者全方位地体会到“程序是怎样炼成的”。

本书使用了Noip的原题和从网络收集的部分资料,由于时间跨度较长,许多资料难以找到原创作者。在此,向这些素材的作者表示衷心感谢。

最后,感谢《信息学奥赛一本通》作者。

章节 1. 【1.1】贪心算法

开放

题目 尝试 AC 难度
1   「一本通 1.1 例 1」活动安排 0 0 (无)
12   「一本通 1.1 例 2」种树 0 0 (无)
23   「一本通 1.1 例 3」喷水装置 0 0 (无)
34   「一本通 1.1 例 4」加工生产调度 0 0 (无)
45   「一本通 1.1 例 5」智力大冲浪 0 0 (无)
47   「一本通 1.1 练习 1」数列极差 0 0 (无)
48   「一本通 1.1 练习 2」数列分段 0 0 (无)
49   「一本通 1.1 练习 3」线段 0 0 (无)
50   「一本通 1.1 练习 4」家庭作业 0 0 (无)
2   「一本通 1.1 练习 5」钓鱼 0 0 (无)
3   「一本通 1.1 练习 6」糖果传递 0 0 (无)

章节 2. 【1.2】二分与三分

开放

题目 尝试 AC 难度
4   「一本通 1.2 例 1」愤怒的牛 2 2 10
5   「一本通 1.2 例 2」Best Cow Fences 13 1 10
6   「一本通 1.2 例 3」曲线 8 2 10
7   「一本通 1.2 练习 1」数列分段 II 5 2 10
8   「一本通 1.2 练习 2」扩散 0 0 (无)
9   「一本通 1.2 练习 3」灯泡 3 2 10
10   「一本通 1.2 练习 4」传送带 0 0 (无)

章节 3. 【1.3】深搜的剪枝技巧

开放

题目 尝试 AC 难度
11   「一本通 1.3 例 1」数的划分 1 1 10
13   「一本通 1.3 例 2」生日蛋糕 0 0 (无)
14   「一本通 1.3 例 3」小木棍 0 0 (无)
15   「一本通 1.3 例 4」Addition Chains 1 1 10
16   「一本通 1.3 例 5」weight 3 1 10
17   「一本通 1.3 练习 1」埃及分数 0 0 (无)
18   「一本通 1.3 练习 2」平板涂色 2 1 10
19   「一本通 1.3 练习 3」质数方阵 0 0 (无)
20   「一本通 1.3 练习 4」靶形数独 0 0 (无)

章节 4. 【1.4】广搜的优化技巧

开放

题目 尝试 AC 难度
21   「一本通 1.4 例 1」电路维修 0 0 (无)
22   「一本通 1.4 例 2」魔板 2 1 10
24   「一本通 1.4 例 3」Knight Moves 0 0 (无)
25   「一本通 1.4 练习 1」棋盘游戏 0 0 (无)
26   「一本通 1.4 练习 2」Keyboarding 0 0 (无)
27   「一本通 1.4 练习 3」移动玩具 0 0 (无)
28   「一本通 1.4 练习 4」山峰和山谷 0 0 (无)