历年NOIP(普及组提高组)试题分析

[解题思想2 by peterche1990/2wsx2wsx2wsx/czp] 容易求出所有最长路，以及所有最长路上的点。依 次枚举，复杂度是O(KN^3)，其中K是最长路的条数。 该算法易于实现，但是写得不好会TLE1个点，部分 大牛就是这样没有得400的。
[解题思想3] 引理：如果树有多条直径，则每条直径上都存在一个core。 明：首先，如图，如果ABCD和FBCE都是直径的话，则AB=FB， CD=CE（如果不然，可设AB>FB，则FBCE<ABCE，矛盾！）。 这样，ABCE，FBCD也都是直径。我们给BC起个名字叫“公共 段”。题目中说过，公共段必然存在。 考虑ecc的定义，路径的ecc是指所有的点到路径的距离的最大值。 核指的是直径上长度满足约束的ECC最小的子路经。假如根据直径 ABCE算得的core是GHBI，路径GHBI的ecc就是max{BF,AG,DI,EI}, 这个最大值取到了最小。由于DC=EC，也就是说，如果路径和公 共段有交集，公共段的一端上，不包含CORE的直径是可以任选的。 换言之，此时max{BF,AG,ID}有最小值，此时用AB替换BF，发现必 然有BF=AB>AG，ecc=max{BF,ID}。也就是说，如果路径和公共段 有交集，实际计算max时，只需要计算路径在公共段上的部分的 ecc，然后和公共段两端的路径长取一遍MAX就行了。
第四个题目 core [题目转述] 给出一棵无根树，边上有权。称最长路径为直径， 定义路径的偏心距为：点到路径的上的点的最小值 的距离的最大值，给出一个s，找出直径上的某段长 度不超过s的路径，使得偏心距最小。
[解题思想] 算法是严格立方的。中心理念是不要做重复的工作。算法比较笨 拙。考虑到树的性质，对于任意两点，最短路=联通路=最长路。 首先求出多源最短路，该步可以由类似Tarjan的算法，在O(N^2) 内解决。实际上由于下一步的复杂度高达三次方，这里就直接 floyd了。同时可以求出最长路径上都有哪些点。在NOI2007中， 记录最短路的中间结点是很有用的。设mid[a,b]是a,b之间的联通 路上的一个中间点，。 由于这是一棵树，最短路必然唯一。考虑问题的解，构造一个函 数F(k,a,b)为K到ab间的最短路的长度。则 f(k,a,b)=min{d[k,mid[a,b],f[k,a,mid[a,b]],f[k,mid[a,b],b]} 写出了这 个方程，便不难得出一个三次方的算法。 在实际coding的时候，把k放在最外层枚举，这样内层实际上只 用到了f的后面2维，用2维数组记录即可。

53
二、模拟类试题
有些问题，我们很难建立数学模型，或者很难 用计算机建立递推、递归、枚举、回溯法等算 法。在这种情况下，一般采用模拟策略。
所谓模拟策略就是模拟某个过程，通过改变数 学模型的各种参数，进而观察变更这些参数所 引起过程状态的变化，由此展开算法设计。
金币 (noip2015普及组第一题)
输入样例：
70 3 71 100
69 1 12
输出样例：
3
（1 <= T <= 1000） （1 <= M <= 100）
采药 （noip2005普及组第三题）
题目大意：共m株草药，每株草药有一个价值 和采摘的时间，问t时间能采摘到的草药的最大 价值。
采药 （noip2005普及组第三题）
输入格式：
第一行有两个整数T和M，T代表总共能够用来采药的时间，M 代表山洞里的草药的数目。接下来的M行每行包括两个在1到 100之间（包括1和100）的整数，分别表示采摘某株草药的时 间和这株草药的价值。
输出格式：
一行只包含一个整数，表示在规定的时间内，可以采到的草药 的最大总价值。
螺旋方阵试题分析
本题首先让我们想到传统的模拟，从[1,1]开 始往数组中填充数字，但对于[30000,30000] 的数组，直接爆零。
对于读入的n, x, y，先判断(x,y)在第几圈， 再模拟圈内的数字。
螺旋方阵试题分析
如：n=4, (2,2)在第2圈，(3,1)在第1圈。 n=6，(4,5)在第2圈
移动；如果前方是未曾经过的格子，则继续前进， 否则右转；重复上述操作直至经过矩阵中所有格子。 根据经过顺序，在格子中依次填入1,2,3,....，便构 成了一个螺旋矩阵。 现给出矩阵大小n以及i和j，请你求出该矩阵中第 i行第j列的数是多少。 下图是一个n=4时的螺旋矩阵。

NOIP提高组初赛历年试题及答案选择题篇单项选择题（共10-15题，每题1.5分，共计15-22.5分。

每题有且仅有一个正确选项。

）注：答案在末尾NOIP2011-1.在二进制下，1011001+（）=1100110。

同普及组NOIP2011-1 A.1011 B.1101 C.1010 D.1111NOIP2011-2.字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。

A.66B.5AC.50D.视具体的计算机而定NOIP2011-3.下图是一棵二叉树，它的先序遍历是（）。

A.ABDEFCB.DBEFACC.DFEBCAD.ABCDEFNOIP2011-4.寄存器是（）的重要组成部分。

同普及组NOIP2011-6A.硬盘B.高速缓存C.内存D.中央处理器（CPU）NOIP2011-5.广度优先搜索时，需要用到的数据结构是（）。

同普及组NOIP2011-11A.链表B.队列C.栈D.散列表NOIP2011-6.在使用高级语言编写程序时，一般提到的“空间复杂度”中的空间是指（）。

同普及组NOIP2011-12A.程序运行时理论上所占的内存空间B.程序运行时理论上所占的数组空间C.程序运行时理论上所占的硬盘空间D.程序源文件理论上所占的硬盘空间NOIP2011-7.应用快速排序的分治思想，可以实现一个求第K大数的程序。

假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。

A.O(n2) B.O(n log n) C.O(n) D.O(1)NOIP2011-8.为解决web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。

A.微软B.美国计算机协会（ACM）C.联合国教科文组织D.万维网联盟（W3C）NOIP2011-9.体育课的铃声响了，同学们都陆续的奔向操场，按老师的要求从高到低站成一排。

枚举法其实是最简单的搜索算法。
.,.,
4
珠心算测验 (noip2014普及组第一题)
珠心算是一种通过在脑中模拟算盘变化来完成快 速运算的一种计算技术。珠心算训练，既能够开 发智力，又能够为日常生活带来很多便利，因而 在很多学校得到普及。
某学校的珠心算老师采用一种快速考察珠心算加 法能力的测验方法。他随机生成一个正整数集合， 集合中的数各不相同，然后要求学生回答：其中 有多少个数，恰好等于集合中另外两个（不同的） 数之和？ 最近老师出了一些测验题，请你帮忙求 出答案。
不过，如果把调查结果就以这种方式呈现出来，大 多数人肯定不会满意。因为这个比例的数值太大， 难以一眼看出它们的关系。对于上面这个例子，如 果把比例记为 5:3，虽然与 真实结果有一定的误差， 但依然能够较为准确地反映调查结果，同时也显得 比较直观。
现给出支持人数 A，反对人数 B，以及一个上限 L， 请你将 A 比 B 化简为 A’比 B’，要求在 A’和 B’均 不大于 L 且 A’和 B’互质（两个整数的最大公约数 是 1）的前提下，A’/B’ ≥ A/B 且 A’/B’ - A/B 的值 尽可能小。
输入样例 2 23 ?*? *??
输出样例 2 mine.out 2*1 *21
对于 100%的数据，1≤n≤100，1≤m≤100
.,.,
10
比例简化 (noip2014普及组第二题)
在社交媒体上，经常会看到针对某一个观点同意与 否的民意调查以及结果。例如，对某 一观点表示 支持的有 1498 人，反对的有 902 人，那么赞同与 反对的比例可以简单的记为1498:902。
.,.,
11
比例简化 (noip2014普及组第二题)
输入格式 输入共一行，包含三个整数 A，B，L，每两个整

对于100%的数据，3 ≤ n ≤ 100 测验题给出的正整数大小不超过10,000。
试题分析

题意大意：给你n个数，在这n个数中，找 到满足A+B=C的C的个数，注意不是这个 等式的个数。
样例中，1,2,3,4有1+2=3，1+3=4两个。

由于本题数据规模n<=100，我们可以直接
枚举C, A, B，三层循环解决问题。
扫雷游戏 (noip2015普及组第二题)
输入样例 1 33 *?? ??? ?*? 输入样例 2 23 ?*? *??
输出样例 1 mine.out *10 221 1*1 输出样例 2 mine.out 2*1 *21
对于 100%的数据，1≤n≤100，1≤m≤100
问题分析：
本题也是简单的枚举类试题。 我们从雷区的第一行第一列(1,1)开始，判断它周围 有多少个地雷。 由于本题读入的是字符，读入时需要注意： readln(n,m); for i=1 to n do begin for j=1 to m do read(a[i][j]); readln; end;
比例简化 (noip2014普及组第二题)



在社交媒体上，经常会看到针对某一个观点同意与 否的民意调查以及结果。例如，对某 一观点表示 支持的有 1498 人，反对的有 902 人，那么赞同与 反对的比例可以简单的记为1498:902。 不过，如果把调查结果就以这种方式呈现出来，大 多数人肯定不会满意。因为这个比例的数值太大， 难以一眼看出它们的关系。对于上面这个例子，如 果把比例记为 5:3，虽然与 真实结果有一定的误差， 但依然能够较为准确地反映调查结果，同时也显得 比较直观。 现给出支持人数 A，反对人数 B，以及一个上限 L， 请你将 A 比 B 化简为 A’比 B’，要求在 A’和 B’均 不大于 L 且 A’和 B’互质（两个整数的最大公约数 是 1）的前提下，A’/B’ ≥ A/B 且 A’/B’ - A/B 的值 尽可能小。

NOIP2008-C
NOIP2008-D
NOIP2009-A
NOIP2009-B
火柴棒等式 模拟
传纸条 双栈排序
动态 规划
构造
潜伏者 模拟
Hankson的 趣味题
数学
枚举,优化/开表 0.8
历届搜索
题一般都比较
多维状态DP 0.7 难，搜索算法
本身简单，于
枚举,贪心/二分 图
0.4
是题目会提高
选手对其他方
模拟
【构造】
动态 规划
构 造， 贪心
多维DP
BFS/贪心,并查 集
平均难度系 数：0.27
构造类题 目一般没有明 确的算法，需
NOIP2010-D
引水入城
搜索 BFS
要选手仔细分 析题目的实
质，并得出解法。
这个解法通常不是唯一的。有时一个好的贪心可以得相当
多的分。有时搜索剪枝可以很大的提高效率。同样以多得分为
需要掌握
模拟,字符串
质数及其性 0.8 质，基础的实
子序列DP,贪心 优化
0.2
数操作，加法 原理和乘法原
置换群,贪心 0.2 理。此类题需
字符串,抽样检 测,表达式
区间环DP
要选手对数学 0.3 规律的灵感。
【图论】 0.6 平均难度系
资源分配DP,构 造
0.6
数：0.50 历届考察
模拟
动态规划/组合 数学,高精度
金明的预算 动态
方案
规划
作业调度方 案
模拟
2^k进制数
动态 规划
统计数字 模拟
字符串的展 开
模拟
矩阵取数游 动态
戏
规划
树网的核 图论

} bool over(hugeint a,hugeint b) // 若大整数 a>b 则返回 true ，否则返回 false { int i; if(a.len<b.len) return false; if( a.len>b.len ) return true; for(i=a.len;i>=1;i--){ if(a.num[i]<b.num[i]) return false; if(a.num[i]>b.num[i]) return true; } return false; } int main() { string s; int i; hugeint target,left,middle,right;
cin>>s; memset(target.num,0,sizeof(target.num)); target.len=s.length(); for(i=1;i<=target.len;i++) target.num[i]=s[target.len-i]- '0'; memset(left.num,0,sizeof(left.num)); left.len=1; left.num[1]=1; right=target; do{ middle=average(left,right); if(over(times(middle,middle),target)) right=middle; else left=middle; }while(!over(plustwo(left),right) ); for(i=left.len;i>=1;i--) cout<<left.num[i]; return 0; }
NOIP2013-1. 序列重排 全局数组变量 a 定义如下: const int SIZE = 100; int a[SIZE], n; 它记录着一个长度为 n 的序列 a[1], a[2], ..., a[n]。 现在需要一个函数， 以整数 p (1 ≤ p≤ n)为参数， 实现如下功能:将序列 a 的前 p 个数与后 n – p 个数对调， 且不改变这 p 个数(或 n – p 个数)之间的相对位置。 例如，长度为 5 的序列 1, 2, 3, 4, 5，当 p = 2 时重排结果为 3, 4, 5, 1, 2。 有一种朴素的算法可以实现这一需求， 其时间复杂度为 O(n)、 空间复杂度为 O(n): void swap1(int p) { int i, j, b[SIZE]; for (i = 1; i <= p; i++) b[n–p+i] = a[i]; for (i = p + 1; i <= n; i++) b[i-p]= a[i]; for(i=1;i<= n;i++) a[i] = b[i]; } 我们也可以用时间换空间， 使用时间复杂度为 O(n2)、 空间复杂度为 O(1)的算法: void swap2(int p) { int i, j, temp; for (i = p + 1; i <= n; i++) { temp = a[i]; for(j=i;j>= i–p+1;j--) a[j] = a[j - 1]; a[i – p]= temp; } }

