第36届ACMICPC网络赛试题(大连、上海、成都)

《第36届ACMICPC网络赛试题(大连、上海、成都)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2011ACM/ICPC网络赛试题《大连站》1001问题描述你们记得我们儿时的时光吗？当我们还是孩子的时候，我们对我们周围的一切事物都感兴趣。一件小事或一个简单的游戏会使我们愉悦很长时间。LLL是个淘气的小男孩。现在，他长大了。深夜，他经常忘记一些事情，包括他儿时的一个令他非常惬意的简单游戏。游戏规则如下：在地上放置有很多砖块，小LLL需要使用这些砖块来盖“摩天大楼”。砖块分为三种类型，每种类型的砖块都用一个整数d标记。我们用4个整数ai,bi,ci,di来描述每个砖块的形状。其中，ai>bi分别表示砖块的长和宽，ci表示砖块

2、的厚度。我们知道ci必须与地面垂直。di表示砖块的类型。①当di=0时，砖块的长和宽一定要大于等于压在它下面砖块的长和宽；②当di二1时，砖块的长和宽不仅要犬于等于压在它下面砖块的长和宽，而且砖块的面积一定要大于压在它下面的砖块面积；③当di=2时，砖块的长和宽一定要大丁•压在它下面砖块的长和宽。现有一些砖块，你知道怎样用它们来盖最高的“摩天大楼”吗？输入输入有很多测试实例。在每个测试实例屮，第一行是一个整数n(0

3、0",d=0或1或2)。输入结朿标志为n=0o输出输出一行一个整数表示使用n个砖块构建的最高“摩天大楼”的高度。样例输入样例输出3241010120101012110101122111010111101011101002问题描述欧拉函数：05)(有时称为0函数)是用于求小于n且与n互素的数的个数。例如:小于9且与9互素的数是1,2,4,5,7和8,即0(9)=6。HG是XY的主人。一天，HG想通过一个数学游戏教给XY-些关于欧拉函数的知识。即HG给出一个正整数N,XY告诉他的主人在不小于2,且不大于N的范围内的数n的值，使得0

4、(斤)具有最人值。很快，HG发现这对于XY似乎是一件易事，因为XY很快就用一段小程序给出了正确答案。于是，HG使用了一些变化，现在，他要求XY告诉他在不小于2,且不大于N的范围内的数n的值，使得n/^ri)具有最大值。这次，由于XY没有充足的知识解决此问题，因此，遇到了一些困难。现在，他需要你的帮助。输入有T(1WTW50000)组测试实例，对于每一个测试实例，标准输入n(2WnW10100)占一行。输出对于每一个测试实例，单行输出上面问题的答案。样例输入样例输出10610030提示：如果最大值多于1个，我们输岀达到该值的最小

5、的n。1003问题描述人们已经在火星上发现了一种新的金矿。这种金矿呈类点状分布，通过路径将这些点连接起来，形成一棵树的形状。人们发射了k个机器人到火星上收集这些金矿，不知什么原因，这些机器人着陆的位置S首先被识别了，换句话说，所有机器人应该从S点开始它们的工作。每个机器人可以从火星上的任何地方返回地球，当然，它们不能再返回火星。我们已经知道了火星上全部的路径信息。为了降低全部能量的耗费，我们应该制定一个最佳方案使消耗的能量最小。输入输入多个实例。在每个实例屮，第一行有三个整数N,S,K,分别表示金矿数量、着陆位置和机器人数量；

6、接下来的n-1行的每一行将给出三个整数x,y,w,表示点x与点y之间有一条路径，需要耗费Wo(1WNW10000,1WSWN,lWkW10,lWx,yWN,lWwWIOOOO)输出对于每个实例，输出一行最小能量耗费值。样例输入样例输出31131211313122121131提示：在第1个实例中：1-2-1-3,耗费值为3；在第2个实例中:1->2；1->3,耗费值为2。1004问题描述一年一度的青蛙王国里的游戏又开始了。其中，最著名的游戏被称为“铁蛙三项其中的一项比赛是跳远。这个项目要求参加比赛的青蛙跳过一条河。河宽为L(1W

7、LW10J。n(lWnW500000)个石头从河的一边到另一边依次排列成一条直线，青蛙只能通过跳在这些石头上的方式过河。如果它们跳到河里了，就出局。青蛙最多有m(lWmWn+1)次跳跃机会，现在，青蛙要知道如果它们要过河，至少它们应该具备什么能力(即青蛙最长的跳远距离)。输入输入包括几个实例：每一个实例的第一行有三个正整数L、n和叫接着有n行，每行表示从开始的河岸到第n个石头的距离，在一个地方不能出现两个石头。输出对于每个实例，输出一个整数，表示青蛙至少应具备的能力。样例输入样例输出612422533111112181005问

8、题描述一场战争屮，敌人的智能非常重要。现在，我军已经掌握了敌军区的情况，并且知道这些战区能依靠网络直接或间接通信，我们也知道敌人止准备修建一条新通信线以便增强他们的通信网络。我们的任务是摧毁他们的通信网络，以便使得他们的一些战区之间不能相互通信。每一条线有它自己的“摧毁成木”