Problem_Senior(高中).doc

2012年海淀区高中信息学奥林匹克竞赛试题 竞赛时间：2.5小时 题目名称 奇妙的数 四个国王 熊猫吃竹子 施工方案 Name fan king eat minlen 输入文件名 fan.in king.in eat.in minlen.in 输出文件名 fan.out king.out eat.out minlen.out 每个测试点时限 1 1 1 1 是否有部分分 无 无 无 无 题目类型 传统型 传统型 传统型 传统型 提交源程序须加后缀 对于Pascal语言 .pas .pas .pas 对于C 语言 .c .c .c 对于C++ 语言 .cpp .cpp .cpp 注意：最终测试时，所有编译命令均不打开任何优化开关。奇妙的数（fan） 【问题描述】 有一类正整数十分奇特。他们的十进制表示都是由0和1组成，并且他们的二进制表示里面1和0的数量一样多。例如： 10=(1010)2 现在想知道：在a~b之间的这样奇特的数有多少个呢？ 【输入格式】 输入的第一行包含两个整数，分别表示a和b。 【输出格式】 输出一个整数，表示大于等于a、小于等于b的奇特的数的个数。 【样例输入】 1 10 【样例输出】 1 【样例说明】 只有一个数：10 【数据规模】 1=a=b四个国王（king） 【问题描述】 小强在N*M的棋盘上摆国际象棋中的“国王”。如果两个“国王”占据的格子有公共边或者公共顶点，那么他们就会相互攻击。现在想知道，一共有多少种不同的方法摆上K个互不攻击的国王呢？ 【输入格式】 输入的第一行包含三个整数，分别表示N、M和K。 【输出格式】 输出一个整数，表示方法数。如果这个数字超过了2147483647，你只用输出2147483648即可。 【样例输入1】 3 3 4 【样例输出1】 1 【样例输入2】 5 100 50 【样例输出2】 2147483648 【样例说明】 第一个样例只有一种可能： XOX OOO XOX X表示一个国王，O表示一个空格子。 第二个样例的方法数显然多于2147483647。 【数据规模】 对70%的数据，N=5，M=5，0=K=4 对另外30%的数据，N=5，M=100，0=K=N*M 熊猫吃竹子（eat） 【问题描述】 熊猫喜欢吃竹子，更喜欢制作竹筒。 现在，熊猫有N个竹子。 每天醒来后，熊猫可以干3件事中的一个： 睡觉：熊猫睡了一个白天。 修建竹园：熊猫修建了一个竹园，这个竹园的建造需要S个竹子。从次日起的第i天，这个竹园将在清晨向熊猫提供A[i]根竹子。 制作竹筒：熊猫制作了一个超级精美的竹筒，消耗了S个竹子。注意：一旦竹子变成竹筒，熊猫就不能吃它了。 每天晚上，熊猫都要吃一个竹子。 熊猫总结自己的人生的时候，把自己的收获定为：K*竹筒数+剩下的竹子数 我们想知道，给熊猫T天的时间，他的收获最大是多少？ 【输入格式】 输入的第一行包含四个整数，分别表示T，N，S，K。 接下来一行T-1个整数，表示A数组。 【输出格式】 输出一个整数，表示熊猫的最大收获。 如果熊猫无法避免的被饿死，那么输出0. 【样例输入】 4 10 5 100 2 3 2 【样例输出】 103 【样例说明】 一共有三天的时间。熊猫的日志如下： 第一天：我醒来，修建了一个竹园，晚上吃了一个竹子，还剩下4根竹子。 第二天：我醒来，从昨天修建的竹园里收获了2个竹子，之后制作了一个竹筒，晚上吃了一个竹子，之后就没有竹子剩下了。 第三天：我醒来，从前天修建的竹园里收获了3个竹子，之后又睡了。晚上吃了一个竹子，还剩2个。 第四天：我醒来，从大前天修建的竹园里收获了2个竹子，之后，接着睡了。晚上起来吃了一个竹子，发现还剩下3个竹子。我总结了我这4天的生活：制作了一个竹筒，剩下了三个竹子，所以收获是103。 【数据规模】 对30%的数据，A数组里面所有的数都是一样的。T=10 对60%的数据，A数组里面所有的数都是一样的。T=40，N=10，S=10 对所有的数据，1=T=100，1=S=500，1=N=1000，SK=100000， A[i]是不超过50的自然数。  施工方案（minlen） 【问题描述】 c国边防军在边境某处的阵地是由n个地堡组成的。工兵连受命来到阵地要进行两期施工。 第一期的任务是挖掘暗道让所有地堡互联互通。现已勘测设计了m条互不相交的暗道挖掘方案，如果这m条暗道都实施挖掘，肯定能达到互联互通的目的。事实上，适当选择其中n-1个方案挖掘，就能实现互联互通，即从每个地堡出发都能到达其他任何一个地堡（允许经过别的地堡）。 连长精心谋算，在m个设计规划中选取了挖掘总距离最短且能保证互联互通的若干个暗道规划实施了挖掘，完成了第一期的施工任务后