noip历届签到题题解

历年NOIP选题题解汇总 联赛前上vijos板刷往年联赛题，使⽤在线编辑编写代码，祝我rp++。

废话不多说，挑⽐较有意思的记⼀下。

题⽬是按照年份排序的，最早只到了03年。

有些题⽬因为我还没写/很早之前写的忘了所以就没写题解。

NOIP2003 神经⽹络：按照题⽬怎么说怎么做，BFS即可。

注意输出层是指出度为0的层，不是指深度最⼤的。

传染病防治：爆搜题，枚举每⼀层减掉哪个。

复杂度不可算，理论在O(2^30*8!)左右，但好像强势不满。

想了⼀会貌似卡不掉？ NOIP2004 ⾍⾷算：知⼆推三，边搜边判。

NOIP2005 篝⽕晚会：⾸先你得知道两个排列可以看成若⼲个环，⽽且每个点只要转⼀次就可以转出来……⽽这题正好是两个排列的形式，即找到⼀个1-n的环和原环匹配最多就是不要动的⼈。

把每个⼈在环中的1的位置记下来取最多的就好了。

过河：把边权>=100的缩成100，因为长度过长没有意义，⼤于100了前⾯的情况必然可以凑出来，然后在1000下暴⼒DP即可。

注意特判S=T的情况，还有不要以为给出的点都在L内。

等价表达式：随便找⼏个数字(1~20)带进去算在模意义下都相等就可以了(跟解⽅程的思想有点像？)，重点是化为后缀表达式处理的trick。

NOIP2006 2^k进制数：⼤整数组合数。

NOIP2007 先坑着 NOIP2008 传纸条：显然的⽹络流，其实化为四维DP可做。

双栈排序：若存在i<j且A[i]>A[j]，即A[j]在A[i]前⾯弹栈。

因为A[i]最终也要出栈，所以⽐A[i]还要⼤的、在[i,j]中间的⼀定不能和A[i]在同⼀个栈中，即构成⼆分图。

判断有解就是⼆分图染⾊。

输出……反正我铁定WA的输出因为数据⽔过去了，不予置评。

NOIP2009 Hankson的趣味题：醉题，复杂度O(nsqrt(B)logB)但是跑得过？反正我是不会什么更好的解法…… 最优贸易：SPFA求出从1出发能买进的最低阶，从n出发沿反向边能卖出的最⾼价，最后枚举边减掉就好了。

枚举法其实是最简单的搜索算法。
.,.,
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/ | （初中部分）1排序：（有些排序因涉及贪心，所以我放在贪心那一节里了）历届试题：NOIP分数线划定奖学金明明的随机数排序法使用：选择排序。

快速排序。

桶排序。

分析：1.分数线划定：ci）这是一道具有代表性的排序题，可使用选择或快排，使用选择排序整体难度较小，但因此题数据量较大，选择排序不可过全部数据。

（2）使用快速排序是解决本题的最好方法，但不可直接套用，因为有儿个排序条件，排序内最好添加几个辅助变量。

2.奖学金：（1）这道题和上题大体相同，但其测试数据较小，可使用选择排序得全分。

3.明明的随机数：（1）本题可用选择或快排，但代码设计较难，使用桶排序解绝此题是较为理想的选择。

2模拟：分为三类：〈1〉普通模拟（完全模拟的较少，大多为结合贪心。

排序的，贪心。

排序的不单独讨论）历届试题：NOIP多项式输出数列1. NOIP多项式输出.：（1）多项式输出:这道题想要拿分很容易，但要注意一下模拟过程，此题实际上需有4个判段过程，其中有一个是极易遗漏的。

（2）数列:这道题竟是第4题，很简单的模拟题，还可用转成2进制的方式直接算.〈2〉罕符模拟历届试题：NOIP ISBN号码Jam记数法立体图（1）ISBN号码：总体难度不大，这道题如果是使用C语言的话，可以用每个字符都减去字符0的方式，直接把它们从字符转为数字，再进行处理。

