NOIP2001-2011提高组复赛试题合集

第一题题库NOIP20071．统计数字(count.pas/c/cpp)【问题描述】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。

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

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

第2~n+1行每行一个自然数。

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

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

【输入输出样例】【限制】40%的数据满足：1<=n <=100080%的数据满足：1<=n <=50000100%的数据满足：1<=n <=200000，每个数均不超过1 500 000 000（1.5*109）NOIP20081. 笨小猴(wird.pas/c/cpp)【问题描述】笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。

但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！这种方法的具体描述如下：假设maxn 是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数，如果maxn-minn 是一个质数，那么笨小猴就认为这是个Lucky Word ，这样的单词很可能就是正确的答案。

【输入】输入文件word.in 只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。

【输出】输出文件word.out 共两行，第一行是一个字符串，假设输入的的单词是Lucky Word ，那么输出“Lucky Word ”，否则输出“No Answer ”；第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn 的值，否则输出0。

第十二届全国信息学奥林匹克分区联赛（NOIP2006）复赛试题（提高组竞赛用时：3小时）关于竞赛中不同语言使用限制的说明一．关于使用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．能量项链(energy.pas/c/cpp)【问题描述】在Mars星球上，每个Mars人都随身佩带着一串能量项链。

在项链上有N颗能量珠。

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

并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。

因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。

1．数字反转(reverse.cpp/c/pas)【问题描述】给定一个整数，请将该数各个位上数字反转得到一个新数。

新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。

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

输入共1行，一个整数N。

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

输出共1行，一个整数，表示反转后的新数。

【输入输出样例1】reverse.in reverse.out 123 321【输入输出样例2】Reverse.in reverse.out -380 -83【数据范围】-1,000,000,000≤N≤1,000,000,000。

2．统计单词数(stat.cpp/c/pas)【问题描述】一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。

现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。

注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。

【输入】输入文件名为stat.in，2行。

第1行为一个字符串，其中只含字母，表示给定单词；第2行为一个字符串，其中只可能包含字母和空格，表示给定的文章。

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

只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从0开始）；如果单词在文章中没有出现，则直接输出一个整数-1。

【输入输出样例1】stat.in stat.out2 0Toto be or not to be is a question【输入输出样例1说明】输出结果表示给定的单词To在文章中出现两次，第一次出现的位置为0。

第十七届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal语言两小时完成）一、单项选择题（共20题，每题1.5分。

共计30分。

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

）1．在二进制下， +（）= 。

A．1011 B．1101 C．1010 D．11112．字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。

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

A．ABDEFC B．DBEFAC C．DFEBCA D．ABCDEF4．寄存器是（）的重要组成部分。

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

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

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

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

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

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

每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。

这种站队的方法类似于（）算法。

A．快速排序B．插入排序C．冒泡排序D．归并排序10．1956年（）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain)，以表彰他们对半导体的研究和晶体管效应的发现。

第七届（2001）分区联赛复赛解题报告（提高组）第一题：一元三次方程求解(p1.pas p1.in p1.out)问题描述有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。

给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。

要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。

提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)*f(x2)<0，则在(x1，x2)之间一定有一个根。

样例输入：1 -5 -4 20输出：-2.00 2.00 5.00第二题：数的划分(p2.pas/c/cpp p2.in p2.out)问题描述将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5; 1，5，1; 5，1，1;问有多少种不同的分法。

输入：n，k (6<n<=200，2<=k<=6)输出：一个整数，即不同的分法。

样例输入： 7 3输出：4 {四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}第三题：统计单词个数(p3.pas/c/cpp p3.in p3.out)问题描述给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。

要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。

当选用一个单词之后，其第一个字母不能再用。

例如字符串this中可包含this和is，选用this之后就不能包含th)。

单词在给出的一个不超过6个单词的字典中。

要求输出最大的个数。

