NOIP2007提高组复赛试题

跪求2007年提高组复赛测试数据！万分感谢！~

시 실수하면 안 된다는 생각

NOIP问题求解经常考数学里的排列组合内容，建议可以专项复习下。 提供两种思路： 1、先往每个盒子里放一个球，有C(7,2)中情况，然后剩下三个自由组合。 2、用“插板方法”：七个人成为一个环，然后插入板子分割成四部分。 解法一：递推公式S(x,y)=S(x-1,y)*y+S(x-1,y-1)。因为把X个球放入Y个箱子，相当于先把X-1个球放好再放最后一个。最后一个有两种放法：放入前面已经有球的箱子或者独占一个箱子。前者对应S(x-1,y)*y (放入每一个不同的箱子都是一种不同的放法，因为箱子内原来的球不同)，后者对应S(x-1,y-1)。 解法二：7个球放入4个箱子无非是2+2+2+1或者3+2+1+1或者4+1+1+1三种情况。所以分别求解再加起来：C(7,1)*C(6,2)*C(4,2)*C(2,2)/P(3,3)+C(7*3)*C(4,2)+C(7,4)。 答案是350。

第一题：count 统计数字
输入一个数n(n<=200000)和n个自然数（每个数都不超过1.5*10^9），请统计出这些自然数各自出现的次数，按顺序从小到大输出。输入数据保证不相同的数不超过10000个。

样例输入：
8
2
4
2
4
5
100
2
100
样例输出：
2 3
4 2
5 1
100 2

第二题：expand 字符串的展开
我们可以用减号对连续字母或数字进行缩写，于是字符串a-dha3-68就可以展开为abcdha34568。
输入三个参数p1,p2,p3，再输入一个仅由数字、小写字母和减号组成的字符串（长度不超过100），请按参数展开此字符串
各个参数的意义如下：

参数p1=1 -> 所有填充的字母都写成小写；

参数p1=2 -> 所有填充的字母都写成大写；

参数p1=3 -> 所有填充的字母和数字都用星号代替；

参数p2=k -> 同一个填充字符连续写k遍；

参数p3=1 -> 顺序填充；

参数p3=2 -> 逆序填充。

另外，如果减号两边的字符一个是数字一个是字母，或者减号右边的ASCII码没左边的大，则该处不变

样例输入1：
1 2 1
abcs-w1234-9s-4zz
样例输出1：
abcsttuuvvw1234556677889s-4zz

样例输入2：
2 3 2
a-d-d
样例输出2：
aCCCBBBd-d

样例输入3：
3 4 2
di-jkstra2-6
样例输出3：
dijkstra2************6

第三题：game 矩阵取数游戏
一个n行m列的矩阵，每次你需要按要求取出n个数，m次正好将所有数取完。每取出一个数你都会有一个得分，请求出最终的得分最大是多少。
每一次取数的要求：每一行中恰好取一个数，且只能取剩下的数中最左边或最右边位置上的数
每取一个数的得分：所取数的数值乘以2^i，i表示这是第i轮取数。
矩阵中的数为不超过100的自然数，1<=n,m<=80

样例输入：
2 3
1 2 3
3 4 2
样例输出：
82
样例说明：
1*2+2*2 + 2*4+3*4 + 3*8+4*8 = 82

第四题：core 树网的核
树上的任两点间都有唯一路径。定义某一点到树上某一路径的距离为该点到路径上所有点的路径长度中的最小值。定义树中某条路径的“偏心距”为所有其它点到此路径的距离的最大值。定义树的直径为树的最长路径（可能不唯一）。给出一个有n个节点的无根树，请找出某个直径上的一段长度不超过s的路径（可能退化为一个点），使它的偏心距最小。请输出这个最小偏心距的值。
题目已经告诉你如下定理：树的所有直径的中点必然重合（这个中点可能在某条边上）。其实这个结论很显然嘛，因为如果中点不重合的话必然可以找到一条更长的路。
5<=n<=300，0<=s<=1000，边权是不超过1000的正整数

---

