少儿编程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背包问题，只是多了附件这个条件。

2006年青少年信息学奥林匹克小学组复赛比赛时间3小时满分200分共4题注意事项：每道题目均有5组测试数据，每组测试数据均为10分，测试数据的范围均在题目中给出了描述。

每道题目都是文件输入、文件输出，屏幕的输入和输出无效。

题目的测试文件为xxx.in文件，请选手们注意，5组测试数据均放在同一个输入文件中，也就是你应该在你的程序最外层套一个循环，从而执行程序主体5次，对于每次运行程序主体，直接把本次结果输出到要求输出的xxx.out文件中，以方便评委的评测工作。

题目中一个样例就是对于一组数据的描述。

例如：给定两个整数a和b，求他们的和。

(假如输入文件文件：a.in , 输出文件：a.out)DIM a AS INTEGER, b AS INTEGERDIM casenum AS INTEGEROPEN "a.in" FOR INPUT AS #1OPEN "a.out" FOR OUTPUT AS #2FOR casenum = 1 TO 5 [ 注意此处循环了5次主体程序，就是为了解决5组数据] INPUT #1, a, b [ 程序主体]WRITE #2, a + b [ 程序主体]NEXT casenumCLOSE #1, #2上面的程序可以作为今天比赛的模板，[程序主体]部分可以替换为每道题目的具体代码。

提醒参赛选手，对于[程序主体]的开头要注意清空上一次循环存留下来的无用数据，以免造成这次运算的错误。

偶数世界源代码: even.bas输入文件: even.in输出文件: even.out假想我们生活在偶数世界里，在这个世界中只有正偶数。

下面就是这个世界中数的集合:Z = {2, 4, 6, 8, 10 ……}；在偶数世界中，除法有它特殊的规则，如果数a能被数b整除，那么a除以b的商也一定是个偶数。

例如2能整除8, 因为2 * 4 = 8。

但是2却不能整除6，因为2 * 3 = 6。

noip普及组复赛试题及答案一、选择题1. 在计算机科学中，以下哪个概念与数据结构最相关？A. 算法B. 操作系统C. 网络协议D. 编译原理答案：A2. 以下哪种排序算法的时间复杂度为O(n^2)？A. 快速排序B. 归并排序C. 堆排序D. 冒泡排序答案：D3. 在C++中，以下哪个关键字用于定义类？A. structB. unionC. enumD. typedef答案：A4. 以下哪个选项不是数据库管理系统（DBMS）的特性？A. 数据持久性B. 数据共享C. 数据加密D. 数据独立性答案：C5. 在计算机网络中，TCP和UDP协议分别属于哪一层？A. 传输层B. 应用层C. 网络层D. 物理层答案：A二、填空题1. 在计算机程序中，______ 用于定义数据的存储方式和组织形式。

答案：数据结构2. 一个算法的时间复杂度为O(1)，表示该算法的执行时间与输入数据的规模______。

答案：无关3. 在C++中，______ 是一种特殊的类，它提供了一种方式来定义数据类型。

答案：typedef4. 数据库管理系统（DBMS）通常包含数据定义语言（DDL）、数据操纵语言（DML）和______。

答案：数据控制语言（DCL）5. 在计算机网络中，______ 协议负责在网络层进行数据包的路由选择。

答案：IP三、简答题1. 请简述面向对象编程（OOP）的三个基本特征。

答案：封装、继承、多态2. 描述二分查找算法的基本步骤。

答案：二分查找算法的基本步骤包括：首先确定数组是有序的，然后取中间元素与目标值比较，如果中间元素等于目标值，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找，直到找到目标值或查找范围为空。

四、编程题1. 编写一个函数，实现对整数数组的排序。

答案：以下是一个简单的冒泡排序算法实现：```cppvoid bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {swap(arr[j], arr[j+1]);}}}}```2. 编写一个函数，实现计算一个整数的阶乘。

第十二年全国青少年信息学奥林匹克联赛提高组复赛试题联赛复赛试题〔NOIP2006提高组〕竞赛时间：2006年11月18日上午8：30—11：30关于竞赛中不同语言使用限制的说明一、关于使用Pascal语言与编译结果的说明1、关于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。

2、同意使用数学库(usesmath子句)，以及ansistring。

但不同意使用编译开关〔最后测试时pascal的范围检查开关默认关闭：{$R-,Q-,S-}〕，也不支持与优化相关的选项。

二、关于C++语言中模板使用的限制说明1、同意使用的部分：标准容器中的布尔集合，迭代器，串，流。

