3.11 美团暑期实习 后端 笔试 第一场

1、修改字符串最小次数

小美有一个由数字字符组成的字符串。现在她想对这个字符串进行一些修改。 具体地，她可以将文个字符串中任意位置字符修改为任意的数字字符。她想知道，至少进行多少次修改，可以使得“修改后的字符串不包含两个连续相同的字符?

例如，对于字符串”111222333", 她可以进行3次修改将其变为” 121212313"。

2、收集金币

小团在一个n*m的网格地图上探索。 网格地图上第i行第j列的格子用坐标(i,j)简记。初始时，小团的位置在地图的左上角，即坐标(1,1)。 地图上的每个格子 上都有一定的金币， 特别地，小团位于的初始位置(1,1)上的金币为0。小团在进行探索移动时，可以选择向右移动-格(即从(x,y)到达(x,y+1))或向下移动一格(即从(x,y)到达(x+1,y)) 。地图上的每个格子都有一个颜色，红，色或蓝色。如果小团次移动前后的两个格子颜色不同，那么他需要支付k个金币才能够完成这-次移动;如果移动前后的两个格子颜色相同，则不需要支付金币。小团可以在任意格子选择结束探索。现在给你网格地图上每个格子的颜色与金币数量，假设小团初始时的金币数量为0，请你帮助小团计算出最优规划，使他能获得最多的金币，输出能获得的最多 金币数量即可。注意:要求保证小团任意时刻金币数量不小于零。

3、流星最佳观测时间

小美是位天文爱好者， 她收集了接下来段时间中所有 会划过她所在的观测地上空的流星信息。具体地，她收集了n个流星在她所在观测地上空的出现时刻和消失时刻。对于一个流星，若'其的出现时刻为s，消失时刻为t，那么小美在时间段[s, t]都能够观测到它。对于一个时刻，观测地上空出现的流星数量越多，则小美认为该时刻越好。小美希望能够选择一个最佳的时刻进行观测和摄影，使她能观测到最多数量的流星。现在小美想知道 ，在这个最佳时刻，她最多能观测到多少个流星以及一共有多少个最佳时刻可供她选择。

4、坦克大战

小D和小W最近在玩坦克大战，双方操控自己的坦克在16*1 6的方格图上战斗，小D的坦克初始位置在地图的左上角，朝向为右，其坐标(0,0)， 小W的坦克初始位置在地图右下角，朝向为左，坐标为(15,15)。坦克不能移动到地图外，坦克会占领自己所在的格子，己方的坦克不可以进入对方占领过的格子。每一个回合双方必须对自己的坦克下达以下5种指令中的一种:

移动指令U:回合结束后，使己方坦克朝向为上，若上方的格子未被对方占领，则向当前朝向移动一个单位(横坐标-1)，否则保持不动;

移动指令D:回合结束后，使己方坦克朝向为下，若下方的格子未被对方占领，则向当前朝向移动一个单位(横坐标+1)，否则保持不动，

移动指令L:回合结束后，使己方坦克朝向为左,若左侧的格子未被对方占领，则向当前朝向移动一个单位(纵坐标-1) ,否则保持不动;

移动指令R:回合结束后，使己方坦克朝向为右，若右侧的格子未被对方占领，则向当前朝向移动一个单位(纵坐标+1)，否则保持不动;

开火指令F:己方坦克在当前回合立即向当前朝向开火;

己方坦克开火后，当前回合己方坦克的正前方若有对方的坦克，对方的坦克将被摧毁，游戏结束，己方获得胜利;若双方的坦克在同一-回合被摧毁，游戏结束，判定为平局;若双方的坦克在同一回合内进入到同一个未被占领的格子，则双方的坦克发生碰撞，游戏结束，判定为平局;当游戏进行到第256个回合后，游戏结束，若双方坦克均未被摧毁，则占领格子数多的一方获得胜利，若双方占领的格子数一样多，判定为平局。*注意， 若-方开火， 另-方移动，则认为是先开火，后移动。

现在小D和小W各自给出一串长度为256的指令字符串， 请你帮助他们计算出游戏将在多少个回合后结束，以及游戏的结果。