（2）Jam记数法:很绝对的模拟，一开始我还认为是数学知识模拟题,就是从后往前推.（3）立体图:很难的很考细心的一道模拟题,没说的，就是上机不断的调程序.〈3〉数学知识模拟历届试题：NOIP细胞分裂（1）初中组目前唯一一道数学知识模拟题，掌握了相关的知识就应该不难，这道题要满分还是比较难的，需要高精度运算（用LONG LONG型不知道可不可以），还有一定要注意时间问题，这道题极易超时.3贪心：历届试题：NOIP排座椅纪念品分组守望者的逃离.注意：任何贪心之前都必需排序。

（1）排座椅:这道题初看不像一道贪心，但实际上只要细细的看，就可以发现了,跟实际生活联系很紧密的一道题。

NOIP普及组初赛历年试题及答案求解题篇问题求解：每次共2题，每空5分，共计10分。

每题全部答对得 5 分，没有部分分。

注：答案在文末在NOIP初赛问题求解中，经常会遇到排列组合问题。

这一类问题不仅内容抽象，解法灵活，而且解题过程极易出现“重复”和“遗漏”的错误，这些错误甚至不容易检查出来，所以解题时要注意不断积累经验，总结解题规律。

解答排列组合问题，首先必须认真审题，明确是属于排列问题还是组合问题，或者属于排列与组合的混合问题，其次要抓住问题的本质特征，灵活运用基本原理和公式进行分析解答。

同时还要注意讲究一些策略和技巧，比如采用分类、分步、捆绑等方法，也可以借助表格、方程等工具，使一些看似复杂的问题迎刃而解。

NOIP2011-1. 每份考卷都有一个8位二进制序列号。

当且仅当一个序列号含有偶数个1时，它才是有效的。

例如，0000000、01010011都是有效的序列号，而11111110不是。

那么，有效的序列号共有______个。

NOIP2011-2. 定义字符串的基本操作为: 删除一个字符、插入一个字符和将一个字符修改成另外一个字符这三种操作。

将字符串A变成字符串B的最少操作步数，称为字符串A到字符串B的编辑距离。

字符串“ ABCDEFG ”到字符串“BADECG ”的编辑距离为_______。

NOIP2012-1. 如果平面上任取n 个整点(横纵坐标都是整数) ，其中一定存在两个点，它们连线的中点也是整点，那么n至少是_____。

NOIP2012-2. 在NOI期间，主办单位为了欢迎来自全国各地的选手，举行了盛大的晚宴。

在第十八桌，有5名大陆选手和5名港澳选手共同进膳。

为了增进交流，他们决定相隔就坐，即每个大陆选手左右相邻的都是港澳选手、每个港澳选手左右相邻的都是大陆选手。

那么，这一桌共有_____种不同的就坐方案。

注意：如果在两个方案中，每个选手左边相邻的选手均相同，则视为同一个方案。

NOIP2013-1. 7 个同学围坐一圈，要选2 个不相邻的作为代表，有_____种不同的选法。

noip历届签到题题解石头剪刀布 //2014/problem/3716/联合权值/problem/3728/无线网络发射器/problem/3578/寻找道路/problem/3731/石头剪刀布打表，找出对应关系。

