noip1999-2008试题大全4

第一篇：noip1999-2008试题大全4

2005

陶陶摘苹果

Time Limit: 1000MS Memory Limit: 65536K 题目描述

陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。

现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。

输入描述

包括两行数据。第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。

输出描述

包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。

样例输入

200 150 140 129 134 167 198 200 111 110 样例输出

校门外的树

Time Limit: 1000MS Memory Limit: 65536K 题目描述

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入描述

第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出描述

包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

样例输入

500 3 150 300 100 200 470 471 样例输出

298

采药

Time Limit: 1000MS Memory Limit: 65536K 题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入描述 第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出描述

包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例输入

3 71 100 69 1 1 2 样例输出

循环

Time Limit: 1000MS Memory Limit: 65536K 题目描述

乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。

众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6……我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象： 循环 循环长度 2(2、4、8、6)4 3(3、9、7、1)4 4（4、6)2 5(5)1 6(6)1 7(7、9、3、1)4 8(8、4、2、6)4 9（9、1)2 这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？ 注意： 注意：

1.如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。2.如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a + L次幂的最后k位都相同。

输入描述

只有一行，包含两个整数n（1 <= n < 10100）和k（1 <= k <= 100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。

输出描述

包括一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。

样例输入

2 样例输出

谁拿了最多奖学金

Time Limit: 1000MS Memory Limit: 65536K 题目描述

某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：

1)院士奖学金，每人8000元，期末平均成绩高于80分（>80），并且在本学期内发表1篇或1篇以上论文的学生均可获得； 2)五四奖学金，每人4000元，期末平均成绩高于85分（>85），并且班级评议成绩高于80分（>80）的学生均可获得；

3)成绩优秀奖，每人2000元，期末平均成绩高于90分（>90）的学生均可获得； 4)西部奖学金，每人1000元，期末平均成绩高于85分（>85）的西部省份学生均可获得；

5)班级贡献奖，每人850元，班级评议成绩高于80分（>80）的学生干部均可获得；

只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。

现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。

输入描述

第一行是一个整数N（1 <= N <= 100），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。

输出描述

第一行是一个整数N（1 <= N <= 100），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。

样例输入 YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1 样例输出

ChenRuiyi 9000 28700

过河

Time Limit: 1000MS Memory Limit: 65536K 题目描述

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

输入描述

第一行有一个正整数L（1<=L<=109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1<=S<=T<=10，1<=M<=100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

输出描述

包括一个整数，表示青蛙过河最少需要踩到的石子数。

样例输入 2 3 5 2 3 5 6 7 样例输出

篝火晚会

Time Limit: 1000MS Memory Limit: 65536K 题目描述

佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。佳佳可向同学们下达命令，每一个命令的形式如下：

(b1,b2,...bm-1,bm)这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，…… bm–1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。

执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？

输入描述

第一行是一个整数n（3 <= n <= 50000），表示一共有n个同学。其后n行每行包括两个不同的正整数，以一个空格隔开，分别表示编号是1的同学最希望相邻的两个同学的编号，编号是2的同学最希望相邻的两个同学的编号，……，编号是n的同学最希望相邻的两个同学的编号。

输出描述

包括一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出-1。

样例输入 3 4 4 3 1 2 1 2 样例输出

等价表达式

Time Limit: 1000MS Memory Limit: 65536K 题目描述

明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。

这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？ 这个选择题中的每个表达式都满足下面的性质： 1．表达式只可能包含一个变量„a‟。

2．表达式中出现的数都是正整数，而且都小于10000。

3． 表达式中可以包括四种运算„+‟（加），„-‟（减），„*‟（乘），„^‟（乘幂），以及小括号„(‟，„)‟。小括号的优先级最高，其次是„^‟，然后是„*‟，最后是„+‟和„-‟。„+‟和„-‟的优先级是相同的。相 同优先级的运算从左到右进行。（注意：运算符„+‟，„-‟，„*‟，„^‟以及小括号„(‟，„)‟都是英文字符）4．幂指数只可能是1到10之间的正整数（包括1和10）。5．表达式内部，头部或者尾部都可能有一些多余的空格。