相关的头文件：2、禁止使用的部分：序列：vector，list，deque序列适配器：stack,queue,priority_queue关联容器：map,multimap,set,multiset拟容器：valarray散列容器：hash_map,hash_set,hash_multimap,hash_multiset 所有的标准库算法相关头文件：1、能量项链(energy.pas/c/cpp)【问题描述】在Mars星球上，每个Mars人都随身佩带着一串能量项链。

在项链上有N颗能量珠。

能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。

同时，关于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。

因为只有如此，通过吸盘〔吸盘是Mars人吸收能量的一种器官〕的作用，这两颗珠子才能聚合成一颗珠子，同时释放出能够被吸盘吸收的能量。

假如前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，那么聚合后释放的能量为〔Mars单位〕，新产生的珠子的头标记为m，尾标记为n。

需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。

显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

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复赛模拟试题2预览说明:预览图片所展示的格式为文档的源格式展示,下载源文件没有水印,内容可编辑和复制2013开明中学NOIP模拟试题2题目1、NBA总冠军（nba.pas/c/cpp）【问题描述】又要考试了，Ljw决定放松一下，就打开电视，看见了篮球赛，他立即想到了每年的NBA 总冠军队伍。

由于复习紧张，他只记起了一部分，记忆的内容是正确的，可能不是按时间顺序排列的，记忆的内容可能有重复。

现在请求学过编程的你帮助Ljw，按时间依次输出总冠军的球队（不能重复）。

（NBA 从1947A.D到2009A.D）【输入】输入文件nba.in的第一行是一个整数n（0<n<50）。

< bdsfid="75" p=""></n<50）。

<>接下来的n行，每行先是城市名（由大到小写字母、空格组成），后是时间（由数字组成）二者之间用空格隔开。

【输出】输出文件nba.out共n行，即排序后的NBA总冠军队伍。

每行先是时间，后是城市名。

【输入输出样例】2.买票（tickets.pas/c/cpp）【问题描述】周末Ztc想去剧场看演出，但他没有票。

这时，救世主Wzj出现了，他慷慨地愿意卖给Ztc 一些票。

Wzj手上共有n张票，但每张票的费用都不一样，贪心的ztc想要得到尽可能多的票，但又想花费最少，慷慨的wzj原意给连续的m张票。

Ztc 希望你能帮助他在花钱范围内取得最大的票数。

【输入】输入文件tickets.in的第一行是2个整数n,，f。

其中（2≤N≤1000000），表示票的数目，（10≤f≤10000），表示ztc身上的钱。

接下来的1行，有n个整数a（1≤a≤30），表示每一张票的票价。

【输出】输出文件tickets.out仅一行整数m，表示Ztc能得连续的最大票数。

【输入输出样例】【限制】50%的数据满足：2≤n≤10000100%的数据满足：2≤n≤10000003.逛街（shop.pas/c/cpp）【问题描述】某天，ZCL 在街上闲逛。

全国信息学奥林匹克分区联赛（NOIP）复赛提高组试题第一届全国信息学奥林匹克分区联赛（NOIP1995）复赛试题（提高组竞赛用时：3.5小时）1、编码问题设有一个数组A:ARRAY[0..N-1]OFINTEGER；数组中存放的元素为0～N-1之间的整数，且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后，求出其编码。

②给出数组A的编码后，求出A中的原数据。

2、灯的排列问题设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……N k（k表示不同颜色灯的个数）。

放灯时要遵守下列规则：①同一种颜色的灯不能分开；②不同颜色的灯之间至少要有一个空位置。

例如：N=8（格子数）；R=2（红灯数）；B=3（蓝灯数），放置的方法有：R-B顺序B-R顺序放置的方法总数为12种。

数据输入的方式为：NP1（颜色，为一个字母）N1（灯的数量）P2 N2……Q（结束标记，Q本身不是灯的颜色）程序要求：求出一种顺序的放置（排列）方案及放置（排列）方案总数。

3、积木块上的数字设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，8，如下图所示放置：其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。

计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的：计算所用到的计算符为：+，-，⨯，且无优先级之分（自左向右计算），运算符最多为2个。

如：3+4⨯5=35 5⨯4+3=23可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的：A=B⨯C+B也就是：8=2⨯3+2，15=3⨯4+3，……14=2⨯6+2程序要求：给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。

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;}输入：114 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找最长的路径的程序。

N O I’95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（高中组）（上机编程，完成时间：210分钟）<1>编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。

N-1），N1数据输入的方式为：NP1（颜色，为一个字母） N1（灯的数量）P2 N2……Q（结束标记，Q本身不是灯的颜色）程序要求：求出一种顺序的排列方案及排列总数。