NOIP提高组初赛历年试题及答案阅读题篇阅读程序写结果（共4 题，每题8 分，共计32 分）阅读程序的最好方法并非是依次从头到尾。

程序不像迷语，我们无法从末尾几页找到答案，也不像一本引人入胜的书籍，只需直接翻到褶皱最多的那几页，我们就能找到最精彩的片断。

因此我们在阅读程序时，最好逐一考察研究每一段代码，搞清楚每一段代码的来龙去脉，理解每一段代码在程序中所起的作用，进而形成一个虚拟的程序结构，并以此为基础来进行阅读。

1、分层读：高层入手，逐层深入，正确理解程序。

2、写注解：固化、总结、提炼已有的理解成果。

3、先模拟：根据代码顺序跟踪变量，模拟运算。

4、找规律：先模拟几次循环后，找出背后的规律。

5、看功能：从代码结构和运算结果判断程序功能。

6、猜算法：有时不知道算法，通过结构和函数猜一猜。

7、换方法：了解程序本质后，换一个熟悉的方法试试。

对大多数人来说，写程序是令人开心的一件事情，读别人的程序却很痛苦，很恐惧，宁愿自己重写一遍。

其实读到好的程序，就像读一篇美文，令人心旷神怡，豁然开朗，因为这背后是一个人的思维，甚至整个人生。

