省选江苏第三轮试题

1、特殊说明：1、Problem 4 星球大战的时限为 5s，其他各题时限均为 1s，评测配置为 2.8GHz，768MB2、Problem 1 最大数只有 8 个数据，满分 80 分。因此 6 道题总分为 580 分。3、Problem 4 是 85 分，Problem 6 是 115 分。4、第一试 4.5h，第二试 5h，280+可以保证通过本轮选拔。Problem 1最大数标志：maxnumber.*试题描述：现在请求你1、查询操作。语法：Q L一个数列，要求提供以下两种操作：功能：查询当前数列中末尾 L 个数中的最大的数，并输出这个数的值。限制：L 不超过当前数列的长度。2、操作。语法：

2、A n功能：将 n 加上 t，其中 t 是最近一次查询操作的（如果还未执行过查询操作，则 t=0)，并将所得结果对一个固定的常数 D 取模，将所得的末尾。限制：n 是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个数。到数列输入文件：第一行两个整数，M 和 D，其中 M 表示操作的个数(M = 200,000)， D 如上文中所述，满足(0D2,000,000,000)接下来的 M 行，每行一个字符串，描述一个具体的操作。语法如上文所述。输出文件：对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。输入样例：5 100A 96Q 1A 97Q 1Q 2输出样例：96939

3、6Problem 2球形空间产生器。标志：sphere.*问题描述：有一个球形空间产生器能够在 n中产生一个坚硬的球体。现在，你被困在了这个 n 维球体中，你只知道球面上 n+1 个点的坐标，你需要以最快的速度确定这个 n 维球体的球心坐标，以便于摧毁这个球形空间产生器。输入文件：第一行是一个整数，n。接下来的 n+1 行，每行有 n 个实数，表示球面上一点的 n 维坐标。每一个实数精确到小数点后 6 位，且其绝对值都不超过 20000。输出文件：有且只有一行，依次给出球心的 n 维坐标（n 个实数），两个实数之间用一个空格隔开。每个实数精确到小数点后 3 位。数据保证有解。你的须和标准输出一

4、模一样才能够得分。必输入样例：20.0 0.0-1.0 1.01.0 0.0输出样例：0.500 1.500数据规模：对于 40%的数据，1=n=3对于 100%的数据，1=n=10提示：给出两个定义：1、球心：到球面上任意一点距离都相等的点。2、距离：设两个 n 为空间上的点 A, B 的坐标为(a1, a2, , an), (b1, b2, , bn)，则 AB 的距离定义为：dist = sqrt( (a1-b1)2 + (a2-b2)2 + + (an-bn)2 )Problem 3标志：prefix.*问题描述：火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方火星人说，有

5、这样一个字符串：madamimadam，号：这个字符串的各个字符予以标现在，火星人定义了一个函数 LCQ(x, y)，表示：该字符串中第 x 个字符开始的字串，与该字符串中第 y 个字符开始的字串，两个字串的公共前缀的长度。比方说，LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0序号：1234567891011字符madamimadam在研究 LCQ 函数的过程中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出 LCQ 函数的值；同样，如果求出了 LCQ函数的值，也可以很快地将该字符串的后缀排好序。尽管火星人聪明地找到了求取

6、 LCQ 函数的快速算法，但不甘心认输的地球人又给火星人出了个难题：在求取 LCQ 函数的同时，还可以改变字符串本身。具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此复杂很快地求取 LCQ 函数的值。中，火星人是否还能够做到输入文件：第一行给出初始的字符串。第二行是一个非负整数 M，表示操作的个数。接下来的 M 行，每行描述一个操作。操作有 3 种，如下所示：1、询问。语法：Q x y，x, y 均为正整数。功能：计算 LCQ(x, y)限制：1 = x, y = 当前字符串长度。2、修改。语法：R x d，x 是正整数，d 是字符。