<3> 设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，82个。

例如n=2时的比赛安排：队 1 2 3 4比赛 1==2 3==4 一天1==3 2==4 二天1==4 2==3 三天2．数制转换（20分）设有一个字符串A$的结构为：A$=’m<n>p’其中m为数字串（长度<=20），而n,p均为1或2位的数字串（其中所表达的内容在2-10之间）。

程序要求：从键盘上读入A$后（不用正确性检查），将A$中的数字串m(n进制)，以p进制的形式输出。

例如：A$=’48<10>8’其意义为：将10进制数48，转换成8进制数输出。

输出结果为：48<10>=60<8>4．挖地雷（30分）在一个地图上有N 个地窖（N<=20），每个地窖中埋有一定数量的地雷。

同时，给出地窖之间的连接路径。

[题目要求] 当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接，当设计一（表示1g 砝码有a1个，2g 砝码有a2个，…，20g 砝码有a6个）输出方式：Total=N（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）如输入：1_1_0_0_0_0 （注：下划线表示空格）输出：TOTAL=3 表示可以称出1g ，2g ，3g 三种不同的重量。

NOIP2006初赛试题(提高组Pascal语言)[日期：2006-10-25] 来源：作者：[字体：大中小]第十二届全国青少年信息学奥林匹克联赛初赛试题（提高组Pascal 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10 题，每题1.5 分，共计15 分。

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

1. 在以下各项中。

（）不是CPU 的组成部分。

A. 控制器B. 运算器C. 寄存器D. ALUE. RAM2. BIOS（基本输入输出系统）是一组固化在计算机内（）上一个ROM 芯片上的程序。

A. 控制器B. CPUC. 主板D. 内存条E. 硬盘3.在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（）。

A. 沃尔夫奖B. 诺贝尔奖C. 菲尔兹奖D. 图灵奖E. 南丁格尔奖4．在编程时（使用任一种高级语言，不一定是Pascal）,如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000 的double 型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。

A. 没有区别B. 有一些区别，但机器处理速度很快，可忽略不计C. 按行读的方式要高一些D. 按列读的方式要高一些E.取决于数组的存储方式。

5．在Pascal 语言中，表达式(21 xor 2)的值是（）A. 441B. 42C.23D.24E.256．在Pascal 语言中，判断a不等于0且b不等于0的正确的条件表达式是（）A. not a=0 or not b=0B. not((a=0)and(b=0))C. not(a=0 and b=0)D. (a<>0)or(b<>0)E. (a<>0)and (b<>0)7．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。

已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。

第十届全国信息学奥林匹克分区联赛（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【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

第十二届全国青少年信息学奥林匹克联赛复赛试题（NOIP2006普及组）竞赛时间：2006年11月18日下午1:30-4:30关于竞赛中不同语言使用限制的说明一．关于使用Pascal语言与编译结果的说明1．对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。

2．允许使用数学库(uses math子句)，以及ansistring。

但不允许使用编译开关（最后测试时pascal 的范围检查开关默认关闭：{$R-,Q-,S-}），也不支持与优化相关的选项。

二．关于C++语言中模板使用的限制说明1．允许使用的部分：标准容器中的布尔集合，迭代器，串，流。

相关的头文件：<bitset > <iterator > <string > <iostream >2．禁止使用的部分：序列：vector，list，deque序列适配器：stack, queue, priority_queue关联容器：map, multimap, set, multiset拟容器：valarray散列容器：hash_map, hash_set, hash_multimap, hash_multiset所有的标准库算法相关头文件：<vector > <list > <deque > <stack > <map > <set > <algorithm >1.明明的随机数（random.pas/c/cpp）【问题描述】明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N 个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。

然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。

2000年全国青少年信息学（计算机）奥林匹克分区联赛复赛试题（高中组竞赛用时：3小时）题一进制转换问题描述我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置的（值减１）为指数，以１０为底数的幂之和的形式。

例如：１２３可表示为１＊１０２＋２＊１０１＋３＊１００这样的形式。

与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的（值－１）为指数，以２为底数的幂之和的形式。

一般说来，任何一个正整数Ｒ或一个负整数－Ｒ都可以被选来作为一个数制系统的基数。

如果是以Ｒ或－Ｒ为基数，则需要用到的数码为０，１，．．．．Ｒ－１。

例如，当Ｒ＝７时，所需用到的数码是０，１，２，３，４，５和６，这与其是Ｒ或－Ｒ无关。