输入格式:输入数据放在文本文件p3.in中，其格式如下：第一行为一个正整数(0<n<=5)表示有n组测试数据每组的第一行有二个正整数(p，k),p表示字串的行数;k表示分为k个部分。

NOI’2001第七届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题普及组题一数的计算(20分)问题描述我们要求找出具有下列性质数的个数(包含输入的自然数n):先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:1.不作任何处理;2.在它的左边加上一个自然数,但该自然数不能超过原数的一半;3.加上数后,继续按此规则进行处理,直到不能再加自然数为止.样例: 输入: 6满足条件的数为 6 (此部分不必输出)162612636136输出: 6题二最大公约数和最小公倍数问题(20分)问题描述输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数条件: 1.P,A是正整数2.要求P,Q以x0为最大公约数,以y0为最小公倍数.试求:满足条件的所有可能的两个正整数的个数.样例输入:x0=3 yo=60输出:4说明(不用输出)此时的P Q 分别为:3 6015 1212 1560 3所以:满足条件的所有可能的两个正整数的个数共4种.题三求先序排列（30分）问题描述给出一棵二叉树的中序与后序排列。

求出它的先序排列。

（约定树结点用不同的大写字母表示，长度<=8）。

样例输入：BADC BDCA输出：ABCD题四装箱问题（30分）问题描述有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n ＜＝30＝，每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

样例输入：24一个整数，表示箱子容量6一个整数，表示有n个物品8接下来n行，分别表示这n 个物品的各自体积312797输出：0一个整数，表示箱子剩余空间。

