微软编程之美2013初试题目

《微软编程之美2013初试题目》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、BeautyofProgramming2013初赛第一场题目列表>竞价时间限制: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,0,1}，-1表示Alice买到的钻石会比

3、Bob少，0表示两人能买到一样多，1表示Alice能买到更多钻石。所有数据按读入顺序从1开始编号。数据范围1≤T≤1000小数据：0≤N≤10;0相似字符串时间限制:4000ms内存限制:256MB描述对于两个长度相等的字符串，我们定义其距离为对应位置不同的字符数量，同时我们认为距离越近的字符串越相似。例如，“0123”和“0000”的距离为3，“0123”和“0213”的距离则为2，所以与“0000”相比，“0213”和“0123”最相似。现在给定

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

5、1:2Case#2:1Case#3:1题目列表>仙剑5前传之璇光殿时间限制:4000ms内存限制:256MB描述仙剑是一款经典的RPG游戏，最近又推出了仙剑5前传。Alice身为忠实的仙剑粉丝，当然是在第一时间就开始玩了。迷宫以及各类小游戏是仙剑系列的一大传统，这次也不例外。而且还增加了称号系统，玩家如果在满足一定条件下通过迷宫或是完成小游戏，都可以获得相应的称号奖励。Alice虽然智商也不算太低，顺利的完成游戏还是没什么问题的，但是某些称号对于她来说好像就比较困难，所以她来找你帮忙。在这个迷宫中，有很多魔法台需要关闭，也有很多宝箱可以捡。你最主要的目标就是关闭所有的魔法台，一旦所有

6、魔法台都被关闭后，立刻通关。这个迷宫中有两个称号可以获得，一个要求拣到所有的宝箱，另一个要求在一定时间内完成。为了让迷宫变得更加复杂，迷宫中还有两种特殊的法阵。第一种法阵是加速阵，可以瞬间使玩家的移动速度提高5m/s（初始速度为30m/s）。第二种是五灵阵，玩家必须按照五灵相克相生的关系来选择开启适当的阵法才可顺利通过。若玩家顺利通过五灵阵，则也可获得5m/s的速度提升，反之，用户则会被困在原地5秒钟。幸运的是，Alice在网上找到了攻略，所以在通过五灵阵时，她只需要查看一下即可保证顺利通过。不过介于她的思考速度，她需要3秒钟来查看攻略。Alice想知道如果她想要拣到所有的宝箱，那么

7、最快多长时间能够通过这个迷宫呢？输入输入数据的第一行包含一个整数T，表示数据组数。接下来有T组数据，每组数据中：·第一行包含两个整数N,M，表示迷宫中节点个数以及边数。节点由1到N标号。·接下来的M行每行包含三个整数a,b,len，表示节点a和节点b之间有一条长度为len米的路。·接下来的一行包含一个整数NM，表示魔法台的个数。下一行NM个整数，表示魔法台所在的节点编号。·接下来的一行包含一个整数NT，表示宝箱的个数。下一行NT个整数，表示宝箱所在的节点编