百度之星astar2012程序设计大赛 复赛试题(下)

《百度之星astar2012程序设计大赛 复赛试题(下)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、百度之星Astar2012程序设计大赛复赛试题（下）2012年6月17日，百度爱好者给大家带了2012百度之星Astar2012程序设计大赛复赛第二场的题目，供有兴趣的朋友研究。复赛第二场共3题。分别是轮子上的度度熊2、消灭病毒和BD语言翻译器。第一题、轮子上的度度熊2百度楼下有一块很大很大的广场。广场上有很多轮滑爱好者，每天轮滑爱好者们都会在广场上做一种叫做平地花式轮滑的表演。度度熊也想像他们一样在轮上飞舞，所以也天天和他们练习。因为度度熊的天赋，一下就学会了好多动作。但他觉得只是单独的做动作很没意思，动作的组合才更有欣赏

2、性。平地花式轮滑（简称平花），是穿轮滑鞋在固定数量的标准桩距间做无跳起动作的各式连续滑行。度度熊表演的舞台上总共有N个桩，而他也从自己会的动作中挑出M最好看的。但事情并没有这么简单。首先，每个动作因为复杂度不同，所以经过的桩的个数、消耗的体力也不尽相同。然而度度熊的体力是有限的。然后，为了保持连贯性，有些动作是接不起来的，所以每个动作都有他前面能接的一个动作的列表。更有甚者，有的动作要考虑前很多个动作才能确定是否能做出来。但度度熊这次把这些应该连接在一起的动作直接定为一个动作了。所以一个动作被描述为一个序列：{X1,X2,X

3、3,…Xn}表示，做这个动作的时候会先前进X1个桩，再前进X2个桩（注意：Xi可能是负数，这表示后退

4、Xi

5、个桩）。度度熊的完整表演需要恰好停在最后一个桩后面，并且在表演过程中不允许有前进/后退方向上桩不够的情况发生。最后，评分也很复杂。这次每个动作没有单独得分了，最终得分=组合得分+剩余体力。表演的时候，需要确定一个组合，表演过程中完成这组组合中所有的动作，同样的动作允许多次出现，但不能包含其他多余的动作。这个组合的分数就是最终得分中的“组合得分”。举个例子，总共有10个桩，体力上限是25，有以下几个动作：动作1：{1,3

6、,1}，需要5的体力。动作2：{1,-3,1}，需要4的体力。动作3：{3,3}，需要4的体力。动作4：{5}，需要3的体力。组合1：（动作1，动作2，动作4），得分15。组合2：（动作1，动作3），得分10。组合3：（动作2，动作3），得分5。最优方案应该是动作3+动作2+动作2+动作3。最后得分：组合得分5分+剩余体力9=14分。虽然，度度熊一下就算出来自己应该怎么表演了。但是他还是想考考精通编程的你。输入一开始一个整数T，表示有T组数据，每个数据如下格式：第一行有四个整数，N，M，P，Q。分别表示桩数、动作数、组合数和

7、体力上限。第二行M个整数，表示每个动作需要的体力。接下来M行，每行描述一个动作。每行的第一个数X(1<=X<=10)，表示动作分为X段。后面接X个数，这个长度为X的序列描述这个动作。接下来P行，每行描述一个组合。每行的前两个数Z(1<=Z<=M)，Y，Z表示组合中总共有Z个动作，Y表示组合能获得的分数。后面接Z个数，表示组合中包含的Z个动作的编号。输出对于每个数据，输出度度熊能获得的最高分数。样例输入11043255443313131-3123315315124210132523样例输出14提示保证至少有一个方案满足要求。度

8、度熊可以多次到达起始位置和终止位置。不存在两个组合包含完全一样的动作。1≤N≤1000，1≤M≤12，0≤P≤3000，1≤Q≤10000，所有分数之和在32位有符号整数范围之内。每个动作至少需要1的体力。第二题、消灭病毒最近科学家发现了一种代号为M的奇怪病毒，感染M病毒的熊会止不住卖萌。经过不懈努力，科学家们研制出N种可以杀死M病毒的药品。第i种药品在首次使用时可以杀死Di个M病毒;以后每次使用，药品的效果会逐次递减，即第2次使用可以杀死Di-1个病毒，第3次使用可以杀死Di-2个病毒,第4次使用可以杀死Di-3个病毒……

9、直到最后不再能杀死M病毒(杀死0个)。从现在开始，每秒钟科学家可以选择使用一种药品杀死M病毒。不过，目前研制出的药品还不够稳定：第i种药品会在从现在开始的第Ci秒后失去药效(不再能杀死M病毒)，因此只能在前Ci秒使用(若Ci=0则该药物在任何时候使用都没有效果)。科学家们想知道如何安排药品的使用，可以在所有药品失效前杀死最多的M病毒。输入输入的第一行是一个正整数T(1<=T<=10)，表示测试数据的组数。每组测试数据的第一行是一个整数N(0<=N<=100000)，表示药品的数目。以下N行每行包含两个整数Di,Ci(0<=D

10、i,Ci<=10^9)，表示第i种药品首次使用能杀死的M病毒数和药效持续时间。输出每组数据输出一个整数，在所有药品失效前最多能杀死的M病毒的数目。样例输入3011001000210021001样例输出05050200提示Di=0意味该药品对M病毒实际上没有药效，不能杀死任何M病毒。样例第3