#include<cstdio>#include<cstdlib>using namespace std;const int m[5][5]={0,0,1,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,1,1,0,0,0,};int a[205],b[205];int main(){int n,na,nb;scanf("%d %d %d",&n,&na,&nb);for(int i=0;i<na;i++)scanf("%d",&a[i]);for(int i=0;i<nb;i++)scanf("%d",&b[i]);int sa=0,sb=0;for(int i=0;i<n;i++){sa=sa+m[a[i%na]][b[i%nb]]; sb=sb+m[b[i%nb]][a[i%na]]; }printf("%d %d",sa ,sb);return(0);}联合权值#include <iostream>#include <cstdio>#include <vector>#include <algorithm>using namespace std;long long n,p,k,w[200010];bool vis[200010];vector <int> edge[200010];void dfs(int x,int last1,int last2) {v is[x]=1;l ong long t=0,t2=0,t3=0,t4=0;f or (int i=0;i<edge[x].size();i++) {int y=edge[x][i];if (!vis[y]){vis[y]=1;if (last1!=0){k=(k+w[y]*w[last1])%10007;p=max(p,w[y]*w[last1]);}t2+=t*w[y]; t+=w[y];if (w[y]>=t3){t4=t3; t3=w[y];}if (w[y]<t3) t4=max(t4,w[y]);dfs(y,x,last1);}}p=max(t3*t4,p); k=(k+t2)%10007;}int main(){c in>>n;f or (int i=1;i<n;i++){int u,v;cin>>u>>v;edge[u].push_back(v);edge[v].push_back(u);}f or (int i=1;i<=n;i++) cin>>w[i];d fs(1,0,0);cout<<p<<' '<<k*2%10007<<endl;r eturn 0;}有关图的问题，到时候再解决。

间的整数，且 A[i]≠A[j]（当 i≠j 时）。
例如：N=6 时，有：
A=（4，3，0，5，1，2）
此时，数组 A 的编码定义如下：
A[0]的编码为 0；
A[i]的编码为：在 A[0]，A[1]，……A[i-1]中比 A[i]的值小的个数（i=1，2……N-1）
∴上面数组 A 的编码为：
B=（0，0，0，3，1，2）
输出： A=（3，2，1，0，4，5，6）
<5> 本题共 30 分（10%+10%+10%）
① 数据输入： N=6
P1=R
N1=1
Q
排列方案： R ② 排数列据总输数入=：6 N=6 R
P1=R
NR1=2
P2=Y
N2=1 R
Q
R
排列方案： R ③ 排数列据总输数入=：12N=1R2
P1=RR
R
Y
R R N1= 3
③ 同一种颜色的灯不能分开；
④ 不同颜色的灯之间至少要有一个空位置。
例如：N=8（格子数） R=2（红灯数） B=3（蓝灯数）
放置的方法有：
R-B 顺序
RR
BBB
RR
BBB
RR
BBB
RR
BBB
RR
BBB
B-R 顺序
RR
BBB
BBB
RR
BBB
RR
BBB
RR
BBB
RR
BBB
RR
放置的总数为 12 种。 数据输入的方式为：
提示：文档已分节，可用 word 跳转节功能 本文为本人将 1995-2008 年历届 NOIP 试题、研究成果整理而成，由于“年代久远”所以有不少 资料没有找到。但本人都尽量整理最有价值的信息记录于此。 资料来源皆为网络，若引用请注明出处 一不注意就 208 页了呢~ 其实最初只是想方便自己，看着一下午的成果，就忍不住放到了网络 上。由于赶时间，质量不太好，而且历届 NOIP 的排版也不一样，只是做了粗略的整理、排 版，若有错误之处，敬请谅解。 回首历届 NOIP，甚至比我自己出生的还早的老题，一代代 OIer 就从这条路上走过，作为一个 不大努力的 OIer，我甚至为自己感到愧疚。总之，为了报答一代代出题人、教师、主办方以及 OIer 们，在努力一把也不迟啊。

