微软编程之美2013初试题目

1、Beauty of Programming 2013初赛第一场题目列表 > 竞价时间限制: 1000ms 内存限制: 256MB描述Alice和Bob都要向同一个商人购买钻石。商人手中有 N 颗钻石，他会将它们一颗颗地卖给他们，Alice和Bob通过竞价的方式来决定钻石的归属。具体的过程如下：商人首先指定其中一个人开始报价，之后两人轮流报价，要求是一定要比对方报的价格更高。任何时候，如果一个人不愿出价或者出不起价钱时，可以宣布弃权，则对手以最后一次报的价格将钻石买下。当然，如果两人都没钱，商人是不会卖钻石的。首次报价至少为 1，并且只能报整数的价钱。Alice和Bob特别爱攀比，因此他们

2、都希望能比对方买到更多的钻石。Alice和Bob各自带了 CA 和 CB 的钱用于竞拍钻石。此外，Alice和商人有很不错的私人关系，因此商人总是会让Alice先报价。现在请问，在Alice和Bob都用最优策略的情况下，谁能买到更多钻石？假设双方都知道对方手中的现金数量，以及商人将要拍卖的钻石数量 N。输入输入文件包含多组测试数据。第一行，给出一个整数T，为数据组数。接下来依次给出每组测试数据。每组数据为三个用空格隔开的整数 N，CA，CB，表示钻石的数量，以及双方带的现金数量。输出对于每组测试数据，输出一行"Case #X: Y"，其中X表示测试数据编号，Y的取值为-1,

3、 0, 1，-1表示Alice买到的钻石会比Bob少，0表示两人能买到一样多，1表示Alice能买到更多钻石。所有数据按读入顺序从1开始编号。数据范围1 T 1000小数据：0 N 10; 0 < CA, CB 10大数据：0 N 105; 0 < CA, CB 106样例输入24 3 57 4 7样例输出Case #1: 0Case #2: 1题目列表 > 相似字符串时间限制: 4000ms 内存限制: 256MB描述对于两个长度相等的字符串，我们定义其距离为对应位置不同的字符数量，同时我们认为距离越近的字符串越相似。例如，“0123”和“0000”的距离为 3，“0123

4、”和“0213”的距离则为 2，所以与“0000”相比，“0213”和“0123”最相似。 现在给定两个字符串 S1 和 S2，其中 S2 的长度不大于 S1。请在 S1 中寻找一个与 S2 长度相同的子串，使得距离最小。输入输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组测试数据恰好占两行，第一行为字符串 S1，第二行为 S2。所有字符串都只包括“0”到“9”的字符。输出对于每组测试数据，单独输出一行“Case #c: d”。其中，c 表示测试数据的编号（从 1 开始），d 表示找到的子串的最小距离。数据范围1 T 100 小数据：字符串长度不超过 1000 大数据：字符串长度

5、不超过 50000样例输入3012345678932101020304050607080940420121221211样例输出Case #1: 2Case #2: 1Case #3: 1题目列表 > 仙剑5前传之璇光殿时间限制: 4000ms 内存限制: 256MB描述仙剑是一款经典的RPG游戏，最近又推出了仙剑5前传。Alice身为忠实的仙剑粉丝，当然是在第一时间就开始玩了。迷宫以及各类小游戏是仙剑系列的一大传统，这次也不例外。而且还增加了称号系统，玩家如果在满足一定条件下通过迷宫或是完成小游戏，都可以获得相应的称号奖励。Alice虽然智商也不算太低，顺利的完成游戏还是没什么问题的，但

6、是某些称号对于她来说好像就比较困难，所以她来找你帮忙。在这个迷宫中，有很多魔法台需要关闭，也有很多宝箱可以捡。你最主要的目标就是关闭所有的魔法台，一旦所有魔法台都被关闭后，立刻通关。这个迷宫中有两个称号可以获得，一个要求拣到所有的宝箱，另一个要求在一定时间内完成。为了让迷宫变得更加复杂，迷宫中还有两种特殊的法阵。第一种法阵是加速阵，可以瞬间使玩家的移动速度提高5m/s（初始速度为30m/s）。第二种是五灵阵，玩家必须按照五灵相克相生的关系来选择开启适当的阵法才可顺利通过。若玩家顺利通过五灵阵，则也可获得5m/s的速度提升，反之，用户则会被困在原地5秒钟。幸运的是，Alice在网上找到了攻略，所