下面是一些合理的表达式的例子：((a^1)^2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1+(a-1)^3，1^10^9……

输入描述

第一行给出的是题干中的表达式。第二行是一个整数n（2<=n<=26），表示选项的个数。后面n行，每行包括一个选项中的表达式。这n个选项的标号分别是A，B，C，D……输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。

输出描述 包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。

样例输入

(a + 1)^2 3(a-1)^2+4*a a + 1+ a a^2 + 2 * a * 1 + 1^2 + 10-10 +a-a 样例输出

AC 2006

明明的随机数

Time Limit: 1000MS Memory Limit: 65536K 题目描述

明明想在学校中请一些同学一起做问卷调查，为了实验的客观性，他先用计算机生成了N 个1 到1000 之间的随机整数，（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入描述

有2 行，第1 行为1 个正整数，表示所生成的随机数的个数：N 第二行有N 个用空格隔开的正整数，为所产生的随机数。

输出描述

也是2 行，第1 行为1 个正整数M，表示不相同的随机数的个数。

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

样例输入 10 20 40 32 67 40 20 89 300 400 15 样例输出 15 20 32 40 67 89 300 400

开心的金明

Time Limit: 1000MS Memory Limit: 65536K 题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数1~5 表示，第5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N 元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j 件物品的价格为v[j]，重要度为w[j]，共选中了k 件物品，编号依次为，则所求的总和为：k j j j , , , 2 1 ? ?（其中*为乘号）] [ * ] [...] [ * ] [ ] [ * ] [ 2 2 1 1 k k j w j v j w j v j w j v ? ?请你帮助金明设计一个满足要求的购物单。

输入描述

输入文件happy.in 的第1 行，为两个正整数，用一个空格隔开：

N m（其中N（<30000）表示总钱数，m(<25)为希望购买物品的个数。）从第2 行到第m+1 行，第j 行给出了编号为j1的物品的基本数据，每行有2 个非负整数

v p（其中v 表示该物品的价格（v≤10000），p 表示该物品的重要度（1~5））

输出描述

输出文件happy.out 只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）

样例输入 1000 5 800 2 400 5 300 5 400 3 200 2 样例输出

3900

Jam的计数法

Time Limit: 1000MS Memory Limit: 65536K 题目描述

Jam是个喜欢标新立异的科学怪人，他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”成为Jam数字。在Jam 数字中，每个字母互不相同，而且从左到右都是严格递增的。每次，Jam 还指定使用字母的范围，如从2 到10，表示只能使用{b,c,d,e,f,g,h,i,j}这些字母。如果再规定位数为5，那么，紧接在Jam 数字“bdfij”与“bdghi”，则U输入描述

有2 行，第1 行为3 个正整数，用一个空格隔开：

s t w（其中s 为所使用的最小字母的序号，t 为所使用的最大的字母序号。w 为数字的位数，这3个数满足：1≤s

第二行为具有w 个小写字母的字符串，为一个符合要求的Jam 数字。

输出描述

最多为5 行，为紧接在输入的Jam 数字后面的5 个Jam 数字，如果后面没有那么多Jam 数字，那么有几个就输出几个。每行只输出一个Jam 数字，是由w 个小写字母组成的字符串，不要有多余的空格。样例输入 10 5 bdfij 样例输出

bdghi bdghj bdgij bdhij befgh

数列

Time Limit: 1000MS Memory Limit: 65536K 题目描述

给定一个正整数k（3≤k≤15），把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列。例如，当k=3时，这个序列是：1，3，4，9，10，12，13，…

请你求出这个序列的第N项的值（用10进制数表示）。例如，对于k=3，N=100，正确答案应该是981。

输入描述

只有1行，为2个正整数，用一个空格隔开：kN（k、N的含义与上述问题的描述一致，且3≤k≤15，10≤N≤1000）。

输出描述

为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*10）。（整数前不要有空格和其它符号）

样例输入 100 样例输出

981

能量项链

Time Limit: 1000MS Memory Limit: 65536K 题目描述

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。

需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(4⊕1)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。

输入描述

第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i

输出描述

只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。

样例输入 2 3 5 10 样例输出

710

金明的预算方案

Time Limit: 1000MS Memory Limit: 65536K 题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子： 主件附件

电脑打印机，扫描仪 书柜图书 书桌台灯，文具 工作椅无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*为乘号）

请你帮助金明设计一个满足要求的购物单。

输入描述

第1行，为两个正整数，用一个空格隔开：Nm（其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数vpq（其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）输出描述

只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。

样例输入

1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 样例输出

2200

作业调度方案

Time Limit: 1000MS Memory Limit: 65536K 题目描述

我们现在要利用m台机器加工n个工件，每个工件都有m道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。每个工件的每个工序称为一个操作，我们用记号j-k表示一个操作，其中j为1到n中的某个数字，为工件号；k为1到m中的某个数字，为工序号，例如2-4表示第2个工件第4道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。

例如，当n=3，m=2时，“1-1，1-2，2-1，3-1，3-2，2-2”就是一个给定的安排顺序，即先安排第1个工件的第1个工序，再安排第1个工件的第2个工序，然后再安排第2个工件的第1个工序，等等。一方面，每个操作的安排都要满足以下的两个约束条件。

(1)对同一个工件，每道工序必须在它前面的工序完成后才能开始；(2)同一时刻每一台机器至多只能加工一个工件。

另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“11233 2”。还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。

例如，取n=3,m=2，已知数据如下： 工件号 机器号/加工时间

工序1 工序2 1 1/3 2/2 2 1/2 2/5 3 2/2 1/4 则对于安排顺序“112332”，下图中的两个实施方案都是正确的。但所需要的总时间分别是10与12。

一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件（1）（2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1）（2）的条件下，插入到最前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。

显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是唯一的，请你计算出该方案完成全部任务所需的总时间。

输入描述

第1行为两个正整数，用一个空格隔开：mn（其中m（<20）表示机器数，n（<20）表示工件数）

第2行：个用空格隔开的数，为给定的安排顺序。

接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。其中前n行依次表示每个工件的每个工序所使用的机器号，第1个数为第1个工序的机器号，第2个数为第2个工序机器号，等等。后n行依次表示每个工件的每个工序的加工时间。

输出描述

只有一个正整数，为最少的加工时间。

样例输入 3 1 1 2 3 3 2 1 2 1 2 2 1 3 2 2 5 2 4 样例输出

2k进制数

Time Limit: 1000MS Memory Limit: 65536K 题目描述

设r是个2k进制数，并满足以下条件：（1）r至少是个2位的2k进制数。

（2）作为2k进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。（3）将r转换为2进制数q后，则q的总位数不超过w。

在这里，正整数k（1≤k≤9）和w（k≤30000）是事先给定的。问：满足上述条件的不同的r共有多少个？

我们再从另一角度作些解释：设S是长度为w的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k的段，每段对应一位2k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2k进制数r。

例：设k=3，w=7。则r是个八进制数（23=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：

2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。

3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。所以，满足要求的r共有36个。

输入描述

只有1行，为两个正整数，用一个空格隔开：

输出描述

输出为1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。（提示：作为结果的正整数可能很大，但不会超过200位）

样例输入 7 样例输出

第二篇：NOIP考前知识大总结

数据类型

Type

Byte

Shortint

Smallint

Word

Integer

Cardinal

Longint

Longword

Int64

QWord

Real

Single

Double

Comp

Extended

算法思想:

1.搜索

2.归纳

3.分治

4.贪心

实现技巧: NOIP考前知识大总结 作者：于俊超 ID:MiniDragonXG2006年11月RangeSize in bytes0..2551-128..1271-32768..3276720..655352either smallint, longint or int64size 2,4 or 8either word, longword or qwordsize 2,4 or 8-2147483648..2***..42949672954-***5808..***580780..***70955161582.9E-39..1.7E3861.5E-45..3.4E3845.0E-324..1.7E3088-9.2E18..9.2E1883.4E-4932..1.1E493210(Search)枚举(穷举)/ 遍历 / 剪枝 / 产生式系统（估价函数）查找(字典)：折半查找(二分法)/ 树形查找(二叉排序树)/ Hash(To 数学方法)>递推式> DP(ex: 4 Hanoi Tower Problem)(Divided and Conquer)(Greedy)5.模拟循环

递推(顺推/倒推)> 博弈 / 动态规划 递归(栈/DFS)

滚动数组

幂：

x ^ y = exp(y*ln(x))

x ^(1/n)= exp(1/n*ln(x))

math单元里的Power

数学方法:

1.数论:质数 / 因数 / 约数个数（种数）/ 最大公约数 / 最小公倍数 / 回文数....2.进制转换注意负进制

3.高精度运算(int64...)

4.排列组合: 全排列

5.经典递推关系:

Fibonacci:fib(n)=fib(n-1)+fib(n-2)

fib(1)=1fib(2)=1

通项： 设g5=sqrt(5)则fib(n)=(1/g5)*(((1+g5)/2)^n-((1-g5)/2)^n)

f(n)=a1*f(n-1)+a2*f(n-2)+....+ak*f(n-k)(ai<>0 & n>k)叫

k阶常系数线性齐次递推关系

可以利用矩阵性质和快速幂在O(logn)内求解

错位排列:F(1)=0F(2)=1

Fn=(x-1)*(Fn-1 +Fn-2)

Catalan数:Catalan(n)=C(n,2*n)/(n+1)

第二类Stirling数 s(n,k)= { s(n-1,k-1)+k*s(n-1,k)}(n>k>=1)

6.高斯消元

数据结构(Data Structure):

1.物理结构:

I: 数组>二维平面/字符串(Ansistring)及其操作

II: 指针>链表（单链表 / 双向链表 / 环状链表）

抽象数据类型(Abstract Data Type)

2.初级ADT:

I: 集合II: 线性结构

A: 栈(stack)

(LIFO)operation: push/pop

a: 后缀表达式

b: 进出站序列问题(Catalan 枚举 > 归纳)

c: 栈优化最长不下降(上升)序列

B: 队列(queue)>循环队列

(FIFO)operation: push/pop

a: 广度优先搜索

b: 求和广义线性表

C: 字典 Dictionary

III: 非线性结构

A: 树Tree(二叉树Binary Tree)

树的遍历：前序/中序/后序(递归)

最优二叉树(哈夫曼树Huffman tree）（贪心）

树形DP

B: 图Grapha: 图的遍历:

Depth first Search(DFS / 回溯 / 递归)

Breadth first Search(BFS / 队列 / FloodFill 种子染色法)

b: 最小生成树：（贪心）

Prim: 边集密

Kruskal: 边集疏（排序 + 并查集）

c: 最短路径

Dijkstra（单源 O(n^2)BFS）

Floyed（所有点间 O(n^3)）

Bellman-Ford（负权环）

d: 拓扑序列

e: 关键路径（AOV网）

f: 无向图传递闭包

有向图强连通分量SCC

(Strong Connected Component)

g: 路与回路

欧拉路(Euler Route)所有边

哈密尔顿路(Hamilton Route)所有点

h: 割顶和桥

去除之后图变得不连通的顶点和边

3.高级ADT:

I: 集合型

A: 并查集(disjoint-set)

operation: Find/Union/Insert

II: 字典型

哈希表(Hash)哈希函数

opertaion: Find/Insert

III: 树型

A: 二叉堆(Heap)>Treap

operation: Insert/Delete(Pop)/GetMax/GetMinB: Binary Search Tree(BST)

C:平衡二叉树......排序算法:

复杂度 思路 InsertChooseExchange O(n^2)直接插入排序 直接选择排序 冒泡排序(Inserting Sort)(Choosing Sort)(Bubble Sort)O(nlogn)希尔排序堆排序快速排序(Shell Sort)(Heap Sort)(Quick Sort)O(n)计数排序桶排序基数排序(Counting Sort)(Bucket Sort)(Radix Sort)归并(Merge Sort)

Quick Sort: 分治

Merge Sort: 分治

Bucket Sort: 哈希表

Heap Sort: 堆

还有二叉排序树..........动态规划(Dynamic programming)

=记忆化搜索+用Table记录免去重复计算

（解决 满足具有最优子结构 且 无后效性）

1.状态转移方程+边界条件

2.合适的实现方法(To 实现技巧)

3.要掌握最经典的动规题目

a: 最长不下降(上升)序列

b: 最大子段和&最大M子段和

c: 最长公共子序列(LCS)

d: 石子合并（链，环）

e: 背包问题

01背包-可重复(DP)

01背包-不可重复(DP)

部分背包(贪心)

博弈问题：

1.关键字：必胜态 / 必败态

2.递推找规律

3.归纳

计算几何

三角形面积s=|x1y2+x2y3+x3y1-x3y2-x2y1-x1y3|二维仿射变换 反射 / 镜像 / 旋转

计算二维凸包……这东西我直接听不懂……

网络流 & 匹配（二分图）& 线段树 & 树状数组 & NP完全 ……

∵九成不考 ∴略……

Copyright ©2006 By MiniDragonXG.All rights reserved.

第三篇：NOIP竞赛语言和评测平台

NOIP竞赛语言和评测平台.txt22真诚是美酒，年份越久越醇香浓型；真诚是焰火，在高处绽放才愈是美丽；真诚是鲜花，送之于人手有余香。一颗孤独的心需要爱的滋润；一颗冰冷的心需要友谊的温暖；一颗绝望的心需要力量的托慰；一颗苍白的心需要真诚的帮助；一颗充满戒备关闭的门是多么需要真诚这一把钥匙打开呀！NOIP竞赛语言和评测平台

NOIP2007比赛环境规范依照兼顾Windows、Linux平台、统一编译器、提供多种集成开发环境（IDE）选择的原则制定。

NOIP2007的比赛环境中，操作系统平台选择Windows；在固定的操作系统平台下，对应同一种语言的不同的集成开发环境，使用统一的编译器，消除编译器不同给选手带来的不利影响；对应每种语言，提供了多种集成开发环境，选手可以根据自己的习惯选择集成开发环境。

在全国评测时，评测环境保持与比赛环境的操作系统及编译器一致。也就是说全国评测时，使用与选手比赛时一致的平台对选手的程序进行评测，以消除平台不一致带来的不利影响。以下是NOIP2007比赛环境要求的详细描述：

1.使用Windows操作系统平台：

（1）Windows操作系统使用Windows 98及更新的版本；

（2）Pascal语言，必须使用Free Pascal 1.0.10及以上版本作为编译器；

（3）C语言，必须使用gcc 3.4.2作为编译器；

（4）C++语言，必须使用g++ 3.4.2作为编译器；

（5）Pascal语言，可以使用Freepascal IDE Windows版、Lazarus Windows版、Dev-Pascal作为集成开发环境，推荐使用Lazarus Windows版；

（6）C和C++语言，可以使用Dev-Cpp、RHIDE Windows版DJGPP作为集成开发环境，推荐使用Dev-Cpp；

2.使用Linux操作系统平台：

（1）必须使用Red Hat Linux 9.0，安装时必须安装Red Hat 9.0自带的开发工具包；

（2）Pascal语言，必须使用Free Pascal 1.0.10及以上版本作为编译器；

（3）C语言，必须使用gcc 3.2.2作为编译器；

（4）C++语言，必须使用g++ 3.2.2作为编译器；

（5）Pascal语言，可以使用Lazarus Linux版、RHIDE Linux版作为集成开发环境，推荐使用Lazarus Linux版；

（6）C和C++语言，可以使用RHIDE Linux版、KDevelop、Anjuta作为集成开发环境，推荐使用Anjuta。

进场、试机

1.所有与会人员一律凭证件（胸卡）进入，非参赛选手和竞赛工作人员不得进入赛区。

2.选手在正式竞赛前30分钟进入竞赛准备室，正式竞赛开始30分钟后不得进入竞赛机房，未经允许不得提前退场。

3.选手一律凭参赛证（胸卡）进入竞赛机房，按指定机房和机位号入座，不准携带任何书籍、光盘、软盘、移动盘及通讯设备进入竞赛机房。

4.选手试机目的是熟悉竞赛环境及提供的编程语言环境，有问题应及时向监考老师提出。

5.试机时间为赛前10分钟，选手在试机过程中不能携带任何物品，只能在自己的目录下操作，严禁在其它目录下作任何操作。

竞

赛

1.用时3小时，由省奥赛委科学委员会测试和评分。

2.选手进入场地，应严格遵守考场纪律，对于违反考场纪律的选手，一经发现，当场取消竞赛资格。

3.选手拿到试题后应认真阅读，对试题有任何疑问应举手示意。选手可向监考老师咨询有关注意事项、试卷不清等方面问题，但不得询问试题解题思路、算法、上机调试等问题。

4.选手所编源程序的文件名应符合试卷的规定，对于文件名不符合要求的，科学委员会不给予测评，该题记零分。

5.选手应完全按照试题要求提交程序（包括输入、输出要求），对于不符合要求的程序，该题记零分。

6.为了减轻由于突发事件（如硬件故障、断电等）所带来的严重后果，要求选手每20分钟存盘一次。若发生突发事件，视情况延长时间，但最多延长20分钟。选手程序的错误和操作不当所造成的死机或文件丢失，不属于突发事件，不延长时间。

7.竞赛时，选手应合理分配时间，先易后难，并在时间允许的情况下尽量优化算法，并注意对边界情况的考虑。

8.竞赛结束5分钟前，选手应停止编程，逐一检查已完成的源程序并将其拷贝到指定的目录路径下。竞赛结束时间一到，应立即停止操作，不关机，有序退场。

测

评

1.参赛选手对于每个完成的试题都应提交严格按规定名字命名的文件——源程序文件，选手提交的文件应存放在大赛组委会规定的文件夹内，同时自建一个BAK文件夹保存一个备份。

2.科学委员会采用自动评测系统对选手所完成的源程序文件进行测试，测试使用的编译器为Windows操作系统平台下的32位编译器，具体来说为Pascal语言用Freepascal2.0.1中win32下的Fpc，C语言使用Dev-Cpp4.9.9.2的gcc作为编译器，C++语言使用Dev-Cpp4.9.9.2的g++作为编译器；任何人不能在测试时修改程序（包括编译开关）或进行编译。

3.竞赛评测采用黑盒测试，只看输出结果是否正确，不看程序。测试数据文件上标明了每个测试点的得分和时限。

4.选手对测试有任何疑问，应在得知成绩后半小时内向科学委员会提出申诉，填写“复测申请表”，科学委员会受理后方可复测。

5.复测申请书应给出复测原因，经审核后，剔除不必要的复测申请，再经竞赛科学委员会负责人同意后，方可再次用该选手的源程序以自动测试的方式进行复测，没有特殊原因(比赛用机编译不正常等)不能对源程序作重新编译后自动测试，对获准重新编译的源程序不能作任何修改，编译时不允许加任何编译开关。每张复测申请只允许申请复测一道题。如果通过复测发现原测试结果有误，则以复测评分为准。如果复测结果与原测试结果相同，则从总分中扣除该题实际得分的10%。当领队或参赛选手对复议或复评结果仍有异议时，应提交JSOI科学委员会仲裁，并以JSOI科学委员会的仲裁结果为该项评测的最终结果。

其 他

1.对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。

2.允许使用数学库(uses math子句)，以及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

所有的标准库算法

相关头文件：

第四篇：NOIP竞赛语言和评测平台介绍

NOIP竞赛语言和评测平台

更新时间：2005-7-27

NOIP2005比赛环境规范依照兼顾Windows、Linux平台、统一编译器、提供多种集成开发环境选择的原则制定。

NOIP2005的比赛环境中，操作系统平台可依各地的实际情况选择Windows或者Linux；在固定的操作系统平台下，对应不同的语言，使用统一的编译器，消除编译器不同给选手带来的不利影响；对应每种语言，提供了多种集成开发环境，选手可以根据自己的习惯选择集成开发环境。

在全国评测时，评测环境保持与比赛环境的操作系统及编译器一致。也就是说全国评测时，使用与选手比赛时一致的平台对选手的程序进行评测，以消除平台不一致带来的不利影响。以下是NOIP2005比赛环境要求的详细描述： 1．使用Windows操作系统平台：

（1）.Windows操作系统必须使用Windows 2000、Windows XP及更新的Windows版本；（2）.Pascal语言，必须使用Free Pascal 1.0.10及以上版本作为编译器；（3）.C语言，必须使用gcc 3.4.2作为编译器；（4）.C++语言，必须使用g++ 3.4.2作为编译器；

（5）.Pascal语言，可以使用Freepascal IDE Windows版、Lazarus Windows版、Dev-Pascal作为集成开发环境，推荐使用Lazarus Windows版；

（6）.C和C++语言，可以使用Dev-C++、RHIDE Windows版作为集成开发环境，推荐使用Dev-C++；

2．使用Linux操作系统平台：

（1）.Linux操作系统必须使用Red Hat Linux 9.0，安装时必须安装Red Hat 9.0自带的开发工具包；

（2）.Pascal语言，必须使用Free Pascal 1.0.10及以上版本作为编译器；（3）.C语言，必须使用gcc 3.2.2作为编译器；（4）.C++语言，必须使用g++ 3.2.2作为编译器；

（5）.Pascal语言，可以使用Lazarus Linux版、RHIDE Linux版作为集成开发环境，推荐使用Lazarus Linux版；

（6）.C和C++语言，可以使用RHIDE Linux版、KDevelop、Anjuta作为集成开发环境，推荐使用Anjuta。

第五篇：高三党的NOIP感想之读题篇

高三党的NOIP感想之读题篇

此篇文章旨在告诉后辈们读题时要注意哪些方面，希望你们不要犯和笔者一样213的错误。

重点：

不要信样例！绝对不要信样例！永远不要信样例！！

DAY1： 第一题：

歧义处：如果你看成有几张毯子覆盖在该点上，恭喜你，样例对了，你死了。

正解：覆盖该处的编号最大的毯子。

第二题：

歧义处1：两间客栈的咖啡馆中有一个满足即可。好吧，你比笔者213一点，你没看见“要求咖啡馆位于两人住的两家客栈话。

之间”这句歧义处2（笔者犯的错误）：非常自然而然行云流水般顺畅的认为咖啡馆要与客栈同样颜色。于是笔者213的爆零了。正解：你们现在一定都懂了„„

第三题：

绝对不会有理解上的歧义。不过这题问题不在这里„„ 于是乎：

普通OIer：我有-1我自豪。

文艺OIer：30%打表我相信有耐心的你一定会手动枚举。高端OIer：搜索+剪枝+神犇不解释。213OIer：有个游戏叫扫雷，挺好玩的。

DAY2： 第一题： 题目描述上无问题

第二题：

歧义处：那两个西格玛是先求和后相乘的，不要一时眼花，以为出题人逗你玩。正解：符合条件的物品个数 X 符合条件的物品的价值总和。

第三题：

只要你能看懂（最普通意义上的）你就能理解。压轴题么：

普通OIer：各种处理各种统计各种排序。文艺OIer：贪心。

高端OIer：„„（笔者真心不知道高端解法是神马）213OIer：有个游戏叫蜘蛛纸牌，挺好玩的。

总结：

样例都是精挑细选出来让你各种理解各种对的，测试点都是黑幕出的让你只有正确理解才能过得。

上面几种歧义应该把213类型概括挺全的了，不过，意外还是会有的，比如笔者DAY1第二题读了四遍还是悲催了„„大家一定要认真读题啊！

嘛，只能说有了前车之鉴希望你们能踩着笔者的尸体向前而不是又一次倒在了笔者的尸体上。最后，祝好运。笔者去了。