阅读别人的程序不仅可以巩固自己的知识，启发自己的思维，提升自己的修养，让你收获满满，其实，这也是在学习、在竞赛、在工作中的最重要、最常用的基本功。

如果说写程序是把自己的思维转化为代码，读程序就是把代码转化为你理解的别人的思维。

当你阅读程序时有强烈的代入感，像演员一样，真正进入到编剧的精神世界，面部表情也随之日渐丰富起来。

祝贺你！你通关了！总之，看得多，码得多，拼得多，你就考得多……NOIP2011-1．#include <iostream>#include <cstring> using namespace std; const int SIZE = 100; int main(){int n,i,sum,x,a[SIZE]; cin>>n;memset(a,0,sizeof(a)); for(i=1;i<=n;i++){ cin>>x;a[x]++;}i=0;sum=0;while(sum<(n/2+1)){ i++;sum+=a[i];}cout<<i<<endl; return 0;}输入：4 5 6 6 4 3 3 2 3 2 1一步步模拟，注意输出的是sum超出循环条件时的i值（中位数），而不是sum，也不是a[x]输出：3NOIP2011-2．#include <iostream>using namespace std;int n;void f2(int x,int y);void f1(int x,int y){if(x<n)f2(y,x+y);void f2(int x,int y){cout<<x<<' ';f1(y,x+y);}int main(){cin>>n;f1(0,1);return 0;}输入：30此为简单的递归题，依次输出f2(x,y)中的x值，注意边界条件时f1(x,y)的x>=30咦！这不是隔一个输出一个的Fibonacci吗？输出：1 2 5 13 34NOIP2011-3．#include <iostream>using namespace std;const int V=100;int n,m,ans,e[V][V];bool visited[V];void dfs(int x,intlen){int i;visited[x]= true;if(len>ans)ans=len;for(i=1;i<=n;i++)if( (!visited[i]) &&(e[x][i]!=-1) ) dfs(i,len+e[x][i]);visited[x]=false;}int main(){int i,j,a,b,c;cin>>n>>m;for(i=1;i<=n;i++)for(j=1;j<=m;j++)e[i][j]=-1;for(i=1;i<=m;i++) {cin>>a>>b>>c; e[a][b]=c;e[b][a]=c;}for(i=1;i<=n;i++) visited[i]=false; ans=0;for(i=1;i<=n;i++) dfs(i,0);cout<<ans<<endl; return 0;}输入：4 61 2 102 3 203 4 304 1 401 3 502 4 60一看就知这是深搜算法（DFS），输入是个四个顶点的无向图（邻接矩阵如下）：如len>ans，则ans=len，可以说明这是个在图中用DFS找最长的路径的程序。