7、以在通过五灵阵时，她只需要查看一下即可保证顺利通过。不过介于她的思考速度，她需要3秒钟来查看攻略。Alice想知道如果她想要拣到所有的宝箱，那么最快多长时间能够通过这个迷宫呢？输入输入数据的第一行包含一个整数 T，表示数据组数。接下来有 T 组数据，每组数据中： 第一行包含两个整数 N, M，表示迷宫中节点个数以及边数。节点由 1 到 N 标号。 接下来的 M 行每行包含三个整数 a, b, len，表示节点 a 和节点 b 之间有一条长度为 len 米的路。 接下来的一行包含一个整数 NM，表示魔法台的个数。下一行 NM 个整数，表示魔法台所在的节点编号。 接下来的一行包含一个整数 NT，表

8、示宝箱的个数。下一行 NT 个整数，表示宝箱所在的节点编号。 接下来的一行包含一个整数 NS，表示加速阵的个数。下一行 NS 个整数，表示加速阵所在的节点编号。 接下来的一行包含一个整数 NR，表示五灵阵的个数。下一行 NR 个整数，表示五灵阵所在的节点编号。 最后一行包含一个整数 S，表示玩家的出发节点编号。输出对于每组数据，输出一行"Case #X: Y",其中 X 为数据组数编号，从 1 开始，Y 为通过该迷宫的最短时间，四舍五入保留5位小数。数据范围1 T 100 len 1000小数据：1 N 300 M 2001 NM 30 NT, NS, NR 3大数据：1

9、N 1000 M 20001 NM 40 NT, NS, NR 4提示1. 每个节点上至多有一个特殊的物品。2. 当你经过魔法台，加速阵以及宝箱时，可以选择不触发它。3. 每个法阵都是一次性的，不会被多次触发。样例输入22 11 2 301 200013 21 2 1002 3 1001300121样例输出Case #1: 1.00000Case #2: 9.19048初赛第二场题目列表 > 管道系统时间限制: 5000ms 内存限制: 256MB描述你正在参与一项输油管道的项目，此项目的目标是架设一组输油管道系统，使得从源头到目的地输送的石油流量最大。如果直接从源头架设管道到目的地，一

10、旦管道有损坏，将无法输送石油。为了增强管道系统抵抗破坏的能力，你决定设置 N - 2 个中间节点，从而把管道分散开来。 源头和目的地可以视为特殊的节点，他们的编号分别为 1 和 N，而其他的中间节点的标号为 2 到 N - 1。每条管道有特定的流量限制 c，石油可以以不超过 c 的速率在管道内流动。两个节点之间至多由一条管道连接，也就是说这两个节点之间单位时间内流动的石油不超过 c。 现在你们已经选定了 N 个节点，并且制定好了建设计划。你想知道，每当一条管道建造完成，从节点 1 到节点 N 最大流量能够增加多少。输入输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组测试数据的第一

11、行包括两个整数 N 和 M，表示节点的数量和将要建造的管道数量。接下来 M 行按建造顺序描述每条管道，每行包括三个整数 i, j, c，表示要在节点 i 和 j 之间建造一条容量为 c 的管道。输出对于每组测试数据，先输出一行“Case #c:”，其中 c 为测试数据编号（从 1 开始）。紧接着按建造顺序输出使得总流量增加的管道编号和相应的增加量，以一个空格隔开。数据范围1 T 100 0 M N(N - 1/2 1 v u N 1 c 100 小数据：2 N 20 大数据：2 N 200样例输入32 11 2 34 51 2 92 3 73 4 62 4 41 3 15 71 2 11 3