如果作为基数的数绝对值超过１０，则为了表示这些数码，通常使用英文字母来表示那些大于９的数码。

例如对１６进制数来说，用Ａ表示１０，用Ｂ表示１１，用Ｃ表示１２，用Ｄ表示１３，用Ｅ表示１４，用Ｆ表示１５。

在负进制数中是用－Ｒ作为基数，例如－１５（十进制）相当于１１０００１（－２进制），并且它可以被表示为２的幂级数的和数：１１０００１＝１＊（－２）５＋１＊（－２）４＋０＊（－２）３＋０＊（－２）２＋０＊（－２）１＋１＊（－２）０问题求解设计一个程序，读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数：－Ｒ∈｛－２，－３，－４，．．．，－２０｝输入输入的每行有两个输入数据。

第一个是十进制数Ｎ（－32768＜＝Ｎ＜＝32767）；第二个是负进制数的基数－Ｒ。

输出结果显示在屏幕上，相对于输入，应输出此负进制数及其基数，若此基数超过１０，则参照１６进制的方式处理。

样例输入３００００－２－２００００－２２８８００－１６－２５０００－１６输出３００００＝１１０１１０１０１０１１１００００（ｂａｓｅ－２）－２００００＝１１１１０１１０００１０００００（ｂａｓｅ－２）２８０００＝１９１８０（ｂａｓｅ－１６）－２５０００＝７ＦＢ８（ｂａｓｅ－１６）题二乘积最大问题描述今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。

NOIP2006普及组解题报告Kyd Dong 1.明明的随机数（random.pas/c/cpp）【问题描述】明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。

然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。

请你协助明明完成“去重”与“排序”的工作。

【输入文件】输入文件random.in 有2行，第1行为1个正整数，表示所生成的随机数的个数：N第2行有N个用空格隔开的正整数，为所产生的随机数。

【输出文件】输出文件random.out 也是2行，第1行为1个正整数M，表示不相同的随机数的个数。

第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

【输入样例】1020 40 32 67 40 20 89 300 400 15【输出样例】815 20 32 40 67 89 300 400【试题分析】简单的映射排序，用一个数组s[1..n]用一个数组a[1..1000]来储存状况，先清空数组为0，在读入s[i]之后，先判断a[s[i]]是否为1，是则再读下一个数据，不是则把a[s[i]]赋值为1，m←m+1。

在输出时，则先输出m,再用一个循环输出各个值，即用如下伪代码：For i←1 to 1000 do{If a[i]=1Then 打印i；}当然还有许多不同的方法，这里只给出代码，供读者自己研究。