1≤ L ≤ R≤10000。
NOIP2010——数字统计
从L到R枚举每一个数i,对i进行分离数字，直接
统计有多少个2......

分离数字的过程
void count(int n)
{while (n>0) {if (n%10==2) ans++; n/=10; }
}
NOIP2010——接水问题

NOIP2012——寻宝

藏宝楼共有N+1层，最上面一层是顶层，顶层有一个 房间里面藏着宝藏。除了顶层外，藏宝楼另有 N层， 每层M个房间，这M个房间围成一圈并按逆时针方向 依次编号为0，…，M-1。其中一些房间有通往上一 层的楼梯，每层楼的楼梯设计可能不同。每个房间里 有一个指示牌，指示牌上有一个数字x，表示从这个 房间开始按逆时针方向选择第x个有楼梯的房间（假 定该房间的编号为k），从该房间上楼，上楼后到达 上一层的k号房间。比如当前房间的指示牌上写着2， 则按逆时针方向开始尝试，找到第2个有楼梯的房间， 从该房间上楼。如果当前房间本身就有楼梯通向上层， 该房间作为第一个有楼梯的房间。
NOIP2010——三国

输入样例
输出样例
8
42 24 10 29 27 12 58
1
77
31 8 16 26 80 6
25 3 36 11 5 33 20 17 13 15 77 9 4 50
19
NOIP2010——三国
显然每个武将对应的最大默契值都无法选到，
但是可以保证能选到次大的。所以就在次大的 中选一个最大的作为答案咯。这样计算机肯定 也得不到更大的值所以一定是可以获胜的。
NOIP2012——质因数分解