桃江县15152383367： noip2007复赛提高组第一题答案 - ？
端房谷氨： #include<stdio.h>#include<string.h>#define LEN 200000 int a[LEN],temp,mid; int sort(int *a,int low,int high) //一趟快排 { mid=a[low]; while (low<high) { while (low<high && a[high]>=mid) high--; temp=a[low];a[low]=a[high];a[high]=temp; while (low<high ...

桃江县15152383367： NOIP2007提高组复赛试题 - ？
端房谷氨： 第一题:count 统计数字 输入一个数n(n<=200000)和n个自然数(每个数都不超过1.5*10^9),请统计出这些自然数各自出现的次数,按顺序从小到大输出.输入数据保证不相同的数不超过10000个.样例输入:8242451002100 样例输出:2 34 ...

桃江县15152383367： NOIP2007提高组复赛试题？
端房谷氨： 第一题:count 统计数字 输入一个数n(n&lt;=200000)和n个自然数(每个数都不超过1.5*10^9),请统计出这些自然数各自出现的次数,按顺序从小到大输出.输入数据保证不相同的数不超过10000个. 样例输入: 8 2 4 2 4 5 100 2 100 样例输...

桃江县15152383367： 谁能告诉我noip提高组复赛技巧 - ？
端房谷氨： NOIP赛场经验(根据往年原题): (1)最水的不一定是第1题; (2)4道题全看完,然后先想自己会的(什么,你说一道也不会……那就滚蛋吧,这些经验不适用于超级菜鸟); (3)有可能一道看起来很水的题很难; (4)尽量相信自己的...

桃江县15152383367： 求noip提高组近五年的复赛试题 - ？
端房谷氨： http://ishare.iask.sina.com.cn/search.php?key=NOIP%CA%D4%CC%E2&format= 复赛的题都是一样的.这里只有测试数据,源代码没有.vijos这个网站里有历届的复赛题,里面有题解.可以参考一下.

桃江县15152383367： 要想在NOIP复赛中获得200左右的分 - ？
端房谷氨： 先谈谈基本算法吧.下面是从OIBH上摘来的,我加了点注释.一、 排序 //这个不用说了,必须十分熟练的过关,特别是快速排序.要能够达到立刻默出来的效果,并要适当学会灵活应用.堆排序也稍微注意一下,毕竟速度比较稳定.1. 快速排...

桃江县15152383367： noip提高组的C语言历届复赛试题？
端房谷氨： 第十三届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组C 语言二小时完成) ● ● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效●● 一、单项选择题(共10 题,每题1.5 分,共计15 分.每题有且仅有一个正确答案). 1. 在以下各...

桃江县15152383367： noip的题初赛和复赛的基本题型.？
端房谷氨： 初赛的笔试题有四部分:选择题、问题求解、程序阅读理解、完善程序. 1、选择题:共20题,每题1.5分,共30分.每题有4个备选方案. 2、问题求解:共2题,每题5分,共10分. 3、程序阅读理解题:共4题,每题8分,共32分. 4、完善程序:共 2题,第一题10分,第二题18分,两题共28分. 复赛为上机编程题,题目包括4道题,每题100分,共计400分.测试时,测试程序为每道题提供了5~10组测试数据,考生程序每答对一组得10~20 分;累计分即为该道题的得分.

桃江县15152383367： 2007 矩阵取数 - ？
端房谷氨： 不用高精度是不行的,不能够AC,因为就算QWORD也装不下. 【pascal程序给你了.带题解】 【题解】 显然取数的规则决定了他有最优子结构,即取了一个数后,剩下的又可以看成是规模更小的子问题 而且每一排的问题性质是一样的,我就...

桃江县15152383367： noip需要准备哪些方面的基础知识.复赛需要做哪些类型的题目(提高组)? - ？
端房谷氨：[答案] Noip算法(小超) 以下用n表示图的点数,m表示边数,k表示一个常数,log均以2为底数,存储边都采用边表. 【模拟】 高精度加、减、乘,除应该不需要 表达式求值(中缀转后缀,栈的操作) 【图论】 图的表示:邻接矩阵,邻接表,边表 单源最...