12、21 4 32 5 43 2 34 3 33 5 2样例输出Case #1:1 3Case #2:3 64 35 1Case #3:4 15 26 17 2题目列表 > 仙剑5前传之软星包子时间限制: 1000ms 内存限制: 256MB描述仙剑是一款经典的RPG游戏，最近又推出了仙剑5前传。Alice身为忠实的仙剑粉丝，当然是在第一时间就开始玩了。迷宫以及各类小游戏是仙剑系列的一大传统，这次也不例外。而且还增加了称号系统，玩家如果在满足一定条件下通过迷宫或是完成小游戏，都可以获得相应的称号奖励。Alice虽然智商也不算太低，顺利的完成游戏还是没什么问题的，但是某些称号对于她来说好像比较

13、困难，所以她来找你帮忙。仙剑5前传中增加了软星包子这种很萌的NPC，它散落在世界各地，你每找到一个，都可以挑战他，挑战成功可以拿到一些卡片。挑战具体说来就是一个记忆力游戏，有 N 种卡片，每种两张，总共 2N 张卡片面朝下放置。玩家可以点击面朝下的卡片并将其翻面。当有两张卡片正面朝上时，如果这两张卡片是同一种，则将这两张卡片收走，否则的话，再将这两张卡片面朝下放置在原位。Alice的记忆力很差，只能记住 K 张卡片（包括刚刚翻开的）。她的策略如下：* 当没有卡片正面朝上时：* 如果她记住的卡片中有两张是同一种的，那就翻开那两张卡片；* 否则，她随机的翻开一张她不知道的卡片。* 当有一张卡片正面

14、朝上时：* 如果她记得另一张同样的卡片在哪里，就直接翻开那张；* 否则，她随机的翻开一张她不知道的卡片。Alice想知道，她期望要点多少次才可以完成这个小游戏。输入输入数据的第一行包含一个整数 T，表示数据组数。接下来有 T 组数据，每组数据中有一行，包含两个整数 N, K。输出对于每组数据，输出一行"Case #X: Y"，其中 X 为数据组数编号，从 1 开始，Y 为期望的步数。绝对误差在1e-6以内或相对误差在1e-8以内即可。数据范围1 T 101 K 10小数据：1 N 100大数据：1 N 100000提示下面是一种可能的游戏过程，用来解释Alice可以记住 K

15、 张卡片这一点：假设N = 5, K = 3已经翻开的卡片刚刚翻开的卡片Alice记住的卡片解释-A0A0A0B0A0, B0-C0A0, B0, C0C0B1B0, C0, B1-B0, B1C0, B0, B1B0和B1都在记忆中，直接翻开移除-A1C0, A1A1D0C0, A1, D0-E0A1, D0, E0E0E1D0, E0, E1碰巧翻到两张一样的，E0和E1移除-D1D0, D1D1D0D1, D0Alice记得D0，D0和D1移除-A1A1继续样例输入22 13 3样例输出Case #1: 8.000000Case #2: 9.000000题目列表 > 集会时间限制:

16、 2000ms 内存限制: 256MB描述在一条河的一侧，分布着 N 个村庄。这些村庄平日里需要一些贸易往来，然而商人们来回走遍每一座村庄是非常辛苦的，于是他们决定每个月都在河边举行一次集会，大家都来集会上购买需要的物品。然而在集会地点的选择上，大家却有分歧，因为谁都不愿意集会的地点离自己村庄非常远。经过一番激烈的讨论之后，大家决定要将集会地点挑选在这样一个位置：它离最远的村庄的距离要尽可能的近。我们把河看做一条足够长的直线，河岸就是平面坐标系上 y = 0 的这条线，y < 0 的区域是河水，而所有村庄都在 y 0 的区域里。现在给出所有村庄的平面坐标，你要在河岸上找到这样一个位置，使得它到所有村庄的最远距离最小。输入输入文件包含多组测试数据。第一行，给出一个整数 T，为数据组数。接下来依次给出每组测试数据。每组数据的第一行是一个整数 N，表示村庄的数量。接下来 N 行，每行有两个实数