NOIP普及组历届试题分析简介全国青少年信息学奥林匹克竞赛（National Olympiad in Informatics in Provinces，简称NOIP）是由教育部主管的我国重要的计算机竞赛之一，也是继数学、物理、化学等奥赛之后的第五个奥赛竞赛科目。

NOIP的目的是为了提高初、高中学生计算机编程能力，培养计算机及其应用等方面人才，推动计算机教学与应用的发展。

NOIP由普及组和提高组组成，普及组适合初学者，困难系数逐年递增，试题越来越难。

本文将以普及组历届试题为主，对试题进行分析，帮助初学者更好地掌握NOIP的难点和解题方法。

历届试题分析2021年2021年普及组共3道试题，分别为：•普及组-1：数论题目，给定两个数n和m，求出从1到n中可以被m整除的数的个数。

•普及组-2：暴力枚举题目，给定一个长度为n的整型数组a，请计算其中有多少个子序列满足其中的元素逆序对数量恰好等于k序列中逆序对数量的个数。

•普及组-3：贪心算法题目，有n个维度相同的矩形，每个矩形的左上和右下两个点坐标都已知，请问从这些矩形中能够组成的最大矩形的面积是多少。

，2021年的普及组试题难度适中，各个题目的知识点都不难掌握，但需要提高思维能力和编程能力。