Noip 2011 提高组（Day 1）解题报告及程序一、铺地毯正着扫一遍判断每个矩形是否覆盖询问的点，覆盖则更新结果或者倒着扫一遍，找到第一个覆盖询问点的矩形，输出即可，时间复杂度O（n）Procedure:#include <cstdio>#define MaxLength 10000inline int Getint(){char c = getchar();while (c<'0' || c>'9') c = getchar();int ret = 0;while (c>='0' && c<='9'){ret = ret*10 + (c-'0');c = getchar();}return ret;}int sx[MaxLength+5], sy[MaxLength+5], ex[MaxLength+5], ey[MaxLength+5], n; void Init(){n = Getint();for (int i=1; i<=n; i++){sx[i] = Getint(), sy[i] = Getint(), ex[i] = Getint(), ey[i] = Getint();ex[i] += sx[i], ey[i] += sy[i];}return ;}int x0, y0, ans = -1;void Solve(){x0 = Getint(), y0 = Getint();for (int i=n; i;i--)if(x0>=sx[i] && x0<=ex[i] && y0>=sy[i] && y0<=ey[i]){ans = i;break;}printf("%d", ans);return ;}int main(){Init();Solve();getchar(); getchar();return 0;}二、选择客栈f [i][j]表示前i个客栈以第j种颜色的方案数，先以客栈划分第一阶段，以颜色划分第二阶段，如果颜色相同的客栈，则以前一客栈相同颜色的方案数+1，否则同其一样；计算答案时记一下前一个比最高消费限制低的客栈编号pos[i]，路径压缩，时间复杂度O（nm）Procedure:#include <cstdio>#define MaxNode 200000#define MaxType 50inline int Getint(){char c = getchar();while (c<'0' || c>'9') c = getchar();int ret = 0;while (c>='0' && c<='9'){ret = ret*10 + (c-'0');c = getchar();}return ret;}int color[MaxNode+5], price[MaxNode+5], n, m, low;void Init(){n = Getint(), m = Getint(), low = Getint();for (int i=1; i<=n; i++) color[i] = Getint(), price[i] = Getint();return ;}int f[MaxNode+5][MaxType+5], pos[MaxNode+5], ans = 0;void Dp(){for (int i=1; i<=n; i++)for (int j=0; j<m; j++)if (color[i]==j) f[i][j] = f[i-1][j]+1;else f[i][j] = f[i-1][j];for (int i=1; i<=n; i++)if (price[i]<=low){pos[i] = i;ans += f[i-1][color[i]];}else{pos[i] = pos[i-1];ans += f[pos[i]][color[i]];}printf("%d", ans);return ;}int main(){Init();Dp();getchar(); getchar();return 0;}三、Mayan纯暴力DFS，加可行性剪枝，如同一种颜色小于3块无法消除，同一颜色交换无意义，下落无法完成左右移动，再加模拟其过程时间复杂度O（ n^(?) ）Procedure：#include <cstdio>#include <memory>inline int Getint(){char c = getchar();while (c<'0' || c>'9') c = getchar();int ret = 0;while (c>='0' && c<='9'){ret = ret*10 + (c-'0');c = getchar();}return ret;}inline void Swap(int &a, int &b){int temp = a; a = b; b = temp;return ;}int map[10][10], point[10], color[15], n, type = 0;void Init(){n = Getint();for (int i=0; i<5; i++){map[i][0] = Getint();if (type<map[i][point[i]]) type = map[i][point[i]];color[ map[i][point[i]] ]++;while (map[i][point[i]]){map[i][++point[i]] = Getint();if (type<map[i][point[i]]) type = map[i][point[i]];color[ map[i][point[i]] ]++;}point[i]--;}return ;}bool Fall(int k){int top = -1;for (int i=0; i<=point[k]; i++)if (map[k][i]) map[k][++top] = map[k][i];if (top!=point[k]){for (int i=top+1; i<=point[k]; i++) map[k][i] = 0;point[k] = top;return true;}return false;}bool Check_Fall(){bool flag = false;for (int i=0; i<5; i++)if (Fall(i)) flag = true;return flag;}bool sign[10][10];void Clear(){int pmax = 0;for (int i=0; i<5; i++)if (point[i]>pmax) pmax = point[i];for (int i=0; i<5; i++)if (point[i]>=2){int k = point[i], j = k-1;for (; j>=0; j--)if (map[i][j]!=map[i][k]){if (k-j>=3)for (; k>j; k--) sign[i][k] = true;else k = j;}if (k-j>=3)for (; k>j; k--) sign[i][k] = true;}for (int i=0; i<=pmax; i++){int k = 0, j = 1;for (; j<5; j++)if (map[j][i]!=map[k][i]){if (j-k>=3)for (; k<j; k++) sign[k][i] = true;else k = j;}if (j-k>=3)for (; k<j; k++) sign[k][i] = true;}for (int i=0; i<5; i++)for (int j=pmax; j>=0; j--)if (sign[i][j]){sign[i][j] = false;color[map[i][j]]--;map[i][j] = 0;}return ;}void Solve(int x, int y){Fall(x), Fall(y);Clear();while (Check_Fall()) Clear();return ;}bool Check_Point(){for (int i=0; i<5; i++)if (point[i]>=0)return false;return true;}bool Check_Color(){for (int i=1; i<=type; i++)if (color[i]==1 || color[i]==2) return false;return true;}struct Ac{int m[10][10], p[10], c[15];}a[10];inline void Copy(int k){memcpy(a[k].m, map, sizeof(map));memcpy(a[k].p, point, sizeof(point));memcpy(a[k].c, color, sizeof(color));return ;}inline void Turn_Copy(int k){memcpy(map, a[k].m, sizeof(a[k].m));memcpy(point, a[k].p, sizeof(a[k].p));memcpy(color, a[k].c, sizeof(a[k].c));return ;}int ans[10][10];bool Dfs(int deep){if (!Check_Color()) return false;Copy(deep);for (int i=0; i<5; i++)for (int j=0; j<=point[i]; j++){ans[deep][0] = i, ans[deep][1] = j;if (i<4){ans[deep][2] = 1;Swap(map[i][j], map[i+1][j]);if (point[i+1]<j) point[i+1] = j;Solve(i, i+1);if (deep==n && Check_Point()) return true;if (deep<n && Dfs(deep+1)) return true;Turn_Copy(deep);}if (i && point[i-1]<j){ans[deep][2] = -1;Swap(map[i][j], map[i-1][j]);point[i-1] = j;Solve(i, i-1);if (deep==n && Check_Point()) return true;if (deep<n && Dfs(deep+1)) return true;Turn_Copy(deep);}}return false;}int main(){Init();if (!Dfs(1)) printf("-1");elsefor (int i=1; i<=n; i++)printf("%d %d %d\n", ans[i][0], ans[i][1], ans[i][2]);getchar(); getchar();return 0;}Noip 2011 提高组（Day 2）解题报告及程序一、计算系数二项式定理，杨辉三角，注意Mod就可以了，时间复杂度O(k^2)Procedure：#include <cstdio>#define MaxNode 1000#define Mod 10007int f[MaxNode+5][MaxNode+5], a, b, k, n, m;void Init(){scanf("%d %d %d %d %d", &a, &b, &k, &n, &m);a %= Mod,b %= Mod, k++;for (int i=1; i<=k; i++) f[i][1] = f[i][i] = 1;for (int i=2; i<=k; i++)for (int j=2; j<i; j++)f[i][j] = (f[i-1][j-1] + f[i-1][j])%Mod;return ;}void Solve(){int x = k, y = k-n;for (int i=1; i<=n; i++) f[x][y] = (f[x][y] * a)%Mod;for (int j=1; j<=m; j++) f[x][y] = (f[x][y] * b)%Mod;printf("%d", f[x][y]%Mod);return ;}int main(){Init();Solve();getchar(); getchar();return 0;}二、聪明的质检员由观察得随着参数W的上升检验值temp会减小，据函数Abs（标准值-temp）有最小值，故可二分查找得出答案其中每次调整参数W时扫描一次矿石中大于W的，num[]表示其数量前缀和，val[]表示其价值前缀和，故可在一个区间的检验值计算中以O（1）的时间得出答案时间复杂度O（log（w）*（n+m））Procedure：#include <cstdio>#define MaxNode 200000#define INF ((0x7fffffffffffffffll)>>1)inline int Getint(){char c = getchar();while (c<'0' || c>'9') c = getchar();int ret = 0;while (c>='0' && c<='9'){ret = ret*10 + (c-'0');c = getchar();}return ret;}long long Abs(long long a){if (a>0) return a;return -a;}int w[MaxNode+5], val[MaxNode+5], l[MaxNode+5], r[MaxNode+5], n, m, lw, rw; long long standard;void Init(){n = Getint(), m = Getint(), scanf("%I64d", &standard);for (int i=1; i<=n; i++){w[i] = Getint(), val[i] = Getint();if (rw<w[i]) rw = w[i]+1;}for (int i=1; i<=m; i++) l[i] = Getint(), r[i] = Getint();return ;}int num[MaxNode+5];long long sum[MaxNode+5];long long Calc(int left, int right){return (sum[right]-sum[left]) * (num[right]-num[left]);}long long Sieve(int Limit){long long ret = 0;sum[0] = num[0] = 0;for (int i=1; i<=n; i++){num[i] = num[i-1];sum[i] = sum[i-1];if (w[i]>=Limit){num[i]++;sum[i] += val[i];}}for (int i=1; i<=m; i++) ret += Calc(l[i]-1, r[i]);return ret;}long long ans = INF;void Binary_Search()while (lw<rw){int mid = (lw+rw)>>1;long long temp = Sieve(mid);long long value = Abs(standard - temp);if (temp<standard) rw = mid;else lw = mid+1;if (ans>value) ans = value;}printf("%I64d", ans);return ;}int main(){Init();Binary_Search();getchar(); getchar();return 0;}三、观光公交贪心令t[i]表示当前到达第i个站的时间，sumoff[i]表示目的地为i的乘客数，arrtime[i]表示第i个乘客到站等车的时刻题目给定加速器的作用就是可以把某个t[i]减去1并把与其相关联的t[i]全部减小1。