历年noip普及组提高组试题分析

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时的螺旋矩阵。

枚举法其实是最简单的搜索算法。
.,.,
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 的值 尽可能小。

第一题：神经网络【试题分析】一、题意分析1、任务描述：从输入层开始，各节点按照传递公式，一层一层向下传递。

输出输出层中信号大于零的节点编号和信号大小。

（节点编号由小到大）如果没有满足条件的编号则输出NULL。

信号传递公式：∑∈-=Ei jijjiiUCWC),(公式中的Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值。

当Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。

当神经元处于兴奋状态时，下一秒它会向其它神经元传递信号，信号的强度为Ci。

2、输入：两个整数n（1≤n≤20）和p。

n表示节点的个数；p表示有向边的条数。

下面n行表示1-n号节点的状态和阈值。

下面p行表示有向边及其权值。

3、输出：输出输出层状态大于零的神经元编号和状态，并且按照编号有小到大顺序输出！若输出层的神经元最后状态小于等于0，则输出NULL。

二、问题分析1、题目中给出每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。

所以不必进行拓扑排序，一层一层的向下传递信号即可。

输出最后一层中信号大于零的节点编号。

2、可以建立一个队列，将输入层节点入队。

3、取队首节点出队，寻找此节点有向边，如果有有向边：1）则记录此节点不是输出层；2）再判断此节点信号大于零则向下传递信号，将指向的节点入队（防止重复入队）。

再出队再传递，直至全部出队。

注意：1）输入层可以是输出层。

2）信号传递公式中只减一次U[i]。

【程序清单】Program network;ConstInName='network.in';OutName='network.out';MM=100;VarInFile,OutFile:Text;C,U:Array[1..MM] Of LongInt;Map:Array[1..MM,1..MM] Of LongInt;Flag:Array[1..MM,1..MM] Of Boolean;IsOut:Array[1..MM] Of Boolean;Queue:Array[1..MM] Of LongInt;N,P,i,Int1,Int2,Head,Rear:LongInt;IsInQueue:Array[1..MM] Of Boolean;IsNull:Boolean;BeginAssign(InFile,InName);Reset(InFile);ReadLn(InFile,N,P);For i:=1 To N Do ReadLn(InFile,C[i],U[i]); FillChar(Flag,SizeOf(Flag),False);For i:=1 To P Do BeginRead(InFile,Int1,Int2);ReadLn(InFile,Map[Int1,Int2]);Flag[Int1,Int2]:=True;End;Close(InFile);FillChar(IsOut,SizeOf(IsOut),True);FillChar(IsInQueue,SizeOf(IsInQueue),False); Head:=1; Rear:=1;For i:=1 To N Do BeginIf C[i]>0 Then BeginQueue[Rear]:=i;Inc(Rear);IsInQueue[i]:=True;EndElse C[i]:=-U[i];End;While Head<Rear Do BeginFor i:=1 To N DoIf Flag[Queue[Head],i] Then BeginIf C[Queue[Head]]>0 Then BeginInc(C[i],Map[Queue[Head],i]*C[Queue[Head]]);If Not IsInQueue[i] Then BeginQueue[Rear]:=i;Inc(Rear);IsInQueue[i]:=True;End;End;IsOut[Queue[Head]]:=False;End;Inc(Head);End;Assign(OutFile,OutName);Rewrite(OutFile);IsNull:=True;For i:=1 To N DoIf IsOut[i] ThenIf C[i]>0 Then BeginWriteLn(OutFile,i,' ',C[i]);IsNull:=False;End;If IsNull Then WriteLn(OutFile,'NULL');Close(OutFile);End.第二题：侦探推理【试题分析】一、题意分析1、任务描述：M个人参加游戏，每人提供一句或多句证言，共P句证言。

【最新整理，下载后即可编辑】NOIP提高组初赛历年试题及答案求解题篇问题求解题（每次2题，每题5分，共计10分。

每题全部答对得5分，没有部分分）注：答案在文末提高组的问题求解题的知识点大多涉及计数问题、鸽巢原理、容斥问题、逻辑推理、递推问题、排列组合问题等。

NOIP2011-1．平面图可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。

4个顶点的平面图至少有6条边，如图所示。

那么，5个顶点的平面图至多有_________条边。

NOIP2011-2．定义一种字符串操作，一次可以将其中一个元素移到任意位置。

举例说明，对于字符串“BCA”可以将A移到B 之前，变字符串“ABC”。

如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要_________次操作。

NOIP2012-1. 本题中，我们约定布尔表达式只能包含p,q, r三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（¬）三种布尔运算。

如果无论p, q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。

例如，(p∨q)∨r和p∨(q∨r)等价，p∨¬p 和q∨¬q 也等价；而p∨q 和p∧q不等价。

那么，两两不等价的布尔表达式最多有_________个。

NOIP2012-2. 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。

例如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集），图2有14个不同的独立集。

那么，图3有_________个不同的独立集。

NOIP2013-1. 某系统自称使用了一种防窃听的方式验证用户密码。

密码是n个数s1,s2,…,sn，均为0或1。

该系统每次随机生成n个数a1,a2,…,an，均为0或1，请用户回答(s1a1+s2a2+…+snan)除以2的余数。

如果多次的回答总是正确，即认为掌握密码。

该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。

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进制数
动态 规划
统计数字 模拟
字符串的展 开
模拟
矩阵取数游 动态
戏
规划
树网的核 图论

noip提高组初赛试题NOIP（全称为：全国青少年信息学奥林匹克竞赛）提高组初赛试题是一项重要的计算机竞赛，旨在选拔优秀的青少年计算机才华，锻炼他们的编程和解题能力。

这项竞赛的题目分为多个部分，包括算法设计与分析、数据结构、离散数学、动态规划等，挑战着选手的智力和思维方式。

本文将对NOIP提高组初赛试题进行全面分析与讨论。

第一部分：算法设计与分析在这一部分，选手将面临各种算法问题，需要设计高效的算法来解决。

例如，题目中可能会给出一个复杂的图结构，要求选手找到最短路径或最大流等问题的解决方案。

此时，选手需要充分理解各种图算法，并结合题目要求给出合理的算法设计。

第二部分：数据结构数据结构是计算机程序设计中的重要基础。

在这一部分中，选手可能会面对各种数据结构相关的问题，如树、队列、堆、图等。

选手需要灵活运用不同类型的数据结构，并结合题目要求进行正确的操作。

第三部分：离散数学离散数学是计算机科学的重要分支，对于理解和解决问题具有重要作用。

在这一部分中，选手可能会遇到图论、集合论、逻辑推理等题目。

选手需要具备扎实的离散数学知识，并能够将其应用于实际问题的解决。

第四部分：动态规划动态规划是一种解决复杂问题的算法设计技巧，也是NOIP提高组初赛试题中常出现的题型。

选手需要根据题目要求，寻找最优子结构并利用动态规划算法进行求解。

这需要选手有很高的抽象思维和编程能力。

总结：NOIP提高组初赛试题的内容丰富多样，不仅考察了选手的编程实力，还要求他们具备扎实的数学和算法基础。

通过参与这项竞赛，选手可以提高自己的逻辑思维能力、问题解决能力和编程技巧，同时也为将来的学习和工作打下坚实的基础。

总之，NOIP提高组初赛试题的挑战性和多样性，为青少年计算机爱好者提供了一个锻炼自身能力的平台。

通过认真思考和努力实践，选手可以在这项竞赛中不断成长，并取得优异的成绩。

祝愿所有参加NOIP提高组初赛的选手能够取得理想的成绩，为未来的计算机领域贡献自己的力量！。

Day1铺地毯【问题描述】为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。

一共有n 张地毯，编号从1 到n。

现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。

注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

【输入】输入文件名为 carpet.in。

输入共 n+2 行。

第一行，一个整数 n，表示总共有n 张地毯。

接下来的 n 行中，第i+1 行表示编号i 的地毯的信息，包含四个正整数a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y 轴方向的长度。

第 n+2 行包含两个正整数x 和y，表示所求的地面的点的坐标（x，y）。

【输出】输出文件名为 carpet.out。

输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。

【输入输出样例 1】【输入输出样例说明】如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2，2）的最上面一张地毯是3 号地毯。

【输入输出样例 2】【输入输出样例说明】如上图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，点（4，5）没有被地毯覆盖，所以输出-1。

【数据范围】对于 30%的数据，有n≤2；对于 50%的数据，0≤a, b, g, k≤100；对于 100%的数据，有0≤n≤10,000，0≤a, b, g, k≤100,000。

【一句话题意】给定n个按顺序覆盖的矩形，求某个点最上方的矩形编号。

【考察知识点】枚举【思路】好吧我承认看到图片的一瞬间想到过二维树状数组和二维线段树。

置答案ans=-1，按顺序枚举所有矩形，如果点在矩形内则更新ans。

注意题中给出的不是对角坐标，实际上是(a,b)与(a+g,b+k)。

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找最长的路径的程序。

② 由编码求原数组：共 15 分（5%+5%+5%）
a 输入：N=5 B=（0，0，0，0，0）
输出： A=（4，3，2，1，0）
b 输入：N=10 B=（0，1，2，3，4，5，6，7，8，9）
输出： A=（0，1，2，3，4，5，6，7，8，9）
c 输入：N=7 B=（0，0，0，0，4，5，6）
R
Y Y
P2=B R N2R=2
Y
P3=Y R N3=R1
Y
Q
RR
Y
排列方案： 排列总数： 105×2=210
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y
RRR
BB
Y BB
① 输10入5×2=210 3 4R 4 R4 4R 3 4 B B
1 2R 2 R2 2R 2 1 3B B
应打印出完整的图形R：（R12 分R）
BB
15 1R6 1R6 1R5 4 B B
Y Y Y Y Y
7 8 R 8R 8 R 7 7
BB
Y
3 4 R4 R4 R4 3 4 B B
Y
1 2 2R 2 R 2 R 2 1
19 18 17 16 15 14 13 12 11 10 <3> 本题 14 分

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普及组解题报告————————————————————————————————作者：————————————————————————————————日期：NOIP2014普及组复赛解题报告本人是潍坊一中的wyw，69级，今年高一，现在马上就要NOIP了，打算把历年的NOIP普及、提高组题目都做一下，然后写写解题报告∵这个报告主要是给初中同学看的，所以我会写的详细一点Prolem 1 珠心算测试(count)这道题其实很简单，意思就是说给你一些数a1,a2,a3,a4...a n，然后让你回答有多少个A+B=C（A ≠ B ≠ C）满足(回答C的数量，而不是等式的数量)方法一那么有一种很明显的做法就是三层循环枚举C、A、B，注意：C是在最外层，若找到了一个A和一个B，满足上述等式，则C是一个符合要求的解，这时ans++，并且退出当前枚举，枚举下一个C，这种算法的时间复杂度是O(N3)而我当时没想到这个算法，因为有更好用而且简单更不容易出错的解法，方法二两重循环，分别枚举i=1...n,j=i+1...n，如果ai+aj这个数在集合中存在，那么you[a i+a j]←true，然后再从a1到a n做一次扫描，只要you[a i]，ans++这个算法的好处在于它很好写，不用退出什么的，也不用注意循环的顺序，而且时间复杂度是O(N2)代码(方法2)：#include<cstdio>using namespace std;int n, a[101], i, j, count;bool you[20001]={false};int main(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);for(i=1;i<n;i++)for(j=i+1;j<=n;j++)you[ a[i]+a[j] ]=true;count=0;for(i=1;i<=n;i++)count += you[ a[i] ];printf("%d\n",count);return 0;}在此征求一下大神的意见，如有更快的做法，敬请奉上小结：这道题很简单，但很多人没有做对的原因就是没有好好理解题意，但是根本原因其实还在于心态太骄傲了，认为是第一题就可以轻视，这样是不好的，水题我们更要做好啊，你想想同样是100分，这100分多么好拿，所以是水题、越该放平心态，细心地做。

历年NOIP(普及组)难度分析 by Climber.pINOIP提高组复赛考察点详细分析动态规划：12 模拟：10数学：5 图论：4搜索：4 构造：3贪心：2【动态规划】平均难度系数：0.55此项为历届NOIP考察次数最多的知识点。

主要有 1.区间模型 2.子序列模型 3.资源分配模型以及一些简单的多维状态设计技巧。

动态规划可以与图,树,高精度等知识点配合出题。

【模拟】平均难度系数：0.76平均每届NOIP都会出现1个模拟题。

这种题一般算法很简单，需要选手细心理解题目意思，注意细节。

考察选手的代码实现能力。

【数学】平均难度系数：0.46需要掌握质数及其性质，基础的实属操作，加法原理和乘法原理。

此类题需要选手对数学规律的灵感。

【图论】平均难度系数：0.50历届考察点基本上都是 1.最短路问题和 2.特殊图的性质。

特殊图包括树，拓扑图，二分图等。

历届NOIP在图论上的考察并不是很多。

【搜索】平均难度系数：0.38历届搜索题一般都比较难，搜索算法本身简单，于是题目会提高选手对其他方面的要求。

主要有搜索优化和模拟。

写搜索题时应该以尽量多得分为目标。

【构造】平均难度系数：0.27构造类题目一般没有明确的算法，需要选手仔细分析题目的实质，并得出解法。

这个解法通常不是唯一的。

有时一个好的贪心可以得相当多的分。

有时搜索剪枝可以很大的提高效率。

同样以多得分为目标。

【【贪心】平均难度系数：0.75此类题需要选手对算法的直觉，贪心正确性一旦被证明，通常题目就简单了。

历年NOIP(普及组)难度分析by Climber.pI年份题目名称考查内容难度1998 Three 枚举☆Factor 高精度运算★Power 数学（进制转换）★★1999 Cantor表模拟或数学★☆回文数字符串处理★★旅行家的预算动态规划或贪心★★☆2000 计算器的改良字符串处理★★税收与补贴问题数学或枚举★★乘积最大动态规划★★★单词接龙回溯★★★★2001 数的计算动态规划★最大公约数和最小公倍数数学（辗转相除法）★求先序排列树的遍历☆装箱问题0/1背包或枚举★2002 级数求和循环结构☆选数生成算法、素数判定★★★产生数简单图论★★★★过河卒递推或动态规划★☆2003 乒乓球字符串处理★☆数字游戏动态规划★★★★★栈数学（卡特兰数）★★麦森数分治、高精度运算★★★2004 不高兴的津津模拟☆花生采摘贪心★FBI树树的遍历★★火星人生成算法★★★2005 淘淘摘苹果模拟☆校门外的树模拟★采药0/1背包★循环高精度运算、数论、快速幂★★★★★2006 明明的随机数冒泡排序（去重）★开心的金明0/1背包★Jam计数法生成算法、字符串★★★数列数学（进制转换）★☆2007 奖学金冒泡排序（双关键字）★纪念品分组贪心、排序算法★☆守望者的逃离动态规划或枚举★★★Hanoi双塔问题数学、高精度★☆2008 ISBN号码字符串处理★排座椅贪心★★传球游戏动态规划★★★立体图字符输出★★★2009 多项式输出字符串处理★分数线划定快速排序（双关键字）★细胞分裂数论★★★★道路游戏动态规划★★★★★2010 数字统计枚举★接水问题模拟★导弹拦截排序+枚举★★★★三国游戏贪心★★★2011 （160）数字反转模拟、字符串★统计单词数模拟、字符串函数★瑞士轮模拟、快排、滚动数组★★★表达式的值栈、表达式计算、递推★★★★★2012 （150）质因数分解枚举★寻宝模拟，模运算★★摆花动态规划★★★★文化之旅搜索、最短路、动规★★★★☆/view/e1cdc430376baf1ffc4fad0c.htmlNOIP提高组复赛考察点详细分析题目编号题目名主考察点知识点系数NOIP-2000-A 进制转换数学初等代数,找规律0.6 NOIP-2000-B 乘积最大动态规划资源分配DP 0.7 NOIP-2000-C 单词接龙搜索DFS,字符串,模拟0.5 NOIP-2000-D 方格取数动态规划多维状态0.6 NOIP-2001-A 一元三次方程求解数学数学,枚举,实数处理0.5 NOIP-2001-B 数的划分动态规划资源分配DP,多维状态DP 0.7 NOIP-2001-C 统计单词个数动态规划资源分配DP,字符串0.3 NOIP-2001-D Car的旅行路线图论最短路,实数处理0.7 NOIP-2002-A 均分纸牌贪心贪心,模拟0.8 NOIP-2002-B 字串变换搜索BFS,字符串0.5 NOIP-2002-C 自由落体数学数学,物理,模拟,实数处理0.6 NOIP-2002-D 矩形覆盖构造动态规划/贪心/搜索剪枝0.2 NOIP-2003-A 神经网络图论拓扑排序,递推0.4 NOIP-2003-B 侦探推理模拟枚举,模拟,字符串0.5 NOIP-2003-C 加分二叉树动态规划树,区间DP 0.4 NOIP-2003-D 传染病控制构造随机贪心/搜索剪枝0.2 NOIP-2004-A 津津的储蓄计划模拟模拟0.9 NOIP-2004-B 合并果子贪心最优哈夫曼树,排序0.7 NOIP-2004-C 合唱队形动态规划子序列DP 0.7 NOIP-2004-D 虫食算搜索搜索剪枝,模拟0.2 NOIP-2005-A 谁拿了最多奖学金模拟模拟,字符串0.8 NOIP-2005-B 过河动态规划子序列DP,贪心优化0.2 NOIP-2005-C 篝火晚会数学置换群,贪心0.2 NOIP-2005-D 等价表达式模拟字符串,抽样检测,表达式0.3 NOIP-2006-A 能量项链动态规划区间环DP 0.6NOIP-2006-B 金明的预算方案动态规划资源分配DP,构造0.6 NOIP-2006-C 作业调度方案模拟模拟0.7 NOIP-2006-D 2^k进制数动态规划动态规划/组合数学,高精度0.5 NOIP-2007-A 统计数字模拟排序 1.0 NOIP-2007-B 字符串的展开模拟字符串,模拟0.7 NOIP-2007-C 矩阵取数游戏动态规划区间DP,高精度0.6 NOIP-2007-D 树网的核图论最短路,树的直径0.4 NOIP-2008-A 笨小猴模拟质数判断,字符串 1.0 NOIP-2008-B 火柴棒等式模拟枚举,优化/开表0.8 NOIP-2008-C 传纸条动态规划多维状态DP 0.7 NOIP-2008-D 双栈排序构造枚举,贪心/二分图0.4 NOIP-2009-A 潜伏者模拟字符串,模拟0.9 NOIP-2009-B Hankson的趣味题数学初等数论,质因数,组合数学0.4 NOIP-2009-C 最优贸易图论最短路0.5 NOIP-2009-D 靶形数独搜索搜索优化0.3 NOIP-2010-A 机器翻译模拟NOIP-2010-B 乌龟棋动态规划动态规划优化NOIP-2010-C 关押罪犯二分答案二分答案或并查集NOIP-2010-D 引水入域广搜+动规判断有解和无解NOIP-2011-D1A 铺地毯枚举，模拟循环队列NOIP-2011-D1B 选择客栈枚举二分查找、NOIP-2011-D1C Mayan游戏深搜剪支NOIP-2011-D2A 计算系数组合二项式系数NOIP-2011-D2B 聪明的质监员二分答案部分和优化NOIP-2011-D2C 观光公交贪心递推分析NOIP-2012-D1A Vigenere密码枚举模拟左偏移位NOIP-2012-D1B 国王游戏贪心排序后列出NOIP-2012-D1C 开车旅行平衡树或链离线深搜，动态规划、倍增NOIP-2012-D2A 同余方程不定方程递归，扩展欧几里得NOIP-2012-D2B 借教室线段树枚举、线段树、二分NOIP-2012-D2C 疫情控制二分答案二分答案，贪心，倍增动态规划：12 模拟：10数学：5 图论：4搜索：4 构造：3贪心：2【动态规划】平均难度系数：0.55此项为历届NOIP考察次数最多的知识点。

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”。

★★★
2008
排座椅
贪心
★★
2008
ISBN 号码
字符串处理
★
2008
立体图
字符输出
★★★
2009
道路游戏
动态规划
★★★★★
2009
分数线划定
快速排序（双关键字）
★
2009
细胞分裂
数论
★★★★
2009
多项式输出
字符串处理
★
2010
数字统计
枚举
★
2010
接水问题
模拟
★★
2010
导弹拦截
排序+枚举，贪心
★★★★
2010
三国游戏
贪心
★★★
2011
瑞士轮
模拟、快拍、归并排序
★★★
2011
数字反转
模拟、字符串
★
2011
统计单词数
模拟、字符串函数
★
2011
表达式的值
栈、表达式计算、递推
★★★★★
2012
摆花
动态规划
★★★★
2012
质因数分解
枚举
★
2012
寻宝
模拟，模运算
★★★
2012
文化之旅
搜索、最短路(图论)、动规
数学（卡特兰数）
★★
2003
乒乓球
字符串处理
★☆
2004
FBI 树
二叉树的遍历
★★
2004
不高兴的津津
枚举
☆
2004
火星人
数学(排列)、stl
★★★
2004
花生采摘
贪心
★