2020年2020年普及组共3道试题，分别为：•普及组-1：模拟题目，给定一些操作，包括插入、删除、查询等操作，让我们实现对一个序列的操作。

•普及组-2：搜索算法题目，有n个物品和一个容量为v的背包，每个物品有重量w和价值c两个属性，要求将物品装入背包中，使得背包中物品的总价值最大，输出最大价值。

•普及组-3：排序算法题目，给定n个三元组(a,b,w)，要求将三元组按照a从小到大、b从小到大排序，如果a和b相等，则按照w从小到大排序。

，2020年的普及组试题相对较简单，难度偏低，但需要细致的思考和编程能力。

2019年2019年普及组共3道试题，分别为：•普及组-1：分支结构和循环结构的题目，输入一个字符串，输出字符串中包含的大写字母、小写字母、数字和空格的个数。

NOIP2007提高组试题及解析1.统计数字（count.pas/c/cpp）【问题描述】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。

已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

【输入】输入文件count.in包含n+1行；第一行是整数n，表示自然数的个数；第2~n+1每行一个自然数。

【输出】输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。

每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

【输入输出样例】count.in8242451002100count.out2 34 25 1100 2【限制】40%的数据满足：1<=n<=100080%的数据满足：1<=n<=50000100%的数据满足：1<=n<=200000，每个数均不超过1500 000 000（1.5*109）【解题思想1】显然，此题可以用排序的方法来解决，根据n的范围，可以看出，O(nlogn)的算法是可以接受的。

【解题思想2】维护一个二叉树，以数的大小作为节点的权值，以数的重复次数作为节点的附加信息。

之后中序遍历即可。

看起来，树内的节点个数应该不到n，所以可能表现不错，其算法复杂度依然为O(nlogn)【实际数据规模】挺小的，而且也没有传说中的卡Qsort的数据，全部都很温柔。

【分析】这个题目实在不能说是一道TG组的好题。

实际上，个人认为题目最大的意义在于：提供了10个测试排序算法的不怎么特别好的数据。

话说回来，此题是送分题，但是送分题送的这么水，考察的也就只有OIers的细心程度了。

在考试的时候，要相信有简单的题目，要相信有直接的算法。

在我的身边就有几个同学因为这个题目与一等失之交臂，这是最可惜的事情。