【程序代码】1.program random; {映射排序}varp:array [1..1000] of shortint; {当前数已有标记1} n,l:shortint;a,max,i:integer;input,output:text;beginassign(input,'random.in');assign(output,'random.out');reset(input);readln(input,n);fillchar(p,sizeof(p),0);max:=-1;l:=0; {max:存最大数， l:不同数字的个数}for i:=1 to n dobeginread(input,a);if p[a]=0 then begin p[a]:=1;l:=l+1 end; {当前数未重复，则标记并记数}if a>max then max:=a;end;rewrite(output);writeln(output,l);for i:=1 to max doif p[i]=1 then write(output,i,' ');close(input);close(output);end2.program random; { 插入排序}var p:array [1..1000] of boolean;a:array [1..100] of integer;i,n,j,g:integer;input,output:text;procedure swap(var a,b:integer);var c:integer;beginc:=a;a:=b;b:=c;end;beginassign(input,'random.in');assign(output,'random.out');reset(input);readln(input,n);fillchar(p,sizeof(p),false);g:=2;read(input,a[1]);p[a[1]]:=true;for i:=2 to n dobeginread(input,a[g]);if p[a[g]]=falsethenbeginp[a[g]]:=true; {当前数已有标记}j:=g; {插入排序}while j>1 dobeginif a[j]<a[j-1] then swap(a[j-1],a[j]); j:=j-1;end;g:=g+1;end;end;rewrite(output);writeln(output,g-1);for i:=1 to g-1 do write(output,a[i],' ');close(output);close(input);end.3.program random; { 插入排序}var a:array [1..100] of integer;i,j,k,l,n,g:integer;input,output:text;beginassign(input,'random.in');assign(output,'random.out');reset(input);readln(input,n);g:=1;read(input,a[1]);for i:=2 to n dobeginread(input,k);j:=1;while (k>a[j]) and (j<=g) do j:=j+1; {找插入位置} if k<a[j] then {中间插入} beging:=g+1;for l:=g downto j+1 do a[l]:=a[l-1];a[j]:=k;end;if j>g then begin g:=g+1;a[g]:=k end; {最后插入} end;rewrite(output);writeln(output,g);for i:=1 to g-1 do write(output,a[i],' ');writeln(output,a[g]);close(output);close(input);end.4.program random; { 链表插入排序}typelink=^node;node=recorddata:integer;next:link;end;var h,t,r,s:link;i,g,n,k:integer;input,output:text;beginassign(input,'random.in');assign(output,'random.out');reset(input);readln(input,n);g:=1;new(t);read(input,t^.data);t^.next:=nil;h:=t; {用第一个数建立链首指针}for i:=2 to n do {插入其余的数}beginread(input,k);if k<h^.data thenbegin new(t);t^.data:=k;t^.next:=h;h:=t;g:=g+1 end{链首插入}elsebeginr:=h;while (k>r^.data) and (r^.next<>nil) do begins:=r;r:=r^.next end; {在链中查找插入位置}if k<r^.data thenbeginnew(t);t^.data:=k;s^.next:=t;t^.next:=r;g:=g+1 end {处理在链中插入}else if (k<>r^.data) and (r^.next=nil) thenbeginnew(t);t^.data:=k;r^.next:=t;t^.next:=nil;g:=g+1 end {处理在链尾插入}end;end;rewrite(output);writeln(output,g);repeatwrite(output,r^.data,' ');r:=r^.next;until r=nil;close(output);close(input);end.5.program random; { 树排序}var a:array [1..100,1..3] of integer;i,n,g:integer;input,output:text;procedure px(s:integer); {建树,s:树中当前结点，i：待插入点}beginif a[i,2]<a[s,2] then if a[s,1]=0 then begin a[s,1]:=i;g:=g+1 end {插入左子树}else begin s:=a[s,1];px(s) end;if a[i,2]>a[s,2] then if a[s,3]=0 then begin a[s,3]:=i;g:=g+1 end {插入右子树}else begin s:=a[s,3];px(s) end;end;procedure print(s:integer); {中序遍历}beginif a[s,1]<>0 then print(a[s,1]); {左子树不空，则递归} write(output,a[s,2],' '); {输出当前父结点}if a[s,3]<>0 then print(a[s,3]); {右子树不空，则递归} end;beginassign(input,'random.in');assign(output,'random.out');reset(input);readln(input,n);fillchar(a,sizeof(a),0);read(input,a[g,2]);for i:=2 to n do begin read(input,a[i,2]);px(1) end; {建排序二叉树}rewrite(output);writeln(output,g);print(1);close(output);close(input);end.2.开心的金明(happy.pas/c/cpp)【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。

NOIP2006 Solutions2006届中国信息学奥林匹克联赛提高组解题报告by FaLLeNs问题一能量项链/Energy核心算法动态规划(原型石子合并问题)时间复杂度O(n3)空间复杂度O(n2)编码复杂度<50行实测时间<0.1s分析记head[i]为第i颗能量珠的首标记，也同时是它前面那颗能量珠的尾标记。

记录Energy[i,j]为从以Head[i]为首标记的能量珠开始顺时针数到以Head[j]为尾标记的能量珠为止所有能量珠组成的串合并后放出的最大能量。

那么对于Energy[i,j]，若先合并从以Head[i]为首标记的能量珠开始顺时针数到以Head[k]为尾标记的能量珠为止的串，在合并以Head[k]为首标记的能量珠开始顺时针数到以Head[j]为尾标记的能量珠为止的串，然后将这两颗合并后的能量珠合并，放出的能量为Energy[i,k]+Energy[k,j]+Head[i]*Head[k]*Head[j]。

也就是说，状态转移方程为Energy[i,j]=Max{Energy[i,k]+Energy[k,j]+Head[i]*Head[k]*Head[j]} (i<=k<=j (i<j), k<i or k>j (i>=j))。

计算Energy[i,j]时，只会用到含有能量珠数目比它少的串在数组中的值，所以可以以串的能量珠数目为顺序规划，即按照k|(k+i) mod n=j的顺序进行规划。

评论如果枚举将能量项链变为串的开链位置，需要约n/2倍计算量，得到一个O(n4)的时间复杂度。

这是不需要的。

一个较优的贪心近似算法是每次找首标记最小的能量珠与它前面的能量珠合并。

对于NOIP中30%数据是正确的。

一个典型的反例是n=4,Head={10,3,2,3}，贪心算法得到3*2*3+10*3*3+10*10*3=408，而最优解为10*3*2+10*2*3+10*10*3=420。