百度之星Astar2012程序设计大赛 复赛试题（下）

百度之星Astar2012程序设计大赛 复赛试题（下）

2012年6月17日，百度爱好者给大家带了2012百度之星Astar2012程序设计大赛复赛第二场的题目，供有兴趣的朋友研究。复赛第二场共3题。分别是轮子上的度度熊2、消灭病毒和BD语言翻译器。

第一题、轮子上的度度熊2

百度楼下有一块很大很大的广场。广场上有很多轮滑爱好者，每天轮滑爱好者们都会在广场上做一种叫做平地花式轮滑的表演。度度熊也想像他们一样在轮上飞舞，所以也天天和他们练习。

因为度度熊的天赋，一下就学会了好多动作。但他觉得只是单独的做动作很没意思，动作的组合才更有欣赏性。

平地花式轮滑（简称平花），是穿轮滑鞋在固定数量的标准桩距间做无跳起动作的各式连续滑行。度度熊表演的舞台上总共有N个桩，而他也从自己会的动作中挑出M最好看的。 但事情并没有这么简单。首先，每个动作因为复杂度不同，所以经过的桩的个数、消耗的体力也不尽相同。然而度度熊的体力是有限的。

然后，为了保持连贯性，有些动作是接不起来的，所以每个动作都有他前面能接的一个动作的列表。更有甚者，有的动作要考虑前很多个动作才能确定是否能做出来。但度度熊这次把这些应该连接在一起的动作直接定为一个动作了。所以一个动作被描述为一个序列：{X1, X2, X3, ? Xn}表示，做这个动作的时候会先前进X1个桩，再前进X2个桩（注意：Xi可能是负数，这表示后退|Xi|个桩）。度度熊的完整表演需要恰好停在最后一个桩后面，并且在表演过程中不允许有前进/后退方向上桩不够的情况发生。

最后，评分也很复杂。这次每个动作没有单独得分了，最终得分=组合得分+剩余体力。表演的时候，需要确定一个组合，表演过程中完成这组组合中所有的动作，同样的动作允许多次出现，但不能包含其他多余的动作。这个组合的分数就是最终得分中的“组合得分”。

举个例子，总共有10个桩，体力上限是25，有以下几个动作： 动作1：{1,3,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。分别表示桩数、动作数、组合数和体力上限。 第二行M个整数，表示每个动作需要的体力。

接下来M行，每行描述一个动作。每行的第一个数X(1<=X<=10)，表示动作分为X段。后面接X个数，这个长度为X的序列描述这个动作。

接下来P行，每行描述一个组合。每行的前两个数Z(1<=Z<=M)，Y，Z表示组合中总共有Z个动作，Y表示组合能获得的分数。后面接Z个数，表示组合中包含的Z个动作的编号。

输出

对于每个数据，输出度度熊能获得的最高分数。 样例输入 1 10 4 3 25 5 4 4 3 3 1 3 1 3 1 -3 1 2 3 3 1 5 3 15 1 2 4 2 10 1 3 2 5 2 3 样例输出 14 提示

保证至少有一个方案满足要求。度度熊可以多次到达起始位置和终止位置。不存在两个组合包含完全一样的动作。

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个病毒??直到最后不再能杀死M病毒(杀死0个)。

从现在开始，每秒钟科学家可以选择使用一种药品杀死M病毒。不过，目前研制出的药品还不够稳定：第i种药品会在从现在开始的第Ci秒后失去药效(不再能杀死M病毒)，因此只能在前Ci秒使用(若Ci=0则该药物在任何时候使用都没有效果)。科学家们想知道如何安排药品的使用，可以在所有药品失效前杀死最多的M病毒。

输入

输入的第一行是一个正整数T(1 <= T <= 10)，表示测试数据的组数。 每组测试数据的第一行是一个整数N(0 <= N <= 100000)，表示药品的数目。 以下N行每行包含两个整数Di,Ci(0 <= Di, Ci <= 10^9)，表示第i种药品首次使用能杀死的M病毒数和药效持续时间。

输出

每组数据输出一个整数，在所有药品失效前最多能杀死的M病毒的数目。 样例输入 3 0 1 100 1000 2 100 2 100 1 样例输出 0 5050 200 提示

Di=0意味该药品对M病毒实际上没有药效，不能杀死任何M病毒。

样例第3组数据解释：第一秒用2号药品杀死100个病毒。第二秒的时候2号药品已经过期，这时用1号药品能再杀死100个病毒。第三秒的时候药品都过期了，总计可以杀死200个病毒。

第三题、BD语言翻译器

度度熊每天上下班都要被堵在路上至少两个小时。在这段时间里，他只能靠玩手机游戏打发时间。

这天，度度熊又被堵在路上了。望着自己的手机，度度熊突发奇想：如果能够用自己的手机来写程序，不就可以充分利用这些宝贵的时间了么？

当然，用手机写程序最大的坏处在于，手机只有12个键：10个数字键、一个“#”键和一个“*”键。因此，度度熊特意设计了一种只包含有这些符号的语言——Best Digital （简称BD语言）。这样的话，度度熊就可以在路上用手机编写BD程序，然后使用翻译器将其直接翻译为对应的C++程序。

虽然度度熊一下就知道怎么实现这个翻译器了。但是他还是想考考精通编程的你。 BD语言只能处理32位有符号整数一种类型的数据（对应C++中的int类型）。在BD语言中，常量表示为“数字串*”，对应C++中的一个由该数字串表示的非负整数，其中数字串长度至少为1且允许有前导0（但翻译后需去掉前导0），该非负整数不能超过int范围；变量表示为“#数字串*”，对应C++的一个名字为“r数字串”的变量，该数字串长度同样至少为1。

BD程序中有如下四种类型的语句（说明：在对应的C++语句中，下划线为空格）： 语句类型 BD语言语句 对应C++代码 赋值语句

1rxoy r_=_x_o_y; 条件语句 2xcy if_(x_c_y)_{ 循环语句 3x

for_(int_it_=_0;_it_<_x;_it++)_{ 结束语句 0 } 其中，

r是一个变量，x和y既可以是变量，也可以是常量；

在赋值语句中，o是一个二元四则运算符，1为“+”，2为“-”，3为“*”，4为“/”。注意，若为除法，除数不能为常数0，但可以是变量。

在条件语句中，c是一个比较操作符，1为“==”，2为“<”，3为“>”;

在循环语句对应的C++语句中，循环变量it的t是一个数字（从0开始编号），即循环变量可以是i0，i1，??，i9，i10，i11，??，在翻译时，应选择最小的不与外层循环相同的t。

下面，度度熊举了个例子来详细说明BD程序是如何翻译成C++程序的（说明：程序中的空格均用下划线给出）。

假设给定的BD程序为：3100*1#1*#1*11*1#0*#0*1#1*0 步骤1

根据之前给出的对应关系，可直译为： C++语句 原BD语句

for_(int_i0_=_0;_i0_<_100;_i0++)_{ 3100* r1_=_r1_+_1; 1#1*#1*11* r0_=_r0_+_r1; 1#0*#0*1#1*

本文来源：https://www.bwwdw.com/article/5gvh.html