var a:array[1..200001] of longint;i,j,k,m,n:longint;procedure qsort(s,t:longint);var i,j,mid,temp:longint;begini:=s;j:=t;mid:=a[(s+t) div 2];while i<=j dobeginwhile a[i]<mid do inc(i);while a[j]>mid do dec(j);if i<=j thenbegintemp:=a[i];a[i]:=a[j];a[j]:=temp;inc(i);dec(j);end;end;if i<t then qsort(i,t);if j>s then qsort(s,j);end;beginreadln(n);for i:=1 to n do readln(a[i]);qsort(1,n);a[n+1]:=maxlongint;k:=1;for i:=2 to n+1 doif a[i]<>a[i-1] thenbegin writeln(a[i-1],' ',k); k:=1;endelse k:=k+1;end.2.字符串的展开（expand.pas/c/cpp）【问题描述】在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增的字母获数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。

NOIP提高组初赛历年试题及答案阅读题篇阅读程序写结果（共4 题，每题8 分，共计32 分）阅读程序的最好方法并非是依次从头到尾。

程序不像迷语，我们无法从末尾几页找到答案，也不像一本引人入胜的书籍，只需直接翻到褶皱最多的那几页，我们就能找到最精彩的片断。

因此我们在阅读程序时，最好逐一考察研究每一段代码，搞清楚每一段代码的来龙去脉，理解每一段代码在程序中所起的作用，进而形成一个虚拟的程序结构，并以此为基础来进行阅读。

1、分层读：高层入手，逐层深入，正确理解程序。

2、写注解：固化、总结、提炼已有的理解成果。

3、先模拟：根据代码顺序跟踪变量，模拟运算。

4、找规律：先模拟几次循环后，找出背后的规律。

5、看功能：从代码结构和运算结果判断程序功能。

6、猜算法：有时不知道算法，通过结构和函数猜一猜。

7、换方法：了解程序本质后，换一个熟悉的方法试试。

对大多数人来说，写程序是令人开心的一件事情，读别人的程序却很痛苦，很恐惧，宁愿自己重写一遍。

其实读到好的程序，就像读一篇美文，令人心旷神怡，豁然开朗，因为这背后是一个人的思维，甚至整个人生。

阅读别人的程序不仅可以巩固自己的知识，启发自己的思维，提升自己的修养，让你收获满满，其实，这也是在学习、在竞赛、在工作中的最重要、最常用的基本功。

如果说写程序是把自己的思维转化为代码，读程序就是把代码转化为你理解的别人的思维。

当你阅读程序时有强烈的代入感，像演员一样，真正进入到编剧的精神世界，面部表情也随之日渐丰富起来。

祝贺你！你通关了！总之，看得多，码得多，拼得多，你就考得多……NOIP2011-1．#include <iostream>#include <cstring> using namespace std; const int SIZE = 100; int main(){int n,i,sum,x,a[SIZE]; cin>>n;memset(a,0,sizeof(a)); for(i=1;i<=n;i++){ cin>>x;a[x]++;}i=0;sum=0;while(sum<(n/2+1)){ i++;sum+=a[i];}cout<<i<<endl; return 0;}输入：4 5 6 6 4 3 3 2 3 2 1一步步模拟，注意输出的是sum超出循环条件时的i值（中位数），而不是sum，也不是a[x]输出：3NOIP2011-2．#include <iostream>using namespace std;int n;void f2(int x,int y);void f1(int x,int y){if(x<n)f2(y,x+y);void f2(int x,int y){cout<<x<<' ';f1(y,x+y);}int main(){cin>>n;f1(0,1);return 0;}输入：30此为简单的递归题，依次输出f2(x,y)中的x值，注意边界条件时f1(x,y)的x>=30咦！这不是隔一个输出一个的Fibonacci吗？输出：1 2 5 13 34NOIP2011-3．#include <iostream>using namespace std;const int V=100;int n,m,ans,e[V][V];bool visited[V];void dfs(int x,intlen){int i;visited[x]= true;if(len>ans)ans=len;for(i=1;i<=n;i++)if( (!visited[i]) &&(e[x][i]!=-1) ) dfs(i,len+e[x][i]);visited[x]=false;}int main(){int i,j,a,b,c;cin>>n>>m;for(i=1;i<=n;i++)for(j=1;j<=m;j++)e[i][j]=-1;for(i=1;i<=m;i++) {cin>>a>>b>>c; e[a][b]=c;e[b][a]=c;}for(i=1;i<=n;i++) visited[i]=false; ans=0;for(i=1;i<=n;i++) dfs(i,0);cout<<ans<<endl; return 0;}输入：4 61 2 102 3 203 4 304 1 401 3 502 4 60一看就知这是深搜算法（DFS），输入是个四个顶点的无向图（邻接矩阵如下）：如len>ans，则ans=len，可以说明这是个在图中用DFS找最长的路径的程序。