2006 年-B
所属知识点:_________________________源自本题心得与经验总结： 29
淮南二中信息学团队资料-历年 NOIP 真题汇编
2006 年-C
所属知识点:_________________________
30
淮南二中信息学团队资料-历年 NOIP 真题汇编
本题心得与经验总结： 31
淮南二中信息学团队资料-历年 NOIP 真题汇编
淮南二中信息学团队资料
历年 NOIP 真题汇编 I(2000-2005)
编辑、校对：刘龙
【2000 年】[4] P1017 进制转换 P1018 乘积最大 P1019 单词接龙 P1023 税收与补贴问题 【2001 年】[4] P1024 一元三次方程求解 P1025 数的划分 P1026 统计单词个数 P1027 Car 的旅行路线 【2002 年】[4] P1031 均分纸牌 P1032 字串变换 P1033 自由落体 P1034 矩形覆盖 【2003 年】[4] P1038 神经网络 P1039 侦探推理 P1040 加分二叉树 P1041 传染病控制 【2004 年】[4] P1089 津津的储蓄计划 P1090 合并果子 P1091 合唱队形 P1092 虫食算 【2005 年】[4] P1051 谁拿了最多奖学金 P1052 过河 P1053 篝火晚会 P1054 等价表达式 【2006 年】[4] P1063 能量项链 P1064 金明的预算方案 P1065 作业调度方案 P1066 2^k 进制数
2000 年-D
所属知识点:_________________________
本题心得与经验总结： 5
淮南二中信息学团队资料-历年 NOIP 真题汇编

第十三届全国青少年信息学奥林匹克联赛初赛试题（普及组Pascal 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案。

）1．在以下各项中，（）不是CPU的组成部分。

A．控制器B．运算器C．寄存器D．主板2．在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。

A．二叉树B．多叉树C．哈希表D．二维表3．在下列各项中，只有（）不是计算机存储容量的常用单位。

A．Byte B．KB C．UB D．TB4．ASCII码的含义是（）。

A．二→十进制转换码 B．美国信息交换标准代码C．数字的二进制编码D．计算机可处理字符的唯一编码5．一个完整的计算机系统应包括（）。

A．系统硬件和系统软件B．硬件系统和软件系统C．主机和外部设备D．主机、键盘、显示器和辅助存储器6．IT的含义是（）。

A．通信技术B．信息技术C．网络技术D．信息学7．LAN的含义是（）。

A．因特网B．局域网C．广域网D．城域网8．冗余数据是指可以由其它数据导出的数据。

例如，数据库中已存放了学生的数学、语文和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。

冗余数据往往会造成数据的不一致。

例如，上面4个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。

下面关于冗余数据的说法中，正确的是（）。

A．应该在数据库中消除一切冗余数据B．用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据C．为了提高查询效率，在数据库中可以保留一些冗余数据，但更新时要做相容性检验D．做相容性检验会降低效率，可以不理睬数据库中的冗余数据9．在下列各软件，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。

A．gcc B．g++ C．Turbo C D．Free Pascal10．以下断电后仍能保存数据的有（）。

noip 2018 第二轮题解NOIP (全国青少年信息学奥林匹克联赛)是中国的一个重要的信息学竞赛，每年都有许多优秀的学生参与。

第二轮是NOIP的选拔赛，对参赛者的算法和编程能力有一定的挑战。

下面是对2018年NOIP第二轮题目的解析。

1.题目一：最短编辑距离这道题目给出了两个字符串A和B，要求通过最少的操作（插入、删除和替换字符）将A转换成B。

首先我们可以使用动态规划的方法解决这个问题。

定义一个二维数组dp[i][j]表示将A的前i个字符转换成B的前j个字符所需要的最小操作数。

初始状态是dp[i][0] = i和dp[0][j] = j。

然后我们根据A[i]和B[j]是否相等来更新dp[i][j]。

如果相等，那么dp[i][j] = dp[i-1][j-1]，即不需要进行任何操作。

如果不相等，要么进行替换操作，那么dp[i][j] = dp[i-1][j-1] + 1；要么进行删除操作，那么dp[i][j] = dp[i-1][j] + 1；要么进行插入操作，那么dp[i][j] = dp[i][j-1] + 1。

最后返回dp[A.length()][B.length()]就是最短编辑距离。

2.题目二：修电线这道题目给出了一个无向图，你需要修复其中一条电线，使得修复后的图是一个树。

首先我们可以将该图表示为一个邻接矩阵，然后使用深度优先搜索(DFS)来遍历图。

在进行DFS的过程中，记录下每个节点的父节点，并检查是否存在回路。

