NOIP 2006年普及组解题报告
- 格式：pdf
- 大小：87.16 KB
- 文档页数：5
下载文档原格式
合集下载
NOIP2006提高组复赛解题报告
1、DP，f表示合并区间内的珠子获得最大能源2、DP，可以先把主件和附件的搭配全部分出来，然后分阶段做背包3、模拟4、递推+高精度1．这题具有最优子结构的性质，与合并石子相似，所以可以用动态规划来做。
首先将数据存于c数组中，每次需要枚举一下起始点i和终点j的位置，还要枚举起点和终点之间一个断点k的位置，表示第i—k个珠子已经合并在了一起，第k—j个珠子也已经合并在了一起，当前要合并的是这两个已经合并在了一起的小珠子，这样就把一个问题分成了许多子问题。
当前一次操作所产生的能量K=c[i]*c[k]*c[j]具体做法是：开一个二维数组a，a[i,j]表示从i开始到j结束这一段中所有珠子合并所能产生的能量的最大值。
然后先枚举段的长度i（i为2到N），接着枚举开始位置j，由i, j 可推出结束位置k。
然后枚举断点位置v，v为j+1到k-1之间。
在每个断点处断开所能获得的能量为K=c[j]*c[v]*c[k]+a[j,v]+a[v,k]。
取这中间的一个最大值赋给a[j , k]。
这样做的时间复杂度为O(n3)，因为N<=100，所以时间上肯定没有问题。
最后a[i,i]的最大值就是合并所有珠子后所能产生的能量的最大值。
constmaxn=100;varc:array[0..maxn] of longint;a:array[0..maxn,0..maxn] of longint;n,i,j,k,t,v,u,max:longint;beginassign(input,'energy.in'); reset(input);assign(output,'energy.out'); rewrite(output);readln(n);for i:=0 to n-1 do read(c[i]);fillchar(a,sizeof(a),0);for i:=2 to n do beginfor j:=0 to n-1 do begink:=(j+i) mod n;max:=0;for v:=j+1 to j+i-1 do beginu:=v mod n;t:=c[j]*c[u]*c[k]+a[j,u]+a[u,k];if t>max then max:=t;end;a[j,k]:=max;end;end;max:=0;for i:=0 to n-1 doif a[i,i]>max then max:=a[i,i];writeln(max);close(input); close(output)end.2、此题初看MS是01背包问题，只是多了附件这个条件。
【通用】信息学奥赛NOIP普及组历届试题分析.ppt
枚举法其实是最简单的搜索算法。
.,.,
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，每两个整
.,.,
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，每两个整
NOIP2006普及组C 题目及答案
第十二届全国青少年信息学奥林匹克联赛初赛试题 2006（普及组C++ 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确答案.）1. 在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。
A. 沃尔夫奖B. 诺贝尔奖C. 菲尔兹奖D. 图灵奖2. 在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。
A. gcc/g++B. Turbo PascalC. RHIDED. free pascal3. 以下断电之后仍能保存数据的有（）。
A. 寄存器B. ROMC. RAMD. 高速缓存4．Linux是一种( )。
A. 绘图软件B. 程序设计语言C. 操作系统D. 网络浏览器5. CPU是( )的简称。
A. 硬盘B. 中央处理器C. 高级程序语言D. 核心寄存器6. 在计算机中，防火墙的作用是（）。
A. 防止火灾蔓延B.防止网络攻击C. 防止计算机死机D. 防止使用者误删除数据7. 在下列关于计算机语言的说法中，不正确的是（）。
A. Pascal和C都是编译执行的高级语言B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C. C++是历史上的第一个支持面向对象的计算机语言D. 与汇编语言相比，高级语言程序更容易阅读8. 在下列关于计算机算法的说法中，不正确的是（）。
A. 一个正确的算法至少要有一个输入B. 算法的改进，在很大程度上推动了计算机科学与技术的进步C. 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性D. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法9. 在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。
A. 选择排序B. 冒泡排序C. 插入排序D. 基数排序10．在编程时（使用任一种高级语言，不一定是C++），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。
NOIP2006年题解解读
金明的预算方案
输入输出要求
【输入文件】 输入文件budget.in 的第1行，为两个正整数，用一个空格隔开： N m （其中N（<32000）表示总钱数，m（<60）为希望购买物品 的个数。） 从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据， 每行有3个非负整数 v p q （其中v表示该物品的价格（v<10000），p表示该物品的重要 度（1~5），q表示该物品是主件还是附件。如果q=0，表示该 物品为主件，如果q>0，表示该物品为附件，q是所属主件的 编号） 【输出文件】 输出文件budget.out只有一个正整数，为不超过总钱数的物品 的价格与重要度乘积的总和的最大值（<200000）。
2 3 4 5 6
i>=2，即对前i件物品，花费不超过k(0<=k<=10)，价
7
8
9
10
1
2 3 4 5
0
0
0
0
0
0
0
0
0
0
0
0
16
16
16
If k>=w[i] then ｛第i件物品可要可不要， 不要 a[i,k]:=a[i-1,k]； 要 a[i,k]:=a[i-1,k-w[i]]+w[i]*v[i]｝ a[i,k]:=max(a[i-1,k], a[i-1,k-w[i]]+w[i]*v[i])
0 1 2 3 4 5 0 0 1 0 0 2 0 0 3 0 0 4 0 ? 5 0 6 0 7 0 8 16 9 16 10 16
W 8 4 3 4 2 V 2 5 5en ｛第i件物品可要可不要， 不要 a[2-1,4]=a[1,4]=0； 要 a[2-1,4-w[2]]+w[2]*v[2]=a[1,0]+4*5=20｝ max(a[2-1,k], a[2-1,k-w[2]]+w[2]*v[2])=max(0,20)
NOIP2006解题报告-陈启峰
显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是 唯一的，请你计算出该方案完成全部任务所需的总时间。 【输入文件】
输入文件 jsp.in 的第 1 行为两个正整数，用一个空格隔开：
500比较小，用搜索是可以过全部数据的。比赛时我写的是一个 windows
下可以所有数据的搜索程序，可是在 linux 下就无法编译~-~。 这里就讲讲与背包算法相似的动态规划。首先，我们把主件和其附件看成是
一个整体。 当主件有 0 个附件时，有 2 种选择：选主件、什么都不选； 当主件有 1 个附件时，有 3 种选择：主件和附件、附件、什么都不选； 当主件有 2 个附件时，有 5 种选择：主件和两个附件，附件 1、附件 2、附
关于竞赛中不同语言使用限制的说明
一．关于使用 Pascal 语言与编译结果的说明
1．对于 Pascal 语言的程序，当使用 IDE 和 fpc 编译结果不一致时，以 fpc 的 编译结果为准。
2．允许使用数学库(uses math 子句)，以及 ansistring。但不允许使用编译开 关（最后测试时 pascal 的范围检查开关默认关闭：{$R-,Q-,S-}），也不支 持与优化相关的选项。
(2) 同一时刻每一台机器至多只能加工一个工件。
另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。 由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍 可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“1 1 2 3 3 2”。
第 7／15页
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数
vpq （其中 v 表示该物品的价格（v<10000），p 表示该物品的重要度（1~5）， q 表示该物品是主件还是附件。如果 q=0，表示该物品为主件，如果 q>0，表示 该物品为附件，q 是所属主件的编号） 【输出文件】
输入文件 jsp.in 的第 1 行为两个正整数，用一个空格隔开：
500比较小，用搜索是可以过全部数据的。比赛时我写的是一个 windows
下可以所有数据的搜索程序，可是在 linux 下就无法编译~-~。 这里就讲讲与背包算法相似的动态规划。首先，我们把主件和其附件看成是
一个整体。 当主件有 0 个附件时，有 2 种选择：选主件、什么都不选； 当主件有 1 个附件时，有 3 种选择：主件和附件、附件、什么都不选； 当主件有 2 个附件时，有 5 种选择：主件和两个附件，附件 1、附件 2、附
关于竞赛中不同语言使用限制的说明
一．关于使用 Pascal 语言与编译结果的说明
1．对于 Pascal 语言的程序，当使用 IDE 和 fpc 编译结果不一致时，以 fpc 的 编译结果为准。
2．允许使用数学库(uses math 子句)，以及 ansistring。但不允许使用编译开 关（最后测试时 pascal 的范围检查开关默认关闭：{$R-,Q-,S-}），也不支 持与优化相关的选项。
(2) 同一时刻每一台机器至多只能加工一个工件。
另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。 由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍 可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“1 1 2 3 3 2”。
第 7／15页
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数
vpq （其中 v 表示该物品的价格（v<10000），p 表示该物品的重要度（1~5）， q 表示该物品是主件还是附件。如果 q=0，表示该物品为主件，如果 q>0，表示 该物品为附件，q 是所属主件的编号） 【输出文件】
NOIP2006普及组初赛试题答案
第十二届全国青少年信息学奥林匹克联赛初赛试题（普及组Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确答案.）。
1.在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。
A.沃尔夫奖B.诺贝尔奖C.菲尔兹奖D.图灵奖2.在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。
A.gcc/g++B.Turbo PascalC.RHIDED.free pascal3.以下断电之后仍能保存数据的有（）。
A.寄存器B.ROMC.RAMD.高速缓存4．Linux是一种()。
A.绘图软件B.程序设计语言C.操作系统D.网络浏览器5.CPU是()的简称。
A.硬盘B.中央处理器C.高级程序语言D.核心寄存器6.在计算机中，防火墙的作用是（）。
A.防止火灾蔓延B.防止网络攻击C.防止计算机死机D.防止使用者误删除数据7.在下列关于计算机语言的说法中，不正确的是（）。
A.Pascal和C都是编译执行的高级语言B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C.C++是历史上的第一个支持面向对象的计算机语言D.与汇编语言相比，高级语言程序更容易阅读8.在下列关于计算机算法的说法中，不正确的是（）。
A.一个正确的算法至少要有一个输入B.算法的改进，在很大程度上推动了计算机科学与技术的进步C.判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法9.在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。
A.选择排序B.冒泡排序C.插入排序D.基数排序10．在编程时（使用任一种高级语言，不一定是Pascal），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。
【NOIP2006普及组】开心的金明
【NOIP2006普及组】开⼼的⾦明
看过题后，你可能会发现这是很典型的0-1背包问题，即要么选择这件要么不选。
0-1背包问题最经典的解法就是动态规划了。
当然这道题的数据范围较⼩，也可以⽤暴搜（暴⼒搜索）来做，即枚举所有情况。
我们⽤递归来实现⼀下。
对于每⼀件物品就模拟两种情况选或者不选，千万不要漏掉哪⼀种情况，最后求取最⼤值就好了。
（由于我们当时模拟赛，所以写了⽂件读取数据，请见谅。
）
好了，暴搜的解法就介绍到这⾥，接下来，要介绍经典解法——动态规划。
动态规划最重要的就是建⽴递推式，根据上⾯讲解我们已经明确了对于每个物品依次检查选或不选，⽤dp[i][j]表⽰前 i 个物品在 j ⾦额下的最优解（结果最⼤）。
如果j放不下第i个物品的话，那么就只能从编号为[1,i-1]的物品中选择了，也就是dp[i-1][j]的值。
所以，
dp[i][j] = dp[i-1][j]; （其中，j < v[i]）
那么j可以放的下这个物品的时候应该怎么办呢？很明显，我们有两种选择，选或不选，之后我们取较⼤的值。
选 dp[i-1][j-v[i]]+v[i]*p[i];
不选 dp[i-1][j];
所以我们得到递推式
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+v[i]*p[i]);（其中，j>=v[i]）
把两种情况整理⼀下，
怎么样？思路明确多了吧！
根据递推式来写代码就好了。
最后附上AC代码。
NOIP2006普及其组C题目及其规范标准答案
第十二届全国青少年信息学奥林匹克联赛初赛试题 2006（普及组C++ 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确答案.）1. 在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。
A. 沃尔夫奖B. 诺贝尔奖C. 菲尔兹奖D. 图灵奖2. 在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。
A. gcc/g++B. Turbo PascalC. RHIDED. free pascal3. 以下断电之后仍能保存数据的有（）。
A. 寄存器B. ROMC. RAMD. 高速缓存4．Linux是一种( )。
A. 绘图软件B. 程序设计语言C. 操作系统D. 网络浏览器5. CPU是( )的简称。
A. 硬盘B. 中央处理器C. 高级程序语言D. 核心寄存器6. 在计算机中，防火墙的作用是（）。
A. 防止火灾蔓延B.防止网络攻击C. 防止计算机死机D. 防止使用者误删除数据7. 在下列关于计算机语言的说法中，不正确的是（）。
A. Pascal和C都是编译执行的高级语言B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C. C++是历史上的第一个支持面向对象的计算机语言D. 与汇编语言相比，高级语言程序更容易阅读8. 在下列关于计算机算法的说法中，不正确的是（）。
A. 一个正确的算法至少要有一个输入B. 算法的改进，在很大程度上推动了计算机科学与技术的进步C. 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性D. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法9. 在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。
A. 选择排序B. 冒泡排序C. 插入排序D. 基数排序10．在编程时（使用任一种高级语言，不一定是C++），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。
noip2006
NOIP2006复赛普及组解题报告【第一题解题思想】：这道题属于容易题，但是题目难度大于NOIP2005和2004普及组第一题，和去年第二题难度相当后者略低一些。
解法1：我们可以用先去掉重复（读入第i个数，和他前面的i-1个数比较），然后用简单排序和冒泡排序排序，最后输出结果。
解法2：运用插入排序（略加修改），边排序边除掉重复。
解法3：直接排序，不去掉重复，计算出不重复的元素个数，输出不重复的元素即可。
如果用数组A存储这些随机数，对于2到N个元素需要比较A是否等于A[i-1]。
解法4：开一个1到1000初值均为假的布尔数组A。
用整型变量X读入N个随机数，赋A[X]的值为真。
统计数组中值为真的元素个数即M，从i从1到1000输出A值为真的i。
这种方法可以算作哈希表的简单应用。
解法5：很多人想到排序，效率大概是O(n^2)吧，其实还有个更简单的方法。
用一个1到1000的数组储存每个数的出现情况，t每出现一次，a[t]=a[t]+1，而且，同时操作if(a[t]>1) 则总数=总数-1。
然后从1到1000的循环，如果a≠0，输出，这样就根本不用排序了。
大概这个应该是最优算法吧。
O(n)的效率。
program random(input,output);var a:array[1..1000] of integer; / ’a是记录数组，相当于数轴，与数一一对应，temp 是临时存储数据，n和题目一样，记录不相同的数的个数’ /i,m,temp,n:integer;beginassign(input,'d:\data\random.in');reset(input);assign(output,'d:\data\random.out');rewrite(output);read(n);readln;fillchar(a,sizeof(a),0); /*初始化数组为0，pascal有fillchar*/m:=n;for i:=1 to n dobeginread(temp);a[temp]:=a[temp]+1; /*记录是哪个数*/if a[temp]>1 then dec(m);end;write(m);writeln;for i:=1 to 1000 doif a>0 then / *如果a不为0。
NOIP普及组历届试题分析
8.
readln;
20.
9. end;
21.
10. for i:=1 to n do
22.
11. begin
23.
12. for j:=1 to m do
24.
13.
begin
25.
14.
s:=0;
26.
15.
if a[i,j]='*' then write(a[i,j2])7.
28.
29.
30.
else begin if a[i][j-1]='*' then inc(s); if a[i][j+1]='*' then inc(s); if a[i+1][j-1]='*' then inc(s); if a[i+1][j+1]='*' then inc(s); if a[i+1][j]='*' then inc(s); if a[i-1][j-1]='*' then inc(s); if a[i-1][j+1]='*' then inc(s); if a[i-1][j]='*' then inc(s); write(s);
8.
begin
9.
read(f[i]);
10.
vis[f[i]]:=1;
11.
end;
12. ans:=0;
13. for a:=1 to n do
14.
for b:=1 to n do
15.
if (vis[f[a]+f[b]]=1)and(a<>b) then
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
using namespace std; int s[30001]; int main(int argc, char *argv[]) {
int i, j, n, m, v, w; cin >> n >> m; for ( i = 0 ; i < m ; i++ ) {
cin >> v >> w; for ( j = n ; j >= v ; j-- )
注 ： 本 份 解 题 报 告 的 参 考 答 案 均 采 用 G++ 编 译 器 通 过 ， 并 已 经 在 /JudgeOnline中测试通过，欢迎大家在在线测评中提交检测，如遇到
问题可到：北京市科协网站的在线交流（/bjnoi/）或到作者的交流 论坛的相应板块中提交。输入输出形式，采用的均为标准输入输出， 如果需要针对竞赛，请更改为相应的文件操作即可。
if (st[i] != z[t - (w - 1) + i]) {
f = false; break; } if ( f ) return; i= 0; while (st[w - i - 1] == z[t - i]) i++; st[w - i - 1]++; c = st[w - i - 1]; for (x = 1 , j = w - i ; j < w ; j++ , x++) st[j] = c + x; } int main(int argc, char *argv[]) { char st[28] , *str; char str1[28]; int i, j, k; cin >> s >> t >> w; cin >> st; str = st; for ( i = 0 ; i < 5 ; i++ ) { strcpy(str1 , str); pre(str); if ( strcmp(str1 , str) != 0) cout << str << endl; else break; } //system("PAUSE"); return EXIT_SUCCESS; } 四、数列 没有想到最后一道题会这么简单，看到题目以后，看到数列首先有些困惑，但是，括 号里的内容，却让思路豁然开朗。这个表达式，明显的表现出了，加法算式的部分选择，这 种情况很正常的想到了 2 进制的 01 转化后和加法算式部分的乘积后的结果。而且，仔细观 察在这道题目中，我们甚至不用生成 2 进制的 01 形式，只需要将 N 转化成为 2 进制就可以 了。可以说，真的是不能够再简单了。
using namespace std; int s[1001] , x[1001]; int main(int argc, char *argv[]) {
int i, t, n; cin >> n; while (n--) {
cin >> t; s[t]++; } for ( t = 0 , i = 0 ; i <= 1000 ; i++ ) if (s[i])
x[t++] = i; cout << t << endl; cout << x[0]; for ( i = 1 ; i < t ; i++ )
cout << " " << x[i];
cout << endl; //system("PAUSE"); return EXIT_SUCCESS; } 二、开心的金明 在 2005 年，大家熟悉了“采药”后，应该说这道题，是一道送分题目。分析也很简单， 用消耗的 N 元钱，来换价值和重要度的乘积。而结构上，属于明显的 01 背包问题。 参考程序如下： #include <cstdlib> #include <iostream>
参考程序如下： #include <cstdlib> #include <iostream>
using namespace std; int s[33]; int kf(int k, int x) {
int i, s; s = 1; for ( i = 0 ; i < x ; i++ )
s *= k; return s; } int main(int argc, char *argv[]) { int k, n, i, w; int t; cin >> k >> n; w = 0; while ( n != 0 ) {
using namespace std; char z[28] = "0abcdefghijklmnopqrstuvwxyz"; int s, t, w; void pre(char *st) {
char c;
int i, j, x; bool f; f = true; for (i = w - 1; i >= 0 ; i-- )
下面，我们来分别看一看各个题目。 一、明明的随机数 在这道题中，再次考察了 2005 年中校门外的树的一一对应的哈希表的知识点，当然， 对待数的排序来说，更是简化了的“箱排序”思想。用至少有 1000 个数组元素的数组，用 位置和数值，一一对应。用位置代替数值。每得到一个数值就在数组的相应位置上做一个标 记或者做加。这样，从头到尾统计一下数值非零的位置就知道有多少个不相同的数字了。可 以然后再记录下来这些数字，从头到尾输出即可。当然，本题因为是要输出个数，并且个数 要求在前，所以需要从头儿到尾统计一下个数。 参考程序： #include <cstdlib> #include <iostream>
if (s[j - v] + v * w > s[j] ) s[j] = s[j - v] + v * w;
} cout << s[n] << endl; //system("PAUSE"); return EXIT_SUCCESS; } 三、Jam 的计数法 这道题在整套题中，属于最难的一题了。也是一道单纯的字符串题目。这道题，一般 会给人一种错觉，好似是回溯的题目去查找，但如果仔细分析，其实题目非常简单。就是要 从后面查找可以改变的位置。如果没有可以改变的了，就代表后面没有数字了。如果有可以 改变的，则这个字母可以做加 1 的操作，而这个可以改变的位置后面的所有字母均需要变的 跟改变的字母连续变化即可。只要把握好这两点，题目可以非常简单的解决。 参考程序如下： #include <cstdlib> #include <iostream>
s[w] = n % 2; n /= 2; w++; } /* for ( i = 0 ; i < w ; i++ ) cout << s[i]; cout << endl; */ t = 0; for ( i = 0 ; i < w ; i++ ) { t = t + s[i] * kf(k , i); } cout << t << endl; //system("PAUSE"); return EXIT_SUCCESS; }NOIP 2006 年普及组解报告北京市八一中学 王祺磊
2006 年，普及组的题目出的略显简单，和提高组题目形成鲜明对比。但是，题目考察 面全面而有效，李老师的程序功底可见一斑。
题目上来说，主要考察了几个方面：模拟（主要是一一对应的哈希表使用），动态规划 （继续了 2005 年的背包问题），字符串操作（规则简单，难度不深），取值规律（简化了的 2 进制全模拟取舍）。其实说简单，主要因为 2005 年普及组的采药刚刚出了 01 背包，在本 年中又出了一道，让人突出的感觉到了 01 背包的重要，也为信息学的动态规划时代，拉开 了序幕。从 2006 年起，动态规划就成了信息学教学的重中之重。而最后一题的规律过于简 单，而且，去掉了，生成所有情况的较复杂部分，只保留了 2 进制转换后的部分。考察点显 得有些过于直白了。
int i, j, n, m, v, w; cin >> n >> m; for ( i = 0 ; i < m ; i++ ) {
cin >> v >> w; for ( j = n ; j >= v ; j-- )
注 ： 本 份 解 题 报 告 的 参 考 答 案 均 采 用 G++ 编 译 器 通 过 ， 并 已 经 在 /JudgeOnline中测试通过，欢迎大家在在线测评中提交检测，如遇到
问题可到：北京市科协网站的在线交流（/bjnoi/）或到作者的交流 论坛的相应板块中提交。输入输出形式，采用的均为标准输入输出， 如果需要针对竞赛，请更改为相应的文件操作即可。
if (st[i] != z[t - (w - 1) + i]) {
f = false; break; } if ( f ) return; i= 0; while (st[w - i - 1] == z[t - i]) i++; st[w - i - 1]++; c = st[w - i - 1]; for (x = 1 , j = w - i ; j < w ; j++ , x++) st[j] = c + x; } int main(int argc, char *argv[]) { char st[28] , *str; char str1[28]; int i, j, k; cin >> s >> t >> w; cin >> st; str = st; for ( i = 0 ; i < 5 ; i++ ) { strcpy(str1 , str); pre(str); if ( strcmp(str1 , str) != 0) cout << str << endl; else break; } //system("PAUSE"); return EXIT_SUCCESS; } 四、数列 没有想到最后一道题会这么简单，看到题目以后，看到数列首先有些困惑，但是，括 号里的内容，却让思路豁然开朗。这个表达式，明显的表现出了，加法算式的部分选择，这 种情况很正常的想到了 2 进制的 01 转化后和加法算式部分的乘积后的结果。而且，仔细观 察在这道题目中，我们甚至不用生成 2 进制的 01 形式，只需要将 N 转化成为 2 进制就可以 了。可以说，真的是不能够再简单了。
using namespace std; int s[1001] , x[1001]; int main(int argc, char *argv[]) {
int i, t, n; cin >> n; while (n--) {
cin >> t; s[t]++; } for ( t = 0 , i = 0 ; i <= 1000 ; i++ ) if (s[i])
x[t++] = i; cout << t << endl; cout << x[0]; for ( i = 1 ; i < t ; i++ )
cout << " " << x[i];
cout << endl; //system("PAUSE"); return EXIT_SUCCESS; } 二、开心的金明 在 2005 年，大家熟悉了“采药”后，应该说这道题，是一道送分题目。分析也很简单， 用消耗的 N 元钱，来换价值和重要度的乘积。而结构上，属于明显的 01 背包问题。 参考程序如下： #include <cstdlib> #include <iostream>
参考程序如下： #include <cstdlib> #include <iostream>
using namespace std; int s[33]; int kf(int k, int x) {
int i, s; s = 1; for ( i = 0 ; i < x ; i++ )
s *= k; return s; } int main(int argc, char *argv[]) { int k, n, i, w; int t; cin >> k >> n; w = 0; while ( n != 0 ) {
using namespace std; char z[28] = "0abcdefghijklmnopqrstuvwxyz"; int s, t, w; void pre(char *st) {
char c;
int i, j, x; bool f; f = true; for (i = w - 1; i >= 0 ; i-- )
下面，我们来分别看一看各个题目。 一、明明的随机数 在这道题中，再次考察了 2005 年中校门外的树的一一对应的哈希表的知识点，当然， 对待数的排序来说，更是简化了的“箱排序”思想。用至少有 1000 个数组元素的数组，用 位置和数值，一一对应。用位置代替数值。每得到一个数值就在数组的相应位置上做一个标 记或者做加。这样，从头到尾统计一下数值非零的位置就知道有多少个不相同的数字了。可 以然后再记录下来这些数字，从头到尾输出即可。当然，本题因为是要输出个数，并且个数 要求在前，所以需要从头儿到尾统计一下个数。 参考程序： #include <cstdlib> #include <iostream>
if (s[j - v] + v * w > s[j] ) s[j] = s[j - v] + v * w;
} cout << s[n] << endl; //system("PAUSE"); return EXIT_SUCCESS; } 三、Jam 的计数法 这道题在整套题中，属于最难的一题了。也是一道单纯的字符串题目。这道题，一般 会给人一种错觉，好似是回溯的题目去查找，但如果仔细分析，其实题目非常简单。就是要 从后面查找可以改变的位置。如果没有可以改变的了，就代表后面没有数字了。如果有可以 改变的，则这个字母可以做加 1 的操作，而这个可以改变的位置后面的所有字母均需要变的 跟改变的字母连续变化即可。只要把握好这两点，题目可以非常简单的解决。 参考程序如下： #include <cstdlib> #include <iostream>
s[w] = n % 2; n /= 2; w++; } /* for ( i = 0 ; i < w ; i++ ) cout << s[i]; cout << endl; */ t = 0; for ( i = 0 ; i < w ; i++ ) { t = t + s[i] * kf(k , i); } cout << t << endl; //system("PAUSE"); return EXIT_SUCCESS; }NOIP 2006 年普及组解报告北京市八一中学 王祺磊
2006 年，普及组的题目出的略显简单，和提高组题目形成鲜明对比。但是，题目考察 面全面而有效，李老师的程序功底可见一斑。
题目上来说，主要考察了几个方面：模拟（主要是一一对应的哈希表使用），动态规划 （继续了 2005 年的背包问题），字符串操作（规则简单，难度不深），取值规律（简化了的 2 进制全模拟取舍）。其实说简单，主要因为 2005 年普及组的采药刚刚出了 01 背包，在本 年中又出了一道，让人突出的感觉到了 01 背包的重要，也为信息学的动态规划时代，拉开 了序幕。从 2006 年起，动态规划就成了信息学教学的重中之重。而最后一题的规律过于简 单，而且，去掉了，生成所有情况的较复杂部分，只保留了 2 进制转换后的部分。考察点显 得有些过于直白了。