NOIP历年复赛提高组试题(2004-2013)第十届全国信息学奥林匹克分区联赛（NOIP2004）复赛试题（提高组竞赛用时：3小时）1、津津的储蓄计划(Save.pas／dpr／c／cpp)【问题描述】津津的零花钱一直都是自己管理。

每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。

因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如11月初津津手中还有83元，妈妈给了津津300元。

津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。

到了11月月末，津津手中会剩下3元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。

有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。

如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。

如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

【输入文件】输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。

【输出文件】输出文件save.out包括一行，这一行只包含一个整数。

如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。

【样例输入1】290230908020060【样例输出2】15802、合并果子(fruit.pas／dpr／c／cpp)【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

第十届全国信息学奥林匹克分区联赛（NOIP2004）复赛试题（提高组竞赛用时：3小时）1、津津的储蓄计划(Save.pas／dpr／c／cpp)【问题描述】津津的零花钱一直都是自己管理。

每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。

因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如11月初津津手中还有83元，妈妈给了津津300元。

津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。

到了11月月末，津津手中会剩下3元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。

有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。

如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。

如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

【输入文件】输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。

【输出文件】输出文件save.out包括一行，这一行只包含一个整数。

如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。

【样例输入1】29023028020030017034050908020060【样例输出1】-7【样例输入2】29023028020030017033050908020060【样例输出2】1580【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

历届“问题求解”解析（2013竞赛辅导）问题求解是信息学竞赛初赛中常见题型，它共两题，每题5分，共10分，十六届增加了比重，有三题，占15分。

诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合、逻辑推理、递推关系等问题出现在问题求解中。

（相关问题的具体讲解根据需要考虑发讲义） 第一届（逻辑推理问题）1. 有标号为A 、B 、C 、D 和1、2、3、4的8个球，每两个球装一盒，分装4盒。

标号为字母的球与标号为数字的球有着某种一一对应的关系（称为匹配），并已知如下条件： ① 匹配的两个球不能在一个盒子内。

② 2号匹配的球与1号球在一个盒子里。

③ A 号和2号球在一个盒子里。

④ B 匹配的球和C 号球在一个盒子里。

⑤ 3号匹配的球与A 号匹配的球在一个盒子里。

⑥ 4号是A 或B 号球的匹配球。

⑦ D 号与1号或2号球匹配。

请写出这四对球匹配的情况。

第四届（递推、树、图）1. 已知一个数列U 1，U 2，U 3，…，U N ，… 往往可以找到一个最小的K 值和K 个数a 1，a 2，…,a n 使得数列从某项开始都满足： U N+K =a 1U N+K-1+a 2U N+K-2+……+a k U N (A)例如对斐波拉契数列1，1，2，3，5，…可以发现：当K=2，a 1 =1，a 2 =1时，从第3项起（即N>=1）都满足U n+2 =U n+1+U n 。

试对数列13，23，33，…，n 3,…求K 和a 1,a 2, …,a K 使得（A ）式成立。

当K= 4，a 1,a 2,…,a k 为a 1=4, a 2=6, a 3=4，a 4=-1对数列132333,…,n 3,…（A ）成立。

2．给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA 画出此二叉树。

3．用邻接矩阵表示下面的无向图：表示该无向图的邻接矩阵为 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0第五届（递推）将Ln 定义为求在一个平面中用n 条直线所能确定的最大区域数目。