如果存在回路，则将回路中的任意一条边删除即可得到一个树。

如果不存在回路，则对于任意一个非树边，将其替换成树边即可。

3.题目三：双链表这道题目给出了一个长度为n的双链表，每个节点包含一个值和指向前后节点的指针。

要求在双链表中执行以下操作：插入节点、删除节点、查询节点值、查询区间最大值、查询区间和。

为了高效地执行这些操作，我们可以使用双端队列(Deque)来实现双链表。

双端队列是一种具有队列和栈的特性的数据结构，可以在队列的前端和后端进行插入和删除操作，时间复杂度均为O(1)。

一、进制(这种题型你们可以看复印的资料上比较详细)(十一届)3.和十进制数23的值相等的二进制数是（D ）。

A. 10110B.11011C.11011D.10111E.10011(十一届)18.(3725)8+(B)16的运算结果是（B ）。

A.(3736)8B.(2016)10C.(1111110000)2D.(3006)10E.(7B0)16（十二届）15. 与十进制数1770对应的八进制数是（C ）。

A. 3350B.3351C.3352D.3540（十二届）18.(2010)16 +(32)8的结果是（A ）。

A.(8234)10B.(202B)16C.(20056)8D. (100000000110)2（十三届）17．与十进制数1770对应的八进制数是（C）。

A．3350 B．3351 C．3352 D．3540（十三届）19．(2070)16 + (34)8 的结果是（A）。

A．（8332）10 B．（208A）16 C．（100000000110）2D．(20212)8(十四届)8．与十进制数28.5625相等的四进制数是（ D ）。

A．123.21 B．131.22 C．130.22 D．130.21(十四届)12．(2008)10+(5B)16的结果是（ A ）。

A．（833）16 B．（2089）10 C．（4163）8 D．（100001100011）2二、字符串(十一届)1.在字符串“ababacbabcbdecced”中出现次数最多的字母出现了（B）次。

A.6B.5C.4D.3E.2（十四届）2．设字符串S=”Olympic”，S的非空字串的数目是（A ）。

A．28 B．29 C．16 D．17三、（“∧”逻辑与也称交运算若A 为真且B 为真,则命题A ∧B 为真;否则为假；“∨”逻辑或也称并运算只要A 或者B 之中一个为真,则命题A ∧B 为真;否则为假）(十一届)2.设全集I={a,b,c,d,e,f,g,h}，集合A={a,b,c,d,e,f}，B={c,d,e}，C={a,d}，那么集合A∩B∩~C为（A）。

NOIP部份试题分析和解答南宁三中孙国强QQ： 393936008竞赛试题名称算法N01P2004津津的储蓄计划模拟合并果子排序+二分杏找合唱队形动态规划虫食算搜索N01P2005谁拿了最多奖学金模拟过河数学或动态规划篝火晚会图论或数学等价表达式分治NOIP2006能量项链动态规划金明的预算方案动态规划作业调度方案模拟2”k进制数数学+高精N01P2007统计数字排序字符串的展开模拟知阵取数游戏动态规划+高精树网的核图论N01P2008笨小猴模拟火柴棒等式搜索或数学传纸条动态规划双栈排序图论一、枚举：I 1 1 e ! 11 It I H It 1 LJ n. -i "i JIJ iri j注意：1.加号与等号各自需要两根火柴棍2.如果A,B,则A+B=C与B+A=C视为不同的等式（A、B、0=0）3.n根火柴棍必须全部用上【输入】输入文件matches.in共一行，乂一个整数n （nv=24）。

【输出】输出文件matches.out共一行，表示能拼成的不同等式的数目。

【输入输出样例1 ]matches, in matches, out142【输入输出样例1解释】2个等式为0+1=1和1+0=1 □【输入输出样例2】matches, in matches, out189【输入输出样例2解释】9个等式为: 0+4=4 0+11=11 1+10=112+2=42+7=94+0=47+2=9 10+1=11 11+0=11既然我们用枚举的方法，就要确定枚举什么？枚举的数量（范）有多少，估算时间和空间复杂度。