7、功能：将字符串中第 x 个数修改为字符 d。限制：x 不超过当前字符串长度。3、：语法：I x d，x 是非负整数，d 是字符。功能：在字符串第 x 个字符之后限制：x 不超过当前字符串长度。字符 d，如果 x = 0，则在字符串开头。输出文件：对于输入文件中每一个询问操作，你都应该输出对应的案一行。一个答样例输入： madamimadam 7Q 1 7Q 4 8Q 10 11R 3 aQ 1 7I 10 aQ 2 11样例输出：51021数据规模：对于 100%的数据，满足：1、所有字符串自始至终都只有小写字母2、M = 150,000。3、字符串长度 L 自始至终都满足 L = 100,0

8、004、询问操作的个数不超过 10,000 个。对于第 1，2 个数据，字符串长度自始至终都不超过 1,000对于第 3，4，5 个数据，没有操作。Problem 4星球大战标志：starwar.*试题描述：很久以前，在一个遥远的星系，一个的靠着它的超级统整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快又重新造出了他的超级。凭借这超级的力量，开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反抗军首领交给你一个任务：给出原来两个星球

9、之间的以太隧道连通情况以及打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同通块中）。输入文件：输入文件第一行包含两个整数，N (1 = N = 2M) 和M (1 = M =200,000)，分别表示星球的数目和以太隧道的数目。星球用 0N-1 的整数。接下来的 M 行，每行包括两个整数 X, Y，其中（0=XYN），表示星球 X和星球 Y 之间有以太隧道。注意所有的以太隧道都是双向的。接下来一行是一个整数 K，表示计划打击的星球个数。接下来的 K 行每行一个整数 X，满足 0=XN，表示总是

10、按输入的顺序依次摧毁星球的。计划打击的星球。输出文件：输出文件的第一行是开始时星球的连通块个数。接下来的 N 行，每行一个整数，表示经过该次打击后现存星球的连通块个数。样例输入：8 130 11 66 55 00 61 22 33 44 5757样例输出：111233Problem 5标志：dotr.*问题描述：DotR (Defense of the Robots) Allstars 是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图 DotA (Defense of the Ancients) Allstars。DotR 里面魔兽地图的只有一个属性力量。他们需要装备来自己的力量值，每件

11、装的力量值等于它购备都可以使佩戴它的的力量值提高固定的点数，所以买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备需要用基本装备或者较低级的高级装备来，不需要附加的金币。装备的路线可以用一棵树来表示。比如，Sange and Yasha 的需要 Sange, Yasha 和 Sange and Yasha Recipe Scroll 三样物品。其中 Sange 又要用Ogre Axe, Belt of Giant Strength 和 Sange Recipe Scroll每件基本装备都有数量限制，这限制了你不能的装备。地某些性价比很高现

12、在，Spectre 有 M 个金币，他想用这些钱装备使自己的力量值尽量高。你能帮帮他吗？他会教你魔法 Haunt（附体）作为回报的。输入文件：输入文件第一行包含两个整数，N (1 = n = 51) 和 m (0 = m =2,000)。分别表示装备的种类数和金币数。装备用 1 到 N 的整数。接下来的 N 行，按照装备 1 到装备 n 的顺序，每行描述一种装备。每一行的第一个正整数表示这个装备贡献的力量值。接下来的非空字符表示这种装备是基本装备还是高级装备，A 表示高级装备，B 表示基本装备。如果是基本装备，紧接着的两个正整数分别表示它的单价（为金币）和数量限制（不超过 100）。如果是高级

13、装备，后面紧跟着一个正整数 C，表示这个高级装备需要 C 种低级装备。后面的 2C 个数，依次描述某个低级装备的种类和需要的个数。输出文件：第一行包含一个整数 S，表示最多可以多少点力量值。接下来的N 行，每行一个整数，描述你提供的方案。第 I 行的整数表示你提供的方案中编号为 I 的装备的数目。输入数据保证正确的 S 不会超过长整范围。输出任意一个满足要求的方案均可。本题没有部分分，你必须完全得到最优可以得分。样例输入：10 595 A 3 6 1 9 2 10 11 B 5 31 B 4 31 B 2 38 A 3 2 1 3 1 7 11 B 5 35 B 3 315 A 3 1 1 5 1 4 11 B 3 51 B 4 3样例输出：330002200100Problem 6标志：award.*问题描述：现在给出了一个简单无向最小生成树计数图。你不满足出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对 31011 的模就可以了。输入文件：第一行包含两个数，n 和 m，其中 1