下载文档原格式
全国青少年信息学奥林匹克联赛大纲(节选)NOIP大纲一、总则由中国计算机学会负责组织的全国青少年信息学奥林匹克联赛(NOIP)是全国信息学奥林匹克竞赛(NOI)整个系列中的一个重要组成部分,旨在向中学生普及计算机基础知识,培养计算机科学和工程领域的后备人才。
普及的重点是根据中学生的特点,培养学生学习计算机的兴趣,使得他们对信息技术的一些核心内容有更多的了解,提高他们创造性地运用程序设计知识解决实际问题的能力。
对学生的能力培养将注重以下的几个方面:●想象力与创造力;●对问题的理解和分析能力;●数学能力和逻辑思维能力;●对客观问题和主观思维的口头和书面表达能力;●人文精神:包括与人的沟通能力,团队精神与合作能力,恒心和毅力,审美能力等。
二、命题程序和组织机构命题是选拔过程的重要一环,同时对计算机的普及内容起着导向性的作用。
命题应注重趣味性、新颖性、知识性、应用性和中学生的心智特点,不直接从大学专业教材中选题。
在命题和审题工作中,坚持开放和规范的原则。
在NOI科学委员会主持下成立的联赛命题委员会负责命题工作,命题委员会成员主要来自参加联赛的省(包括直辖市、自治区、下同。
每个省最多派一名委员),也可来自社会计算机界。
联赛命题委员会的主要职责是提供联赛的备选题目,并承担对所提供的题目保密的责任。
1. 联赛命题委员会委员应具备如下资格:●从事一线计算机教学或信息学奥赛辅导工作两年(含)以上;●有精力和时间从事该项工作;●对此项工作有兴趣并愿意作为志愿者从事NOIP命题及其相关工作。
2. 联赛命题委员会委员的产生过程:●本人提出申请(填写表格);●中学教师需所在单位同意或省奥赛主管部门同意;●科学委员会批准,由中国计算机学会颁发聘书(每一聘期为两年)。
3. 联赛命题委员会委员的职责:●每年为NOIP提供备选题题目若干,在9月1日之前提交科学委员会;●备选试题的保密期为2年,在该段时间内不得泄密或另作他用;●搜集本省信息学奥赛的有关信息并向科学委员会通报;题目一经提交,即表明同意授权中国计算机学会科学委员会全权处理,包括使用、修改和出版。
信息学奥赛基础知识习题(答案版)一、选择题（下列各题仅有一个正确答案，请将你认为是正确的答案填在相应的横线上）1．我们把计算机硬件系统和软件系统总称为 C 。
(A)计算机CPU (B)固件(C)计算机系统 (D)微处理机2．硬件系统是指 D 。
(A)控制器，运算器 (B)存储器，控制器(C)接口电路，I/O设备 (D)包括(A)、(B)、(C)3. 计算机软件系统包括 B 。
A) 操作系统、网络软件 B) 系统软件、应用软件C) 客户端应用软件、服务器端系统软件 D) 操作系统、应用软件和网络软件4．计算机硬件能直接识别和执行的只有 D 。
(A)高级语言 (B)符号语言(C)汇编语言 (D)机器语言5．硬盘工作时应特别注意避免 B 。
(A)噪声 (B)震动 (C)潮湿 (D)日光6．计算机中数据的表示形式是 C 。
(A)八进制 (B)十进制 (C)二进制 (D)十六进制7．下列四个不同数制表示的数中，数值最大的是 A 。
(A)二进制数11011101 (B)八进制数334(C)十进制数219 (D)十六进制数DA8．Windows 9x操作系统是一个 A 。
(A)单用户多任务操作系统 (B)单用户单任务操作系统(C)多用户单任务操作系统 (D)多用户多任务操作系统9．局域网中的计算机为了相互通信，必须安装___B__。
（A）调制解调器（B）网卡（C）声卡（D）电视卡10．域名后缀为edu的主页一般属于__A____。
（A）教育机构（B）军事部门（C）政府部门（D）商业组织11. 香港在世界上注册的顶级域名是__A____。
（A）hk（B）cn（C）tw（D）com12．计算机能够自动、准确、快速地按照人们的意图进行运行的最基本思想是（ D ）。
（A）采用超大规模集成电路（B）采用CPU作为中央核心部件（C）采用操作系统（D）存储程序和程序控制13．设桌面上已经有某应用程序的图标，要运行该程序，可以 C 。
信息学奥赛一本通编程启蒙之第三章循环结构奇偶分家本章主要介绍循环结构中的奇偶分家问题，通过实例和代码实现，帮助读者理解和掌握奇偶分家问题的解决方法和技巧。
下面是本店铺为大家精心编写的4篇《信息学奥赛一本通编程启蒙之第三章循环结构奇偶分家》，供大家借鉴与参考，希望对大家有所帮助。
《信息学奥赛一本通编程启蒙之第三章循环结构奇偶分家》篇1 引言在信息学奥赛中，循环结构是程序设计中经常用到的一种结构，而奇偶分家是循环结构中一个重要的问题。
在解决奇偶分家问题时，需要分析题目的特点，选择合适的算法和数据结构，从而提高程序的效率和正确性。
本章将通过实例和代码实现，帮助读者理解和掌握奇偶分家问题的解决方法和技巧。
奇偶分家问题的基本思路奇偶分家问题是指将一个序列中的数分为两部分，一部分为奇数，另一部分为偶数。
基本的思路是先找到序列中的第一个数，然后将其与序列中的最后一个数交换位置，接着找到序列中的第二个数，将其与序列中的倒数第二个数交换位置，以此类推，直到将序列中的所有数都分为两部分。
实例分析下面以一个实例来说明奇偶分家问题的解决方法。
假设有一个序列：5, 2, 9, 1, 6, 3, 8, 0, 7, 4。
现在需要将这个序列中的数分为两部分，一部分为奇数，另一部分为偶数。
首先找到序列中的第一个数 5，将其与序列中的最后一个数 0 交换位置，得到序列：0, 2, 9, 1, 6, 3, 8, 5, 7, 4。
然后找到序列中的第二个数 2，将其与序列中的倒数第二个数 5 交换位置，得到序列：0, 5, 9, 1, 6, 3, 8, 2, 7, 4。
接着找到序列中的第三个数 9，将其与序列中的倒数第三个数 2 交换位置，得到序列：0, 5, 2, 1, 6, 3, 8, 9, 7, 4。
以此类推，直到将序列中的所有数都分为两部分，得到奇数部分：5, 9, 1, 3, 7 和偶数部分：0, 2, 6, 8, 4。
代码实现下面是一个用 C++ 实现奇偶分家问题的示例代码：```cpp#include <iostream>using namespace std;void swap(int& a, int& b) {int temp = a;a = b;b = temp;}int main() {int n;cin >> n;int a[n];for (int i = 0; i < n; i++) { cin >> a[i];}int odd = 0, even = 0;for (int i = 0; i < n; i++) { if (a[i] % 2 == 1) {swap(a[i], a[odd]);odd++;} else {swap(a[i], a[even]);even++;}}for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;return 0;}```该程序首先从标准输入中读入一个整数 n，表示序列中数的个数。
信息学奥赛NOIP系列课程（三阶段）第一阶段C++语言及数据结构与算法基础课本:1、信息学奥赛一本通+训练指导教程C++版第五版--2017年出版(两本）第1部分C++语言（50课时）适于：零基础的初中或高中的学生，当然有C语言或scratch、Python语言基础更好授课：相关内容讲授+实例+题目现堂训练（每次课2-3题，题目较大可能是1题）第1章C++语言入门（2－3课时）第2章顺序结构程序设计（6课时）第3章程序控制结构（3课时）NOIP2017复赛普及组第1题成绩https:///problem-12334.htmlNOIP2018复赛普及组第1题标题统计方法一https:///problem-12393.htmlNOIP1996普及组第1题https:///WDAJSNHC/article/details/83513564https:///yuyanggo/article/details/47311665第4章循环结构（5课时）NOIP2018复赛普及组第1题标题统计方法二https:///problem-12393.htmlNOIP2016复赛普及组第1题买铅笔https:///problem-12121.htmlNOIP2015复赛普及组第1题金币/ch0105/45/NOIP2002复赛普及组第1题级数求和/ch0105/27/NOIP2013复赛普及组第1题计数问题https:///problem-11005.html?tdsourcetag=s_pcqq_aiomsgNOIP2012复赛普及组第1题质因数分解/ch0105/43/NOIP2011复赛普及组第1题数字反转/ch0105/29/NOIP2010复赛普及组第1题数字统计https:///problem-10012.htmlNOIP1999普及组第1题Cantor表/ch0201/8760/https:///problemnew/show/P1014NOIP1997普及组第1题棋盘问题https:///problemnew/show/P1548NOIP1995普及组复赛第1题https:///secret_zz/article/details/76862335https:///WDAJSNHC/article/details/83513896NOIP1997普及组第2题数字三角形https:///ber_bai/article/details/76722379第5章数组（9－10课时）NOIP2014复赛普及组第1题珠心算测验https:///problem-12091.htmlNOIP2009复赛普及组第1题多项式输出/ch0113/39/NOIP2006复赛普及组第1题明明的随机数/ch0110/09/NOIP2005复赛普及组第1题陶陶摘苹果/ch0106/02/NOIP2004复赛普及组第1题不高兴的津津/ch0109/03/NOIP2003年普及组第1题乒乓球/ch0113/37/NOIP1998年普及组第1题三连击（枚举）https:///problemnew/show/P1008NOIP1995普及组复赛第2题方阵填数https:///WDAJSNHC/article/details/79381876NOIP1996普及组第2题格子问题https:///WDAJSNHC/article/details/79381843?utm_source=blogxgwz5NOIP2016复赛普及组第2题回文日期https:///problem-12122.htmlhttps:///problemnew/show/P2010NOIP2015普及组第2题P2670扫雷游戏/ch0108/14/https:///problemnew/show/P2670https:///problem-12105.htmlNOIP2012普及组第2题_P1076寻宝/ch0112/06/https:///problemnew/show/P1076第6章函数（5课时）NOIP2008复赛普及组第1题ISBN号码/ch0107/29/NOIP2000提高组第1题P1017进制转换https:///problemnew/show/P1017NOIP2000普及组第1题计算器的改良https:///problemnew/show/P1022https:///yuyanggo/article/details/47856785https:///u012773338/article/details/41749421NOIP2018普及组第2题龙虎斗https:///problemnew/show/P5016https:///problem-12394.html机器翻译【1.12编程基础之函数与过程抽象07】Noip2010提高组第1题/ch0112/07/Vigenère密码【1.12编程基础之函数与过程抽象08】Noip2012提高组第1题/ch0112/08/笨小猴【1.9编程基础之顺序查找06】NOIP2008提高组第1题/ch0109/06/第7章文件和结构体（5课时）NOIP2011复赛提高组第1题铺地毯/ch0109/14/NOIp2008提高组第2题火柴棒等式https:///problemnew/show/P1149https:///Mr_Doublerun/article/details/52589778第8章指针及其应用（8课时）第9章C++实用技巧与模版库（5课时）NOIP2007复赛普及组第1题奖学金/ch0110/04/NOIP2017复赛普及组第2题图书管理员（STL、排序）https:///problem-12335.htmlhttps:///problemnew/show/P3955NOIP1999普及组第2题回文数https:///problemnew/show/P1015***模拟NOIP2017年提高组第2题时间复杂度（模拟）https:///problem-12333.htmlhttps:///problemnew/show/P3952NOIP2011普及组第3题P1309瑞士轮（模拟、快拍、归并排序）/ch0401/4363/https:///problemnew/show/P1309NOIP2018复赛普及组第3题摆渡车(模拟)https:///problem-12395.htmlhttps:///problemnew/show/P5017NOIP2016普及组第3题海港（port）--枚举https:///problemnew/show/P2058NOIP2006年提高组第3题P1065作业调度方案(模拟)https:///problemnew/show/P1065NOIP2013提高组第4题P1969积木大赛（模拟贪心）https:///problem-12071.htmlhttps:///problemnew/show/P1969NOIP2014提高组第4题P2038无线网络发射器选址（模拟）https:///problemnew/show/P2038第2部分NOIP基础算法（39课时）第1章高精度计算（2-3课时）【例1.6】回文数(Noip1999):8088/problem_show.php?pid=1309NOIP2003普及组第4题P1045麦森数(分治、高精度运算)https:///problemnew/show/P1045NOIP2005普及组第4题P1050循环(高精度运算、数论、快速幂) https:///problemnew/show/P1050第2章数据排序（3课时）NOIP2014复赛普及组第1题珠心算测验https:///problem-12091.html第3章递推算法（2-3课时）1314：【例3.6】过河卒(Noip2002):8088/problem_show.php?pid=1314NOIP2011普及组第4题P1310表达式的值(栈、表达式计算、递推) https:///problemnew/show/P1310NOIP2011提高组第6题P1315观光公交(递推分析、贪心)https:///problemnew/show/P1315第4章递归算法（2-3课时）【例4.6】数的计数(Noip2001普及组第1题):8088/problem_show.php?pid=1316第5章搜索与回溯算法（2-3课时）NOIP2015day1T3_斗地主P2668斗地主https:///problemnew/show/P2668NOIP2017年普及组第3题棋盘https:///problemnew/show/P3956https:///problem-12336.htmlNOIP2015年提高组第2题P2661信息传递（Tarjen bfs/dfs（图论））https:///problem-12107.htmlhttps:///problemnew/show/P2661NOIP2016年提高组第2题天天爱跑步（Lca/dfs（图论）树结构最近公共祖先）https:///problem-12208.htmlhttps:///problemnew/show/P1600NOIP2000普及组第4题P1019单词接龙(深搜)https:///problemnew/show/P1019NOIP2000年提高组第3题单词接龙(DFS,字符串,模拟)https:///problemnew/show/P1019NOIP2014普及组第4题P2258子矩阵(搜索或dp)https:///problemnew/show/P2258NOIP2018年提高组第3题P5021赛道修建(搜索深度优先搜索)https:///problem-12392.htmlhttps:///problemnew/show/P5021第6章贪心算法（3课时）删数问题（NOIP1994）P1106删数问题https:///problemnew/show/P1106:8088/problem_show.php?pid=1321NOIP2010复赛普及组第2题接水问题/ch0109/15/NOIP1999年提高组第1题导弹拦截https:///problemnew/show/P1020https:///huashanqingzhu/p/6728652.html https:///qq_33927580/article/details/51853345 https:///Darost/article/details/52086240https:///yuyanggo/article/details/48739029NOIP2002提高组第1题均分纸牌P1031均分纸牌https:///problemnew/show/P1031NOIP2007普及组第2题_P1094纪念品分组https:///problem-12007.htmlhttps:///problemnew/show/P1094NOIP2008普及组第2题_P1056排座椅https:///problem-12008.htmlhttps:///problemnew/show/P1056NOIP2012年提高组第2题国王游戏（贪心、排序后列出）https:///problemnew/show/P1080NOIP2013年提高组第2题P1966火柴排队(逆序对、贪心、排序) https:///problem-12083.htmlhttps:///problemnew/show/P1966NOIP2010普及组第4题P1199三国游戏(贪心)https:///problemnew/show/P1199第7章分治算法（3课时）NOIP2001提高组第1题P1024一元三次方程求解/ch0204/7891/https:///problemnew/show/P1024NOIP2011年提高组第2题P1311选择客栈(二分查找)https:///problemnew/show/P1311NOIP2003普及组第4题P1045麦森数(分治、高精度运算)https:///problemnew/show/P1045第8章广度优先搜索算法（2-3课时）NOIP2002年提高组第2题P1032字串变换(BFS,字符串)https:///problemnew/show/P1032NOIP2013提高组第6题P1979华容道(广搜\最短路:图论)https:///problem-12212.htmlhttps:///problemnew/show/P1979第9章动态规划（15课时）第一节动态规划的基本模型1260：【例9.4】拦截导弹(NOIP1999):8088/problem_show.php?pid=1260NOIP2013普及组第3题P1982小朋友的数字https:///problemnew/show/P1982NOIP2003复赛普及组第2题_P1043数字游戏数字游戏（Game.cpp）https:///problemnew/show/P1043NOIP2006年提高组第2题P1064金明的预算方案(资源分配DP,构造) https:///problemnew/show/P1064NOIP2013普及组第3题P1982小朋友的数字（动态规划、子段和）https:///problemnew/show/P1982NOIP2007普及组第3题P1095守望者的逃离(动态规划或枚举）https:///problemnew/show/P1095NOIP2009普及组第4题P1070道路游戏(动态规划)https:///problemnew/show/P1070NOIP2004年提高组第3题P1091合唱队形(子序列DP)https:///problemnew/show/P1091第二节背包问题NOIP2018提高组第2题货币系统https:///problem-12391.htmlNOIP2006普及组第2题_P1060开心的金明题解https:///problemnew/show/P1060NOIP2005普及组第3题P1048采药(0/1背包)/ch0206/1775/https:///problem-12062.htmlhttps:///problemnew/show/P1048NOIP2001普及组第4题P1049装箱问题(0/1背包或枚举)https:///problemnew/show/P1049NOIP2014年提高组第3题P1941飞扬的小鸟(背包DP)https:///problem-12087.htmlhttps:///problemnew/show/P1941第三节动态规划经典题NOIP2000年提高组第2题P1018乘积最大（资源分配DP）https:///problemnew/show/P1018NOIP2000普及组第3题P1018乘积最大(划分动态规划)https:///problemnew/show/P1018NOIP2001年提高组第2题P1025数的划分（资源分配DP,多维状态DP）/ch0206/8787/https:///problemnew/show/P1025NOIP2001年提高组第3题统计单词个数(资源分配DP,字符串) https:///problemnew/show/P1026NOIP2005年提高组第2题P1052过河(子序列DP,贪心优化)https:///problemnew/show/P1052NOIP2010年提高组第2题P1541乌龟棋(动态规划优化)https:///problemnew/show/P1541NOIP2014年提高组第2题P1351联合权值（动态规划搜索图结构树形DP图的遍历遍历（图论）,二次展开式）https:///problem-12086.htmlhttps:///problem-12210.htmlhttps:///problemnew/show/P1351NOIP2008普及组第3题P1057传球游戏（动态规划）https:///problemnew/show/P1057NOIP2012普及组第3题摆花（动态规划）https:///problem-12366.htmlhttps:///problemnew/show/P1077NOIP2002普及组第4题P1002过河卒(棋盘动态规划)https:///problemnew/show/P1002NOIP2008年提高组第3题P1006传纸条(多维状态DP动态规划图结构最短路网络流)https:///problem-12110.htmlhttps:///problemnew/show/P1006NOIP2000提高组第4题方格取数(多维状态DP)/ch0206/8786/https:///problem-12186.htmlhttps:///problemnew/show/P1004NOIP2002提高组第4题P1034矩形覆盖(动态规划/贪心/搜索剪枝) /ch0405/1793/https:///problemnew/show/P1034第3部分NOIP数据结构（19课时）第1章栈（3课时）NOIP2011普及组第4题P1310表达式的值(栈、表达式计算、递推) https:///problemnew/show/P1310第2章队列（3-5课时）NOIP2016普及组第3题海港（port）https:///problemnew/show/P2058第3章树（3课时）第一节树的概念第二节二叉树第三节堆及其应用NOIP2015普及组第4题P2672推销员(枚举、堆)https:///problemnew/show/P2672NOIP2001普及组第3题P1030求先序排列(树的遍历)https:///problemnew/show/P1030NOIP2004普及组第3题P1087FBI树(二叉树的遍历)https:///problemnew/show/P1087第4章图论算法（8课时）第一节基本概念第二节图的遍历第三节最短路径算法NOIP2002普及组第3题P1037产生数(最短路、高精度)https:///problemnew/show/P1037NOIP2012普及组第4题P1078文化之旅(搜索、最短路(图论)、动规) https:///problemnew/show/P1078NOIP2009年提高组第3题P1073最优贸易(最短路:图论）https:///problemnew/show/P1073NOIP2001提高组第4题P1027Car的旅行路线(最短路,实数处理)https:///problemnew/show/P1027NOIP2007提高组第4题P1099树网的核(最短路,树的直径)https:///problemnew/show/P1099第四节图的连通性问题第五节并查集NOIP2010年提高组第3题P1525关押罪犯(二分答案或并查集)https:///problemnew/show/P1525NOIP2017提高组第4题P3958奶酪（数据结构树结构并查集）https:///problem-12205.htmlhttps:///problemnew/show/P3958第六节最小生成树第七节拓朴排序与关键路径NOIP2013普及组第4题P1983车站分级(图论、拓扑排序) https:///problemnew/show/P19831390：食物链【NOI2001】:8088/problem_show.php?pid=1390NOIP2004年提高组第2题P1090合并果子(最优哈夫曼树，排序，贪心)https:///problemnew/show/P1090NOIP2013年提高组第3题P1967货车运输(最大生成树,最近公共祖先)https:///problemnew/show/P1967NOIP2018提高组第4题P5022旅行（搜索图结构）https:///problem-12397.htmlhttps:///problemnew/show/P5022NOIP2018提高组第6题P5024保卫王国(图结构)https:///problem-12399.htmlhttps:///problemnew/show/P50242、啊哈！算法--2014-06（35-50小时）第二阶段算法与数据结构提高1、《信息学奥赛一本通·提高篇》（80-100课时，不一定一次都讲完）第一部分基础算法第1章贪心算法NOIP2002提高组第1题P1031均分纸牌(贪心,模拟)https:///problemnew/show/P1031NOIP2010普及组第3题P1158导弹拦截（排序+枚举，贪心）https:///problemnew/show/P1158NOIP2012提高组第6题P1084疫情控制(二分答案，贪心，倍增)https:///problemnew/show/P1084第2章二分与三分NOIP2010年提高组第3题P1525关押罪犯(二分答案或并查集)https:///problemnew/show/P1525NOIP2008提高组第4题P1155双栈排序(枚举,贪心/二分图)https:///problemnew/show/P1155NOIP2015提高组第4题P2678跳石头（二分查找、二分答案）https:///problem-12198.htmlhttps:///problemnew/show/P2678第3章深搜的剪枝技巧NOIP2018普及组第4题对称二叉树（搜索树结构深度优先搜索）https:///problem-12396.htmlhttps:///problemnew/show/P5018NOIP2011年提高组第3题P1312Mayan游戏(深搜、剪支)https:///problemnew/show/P1312NOIP2015年提高组第3题P2668斗地主(分情况,剪枝)https:///problemnew/show/P2668NOIP2003提高组第4题P1041传染病控制(随机贪心/搜索剪枝)https:///problemnew/show/P1041NOIP2004提高组第4题P1092虫食算（搜索搜索与剪枝）https:///problem-12414.htmlhttps:///problemnew/show/P1092第4章广搜的优化技巧NOIP2017年普及组第3题棋盘（搜索搜索与剪枝广度优先搜索）https:///problemnew/show/P3956https:///problem-12336.htmlNOIP2009提高组第4题P1074靶形数独(搜索优化)https:///problemnew/show/P1074NOIP2010提高组第4题P1514引入水域（广搜+动态规划，判断有解和无解）https:///problemnew/show/P1514第二部分字符串算法第1章哈希表第2章KMP算法第3章Trie字典树第4章AC自动机NOIP2005提高组第4题P1054等价表达式(字符串,抽样检测,表达式) /practice/1686/https:///problemnew/show/P1054NOIP2008普及组第4题P1058立体图(字符输出)https:///problemnew/show/P1058NOIP2006普及组第3题P1061Jam的计数法(数学、字符串)https:///problemnew/show/P1061NOIP2007年提高组第2题字符串的展开（字符串模拟）https:///problem-11016.htmlhttps:///problemnew/show/P1098NOIP2003年提高组第2题P1039侦探推理(枚举,模拟,字符串)https:///problemnew/show/P1039NOIP2011普及组第2题_P1308统计单词数/ch0112/05/https:///problemnew/show/P1308第三部分图论第1章最小生成树第2章最短路径NOIP2016年提高组第3题P1850换教室(最短路/Dp)https:///problemnew/show/P1850NOIP2017年提高组第3题P3953逛公园(搜索图结构记忆化搜索最短路)https:///problem-12337.htmlhttps:///problemnew/show/P3953NOIP2014提高组第5题P1351联合权值(遍历,二次展开式)https:///problem-12086.htmlhttps:///problemnew/show/P1351第3章SPFA算法的优化第4章差分约束系统第5章强连通分量第6章割点和桥第7章欧拉回路第四部分数据结构第1章树状数组第2章RMQ问题第3章线段树NOIP2012提高组第5题P1083借教室(枚举、线段树、树状数组、二分) https:///problem-12069.htmlhttps:///problemnew/show/P1083NOIP2017提高组第6题P3960列队(数据结构平衡树线段树)https:///problem-12339.htmlhttps:///problemnew/show/P3960第4章倍增求LCANOIP2015提高组第6题P2680运输计划(Lca或线段树)https:///problem-12213.htmlhttps:///problemnew/show/P2680第5章树链剖分第6章平衡树Treap第五部分动态规划第1章区间类型动态规划NOIP2007年提高组第3题P1005矩阵取数游戏(区间DP,高精度)https:///problemnew/show/P1005第2章树型动态规划NOIP2003年提高组第3题P1040加分二叉树(树,区间DP)https:///problemnew/show/P1040第3章数位动态规划第4章状态压缩类动态规划NOIP2017提高组第5题P3959宝藏(动态规划搜索贪心状态压缩DP枚举)https:///problem-12340.htmlhttps:///problemnew/show/P3959NOIP2016提高组第6题愤怒的小鸟(状态压缩动态规划)https:///problemnew/show/P2831第5章单调队列优化动态规划NOIP2016提高组第5题蚯蚓(单调队列)https:///Mrsrz/p/7517155.htmlhttps:///m0_38083668/article/details/82557281NOIP2017普及组第4题P3957跳房子（数据结构动态规划单调队列队列）https:///problem-12338.htmlhttps:///problemnew/show/P3957第6章利用斜率优化动态规划NOIP2012年提高组第3题P1081开车旅行(离线深搜，动态规划、倍增)https:///problemnew/show/P1081NOIP2015提高组第5题P2679子串(Dp+滚动数组)https:///problemnew/show/P2679第六部分数学基础第1章快速幂第2章素数第3章约数第4章同余问题第5章矩阵乘法第6章组合数学NOIP2009年提高组第2题P1072Hankson的趣味题(初等数论,质因数,组合数学)https:///problemnew/show/P1072NOIP2006提高组第4题P10662^k进制数(动态规划/组合数学,高精度) https:///problemnew/show/P1066NOIP2011提高组第4题P1313计算系数（组合、二项式系数）/practice/4036/https:///problemnew/show/P1313NOIP2016提高组第4题P2822组合数问题（杨辉三角）https:///problemnew/show/P2822第7章博弈论NOIP2004普及组第4题P1088火星人(数学:排列、stl)https:///problemnew/show/P1088NOIP2009普及组第3题P1069细胞分裂（数论）https:///problemnew/show/P1069NOIP2000提高组第1题P1017进制转换(初等代数,找规律)https:///problemnew/show/P1017NOIP2001提高组第1题P1024一元三次方程求解(数学,枚举,实数处理) /ch0204/7891/https:///problemnew/show/P1024NOIP2003普及组第3题P1044栈(数学:卡特兰数）https:///problemnew/show/P1044NOIP2018年提高组第2题货币系统(数论)https:///problem-12391.htmlhttps:///problemnew/show/P5020NOIP2014年普及组复赛第3题螺旋矩阵（数学分析）https:///problem-12341.htmlhttps:///problemnew/show/P2239NOIP2015年普及组第3题求和（数学：数列）https:///problemnew/show/P2671NOIP2004普及组第4题P1088火星人(数学:排列、stl)https:///problemnew/show/P1088NOIP2005普及组第4题P1050循环(高精度运算、数论、快速幂) https:///problemnew/show/P1050NOIP2006普及组第4题P1062数列(数学:进制转换)https:///problemnew/show/P1062NOIP2007普及组第4题P1096$Hanoi$双塔问题(数学、高精度) https:///problemnew/show/P1096NOIP2016普及组第4题P2119魔法阵(数学分析、枚举)https:///problemnew/show/P2119NOIP2002年提高组第3题P1033自由落体(数学,物理,模拟,实数处理) https:///problemnew/show/P1033NOIP2005年提高组第3题P1053篝火晚会(置换群,贪心)https:///problemnew/show/P1053NOIP2012提高组第4题P1082同余方程（数论、递归，扩展欧几里得）https:///problemnew/show/P1082NOIP2011提高组第5题P1314聪明的质监员(部分和优化)/practice/4037/https:///problemnew/show/P1314NOIP2013提高组第5题P1970花匠(序列)https:///problem-12072.htmlhttps:///problemnew/show/P1970NOIP2018提高组第5题P5023填数游戏（DP）https:///problem-12398.htmlhttps:///problemnew/show/P50232、NOIP历年真题讲解（30-50小时）---包括初赛和复赛3、《骗分导论》（推荐指数：5颗星）--电子书（可以作为学习的参考资料）第三阶段算法与数据结构高级专题（选择性学习）1、信息学奥赛之数学专题2、高级数据结构(C++版)3、动态规划专题注：上面的内容也可能要交叉的进行讲解在线题库：1、OpenJudge在线题库/2、信息学奥赛一本通在线评测系统:8088/3、洛谷https:///4、啊哈编程/tiku/5、《信息学奥赛一本通（提高篇）》在线评测OJhttps://loj.ac/注：本系列课程将根据行业发展状况，及时优化调整课程内容，具体课程设置以实际为准。
程序设计试题及答案（备注：试题难度评价采取五★级评价体系，分基础、容易、一般、稍难、难五个等级，其中的一、二、三★级都属于程序设计的基础试题级别，同学们稍加思考均有能力求得正确解答，对于四★级试题属于程序设计试题基础级别的思考题，五★级难度试题在此没有涉及，在程序设计高级试题中另行讲解。
对于基础和容易两个级别的程序设计试题，若能够给出语句分类（如If条件语句、条件语句嵌套、循环语句、多重循环语句等）的将尽量给出。
若属于13大类别的将尽量标注。
）程序设计试题几大分类：1、素数类问题（求素数的几种算法）：2、数据排序问题（数据排序的几种方法）：3、最大公约数和最小公倍数问题（几种算法）：4、公式求解类问题（如求圆周率π、自然常数e、解方程等等）：5、编号相反处理问题：6、约瑟夫问题（或猴子选大王问题、密码问题）：7、回文数问题：8、高精度数值计算问题：9、数值计算问题：10、进制相互转换问题：11、字符串倒置问题：12、排列与组合类问题：13、因子、质因子（质因数）类相关问题：答案部分：（程序设计的源程序没有统一的标准答案，实现程序的算法也是多种多样，但结果是唯一的，算法也有优劣之分，一个程序的优劣，关键在于是否找到了好的算法，以下程序和算法不一定就是最佳算法和最佳程序，只能仅供参考，希望同学们能够对某些程序提出更好的算法来改进程序）（经常碰到的判断是否为素数、是否为回文数、求两个数的最大公约数、求两个数的最小公倍数等问题的子函数源程序，请务必记住！）①判断是否为素数，若是素数则返回true，若不是素数则返回false：function prime(x:longint):boolean;varj,y:longint;beginprime:=true;if x<2 then prime:=false;y:=trunc(sqrt(x));for j:=2 to y doif (x mod j = 0) thenbegin prime:=false; exit; end;end;备注：1～100之间所有的素数：2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97。
2012福建省信息学奥林匹克CCFNOIP夏令营第三天训练解题思路及参考程序编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（2012福建省信息学奥林匹克CCFNOIP夏令营第三天训练解题思路及参考程序）的内容能够给您的工作和学习带来便利。
同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为2012福建省信息学奥林匹克CCFNOIP夏令营第三天训练解题思路及参考程序的全部内容。
瑞瑞的木棍:Hash函数题目大意：有N根两端被染色的木棍，只有两个颜色相同的端点才能连接在一起，求是否能将木棍连成一条直线.需要解决：如何处理用单词表示的颜色如何判断是否能连成一条直线单词的处理：在计算过程中用单词表示颜色显然是很不方便的,所以常用的做法就是将单词编号。
使用hash表将每个单词对应唯一的hash值对新出现的hash值编号，使每个单词分别对应编号1。
..M判断木棍是否能连成一条线:将每种颜色看作一个点，将每根木棍看作一条边,则问题转化为判断该图是否存在欧拉路径.存在欧拉路径的条件：图是连通的每个点都与偶数条边相连或有且只有2个点与奇数条边相连解题思路：1.用hash表将单词编号，将木棍以边的形式储存2。
统计与奇数条边相连的点的数量3.判断图是否连通：方法1：用dfs或bfs判断一个点是否能到达其他所有点方法2：用并查集判断所有点是否属于同一个集合参考程序：/* H: Colored Sticks */#include <stdio。
h〉#include 〈stdlib.h〉typedef struct｛char c1[11］;char c2[11];} Stick；typedef struct{char *col；} Color；Stick sticks[250020];int ssize = 0；Color colors[500020］;Color colorindex[500020］;int setsize = 0;int colorset［500020］;int csize = 0;int GetRoot(int x）{if（colorset[x] < 0） return x;else return GetRoot(colorset[x］）;}void Union (int a， int b）｛int rootA = GetRoot（a)；int rootB = GetRoot（b)；if(rootA == rootB) return；if（colorset[rootA］ <= colorset[rootB］）{colorset［rootA］ += colorset[rootB］； colorset[rootB］ = rootA；if(colorset[rootA］ == -1*setsize）｛printf（”Possible\n”）;exit(0）；}｝ else {colorset［rootB] += colorset［rootA］;colorset[rootA] = rootB；if（colorset[rootB] == -1＊setsize){printf（"Possible\n")；exit（0)；｝}}int cmp_sticks(Stick *a, Stick ＊b）｛int result = 0;result = strcmp(a—>c1，b—〉c1）；if（result == 0) result = strcmp(a-〉c2, b—>c2）;return result；｝int cmp_colors（Color *a, Color ＊b){return strcmp（a—>col, b—〉col)；}int binsearch（char *key， int min, int max）｛int cmp;int middle = (min+max)/2;if(min == max) return min；cmp = strcmp（key， colorindex[middle]。