2.举例：一-年一度的高一YL杯超级篮球赛开赛了。

当然，所谓超级，意思是参赛人数可能多余5人。

小三对这项篮球非常感兴趣，所以一场都没有落下。

每个中午都准时守侯在篮球场看比赛。

经过一个星期的研究，小三终于对篮球的技战术找到了一丝丝感觉了。

他发现打YL 杯的每个班都有一奁相似的进攻战术：1:控球后卫带球到前场，找到一个最佳攻击点（x,y）2:所有除控卫以外的队员都从各自的当前位置迅速向（x,y）移动3:控球后卫根据场上情况组织进攻这个战术对于一般情况是非常奏效的，但是每个队员毕竞不像小三一样每天精力过剩, 每个队员都有一个疲劳指数W,显然对于每个队员的移动需要消耗一些能量。

历届问题求解NOIP1998 普及二、问题求解：（20%） 1．已知一个数列U 1，U 2，U 3，…，U N ，… 往往可以找到一个最小的K 值和K 个数a 1，a 2， …，a k 使得数列从某项开始都满足： 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 。

试对数列12，22，32，…，n 2,…求K 和a 1,a 2, …,a K 使得（A ）式成立。

{7%} 2．某班有50名学生，每位学生发一张调查卡，上写a ，b ，c 三本书的书名，将读过的书打 ，结果统计数字如下： 只读a 者8人；只读b 者4人；只读c 者3人；全部读过的有2人；读过a ，b 两本书的有4人；读过a ，c 两本书的有2人；读过b ，c 两本书的有3人；{6%} （1）读过a 的人数是 （2）一本书也没有读过的人数是 3．任给自然数n ，k ， 1≤K ≤9 ，按如下计算步骤求序列X J X J-1……X 0的步骤：{8%} （1） j=0 （2） 如果N>=K 则转第3步，否则转第7步（3） X j = N MOD K {div表示整数除法，结果取整数； （4） N =N DIV K mod 表示整除取余数}（5） j=j+1 （6） 回第2步（7） X j = N（8） 结束试求当： N=1998， K=3时，X J X J-1……X 0 之值。

NOIP1998 提高 二、问题求解：(21%)1、已知一个数列U 1，U 2，U 3，…U n ，…往往可以找到一个最小的k 值和k 个数a 1，a 2，…，a k ，使得数列从某项开始都满足： 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 。

影响接下来的发挥。 • E 深呼吸，心理暗示 • 比赛之前一定要淡定！ • 遇到卡壳的情况，深呼吸，上厕所洗把脸！ • 相信自己只要把该拿到的分拿到，考出一个不让自己后悔的分数，就是自己的进步。 • 充分利用考试剩余的时间得到尽量多的分数（就像背包问题一样规划，用有限的时间来拿最多的分啊），而不管其余人的表现。
两个主要方面
• 竞赛中我们的目的就是得分。在比赛中，将自己能力范围内的分全部抓住， 不丢掉不该丢的分，就是最好的得分方式。
• 减少非受迫性失误：会做的都做对 • 在减少失误的前提下增加得分：不会做的都蒙对
减少非受迫性失误：
• 理解题目有误 • 思路想法错误 • 时间分配不合理 • 调试失误 • 心态失衡 • 低级失误
年份 2017 2016 2015 2014 2013 2012 2011
T1
T2
T3
T4
T5
打表+ 扩欧 模拟
模拟
模拟
快速 幂 模拟
模拟
模拟
LCA+树上 差分 tarjan+拓 扑 图遍历+二 次展开式 逆序对
高精度+贪 心 贪心
tarj;剪枝+ 状压 背包DP
• B 三思而后行： • 在草稿纸上，而非大脑干想，推算自己的思路 • 有了思路后验算样例 • 遇到熟悉的题目要十分警惕，先要在草稿纸上演算计算步骤，并测试其正确性 • 写下代码前要有充足的思考时间，最好举例子通过草稿验证 • 不要写从未接触过/极其不熟练的算法，即使之前听说过
时间分配不合理：
• 有的同学可能一上来就和一道难题较上劲了，（主观认为这道题目十分简单大家都会做，我做不出来就落后了 / 我做过类似的题目，别人没有做过， 我做了就能拉分了），在编程、调试等环节花了大量时间，导致其他的题目得分不理想。

第14页，共31页。
金币 (noip2015普及组第一题)
国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两 天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每 天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；
这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在 之后的连续N+1天里，每天收到N+1枚金币。 请计算在前K天里，骑士一共获得了多少金币。
输入格式： 输入文件只有1行，包含一个正整数K，表示发放金币的天数。
输出格式：
输出文件只有1行，包含一个正整数，即骑士收到的金币数。 输入输出样例
输入样例：
1000
输出样例： 29820
第15页，共31页。
螺旋方阵 (noip2014普及组第三题)
一个n行n列的螺旋矩阵可由如下方法生成： 从矩阵的左上角(第1行第1列)出发，初始时向右移动；
如果前方是未曾经过的格子，则继续前进，否则右转；重 复上述操作直至经过矩阵中所有格子。根据经过顺序，在
格子中依次填入1,2,3,....，便构成了一个螺旋矩阵。 现给出矩阵大小n以及i和j，请你求出该矩阵中第i行第j
列的数是多少。
下图是一个n=4时的螺旋矩阵。
第16页，共31页。
螺旋方阵 (noip2014普及组第三题)
请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。 比如在给定范围[2, 22]，数字2在数2中出现了1次，在数12 中出现了1次，在数20中出现了1次，在数21中出现了1次， 在数22中出现了2次，所以数字2在该范围内一共出现了6次。 输入格式 输入共一行，为两个正整数L和R，之间用一个空格隔开。 输出格式

信息学初赛问题求解部分(第8-15届)问题求解(共2题,每题5分,共计10分)(第八届)1、如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。

其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。

现已知第一个到达出口的是3号车厢,请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。

解:此题主要考查栈的先进后出及队列先进先出的概念,给合枚举,因为3要最先出去,肯定要把1,2依次压入栈中,所以出队列的时候,2肯定在1的前面。

共有9种。

32145,32154,32415,32451,32541,34215,34251,34521,35421 2、将N个红球和M 个黄球排成一行。

例如:N=2,M=3可得到以下6种排法: 红红黄黄黄红黄红黄黄红黄黄红黄黄红红黄黄黄红黄红黄黄黄黄红红问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法)解:分析:要计算出N=4,M=3的排法。

球的总数是7个,我们可以理解为:有7个可以用来存放这些球的箱子,如下图:怎样将这些球放入相应的箱子中呢?如果这7个球完全不一样,我们很容易知道,存放的方法就是7的全排列。

但实际上,这7个球只分为两种:红球和黄球。

所以,只要我们把其中任意一种球的存放位置确定好,问题就算解决了。

剩下的球只需往空的箱子里面放。

比如,我们要确定红球的存放位置。

红球一共有4个。

要把4个红球放入已知的7个箱子中,因为这4个红球都是一样的,所以存放的方法实际上就是从7个箱子中任取4个的组合,即:。

直接套用组合数公式进行计算 C73=7*6*5/3*2*1=35(第九届)1、现在市场上有一款汽车A很热销,售价是2万美元。

汽车A每加仑汽油可以行驶20英里。

普通汽车每年大约行驶12000英里。

油价是每加仑1美元。

不久我公司就要推出新款节油汽车B,汽车B每加仑汽油可以行驶30英里。

现在我们要为B制定价格(它的价格略高于A):我们预计如果用户能够在两年内通过节省油钱把B高出A的价钱弥补回来,则他们就会购买B,否则就不会购买B。