友塔游戏 校招 笔试真题

6.3开

7.5boss投 游戏服务端开发

7.13 笔试

一周内完成

牛客 2h

编程x4（从题库中抽）（dfs 15 66.7%、dfs 20 90%、树dp 30 20%、数字位处理 35 不难但没时间）

1. 有一个消除类游戏，游戏场景是一个最大9x9范围的方形棋盘，棋盘上的每一个格子可能有一个棋子。每一个格子上的棋子有颜色和分数两个属性。当点击棋盘上任意一个棋子时，会触发一次消除，消除范围是被点击的棋子和四周相同连续颜色的棋子。消除获得的分数等于被消除棋子数量和被消除棋子中最大分数的乘积。现在给定一个棋盘，求可能得到的最大消除分数。1输入描述 第0行：棋盘宽度n 第1-n行：母个棋子颜色ci,cj 第nt1-2n行：每个棋了分数s_i,s」 1输出描述 最大消除分数
2. 夏天到了，爱吃冰淇淋的小X自己制造了一台冰淇淋机器，但因为一些原因他的机器会产生不规则的冰淇淋，他需要收集一些数据来优化这个机器，所以他需要你的帮助这个机器可以产生如下形状的冰淇淋：冰淇淋的形状是一个N*N(1<=N<=1000)的方块其中“"”代表空白，“#”代表一块1*1的方块冰淇淋。因为机器的问题，所以会产生多个断开的冰淇淋团，如果一个冰淇淋块的东、南、西、北四个方向有另一个冰淇淋块，则我们认为这两个冰淇淋块属于同一个冰淇淋团。现在小X想要找到面积最大的冰淇淋团和他对应的周长。比如上面这个例子，就存在两个冰淇淋团，第一个冰淇淋团由第一行的两个冰淇淋块组成，他们的面积是2，周长是6。第二个冰淇淋团是由剩下的冰淇淋块组成，他们的面积是13，周长是22。所以小X希望得到的数据就是13和22.需要注意的是，如果冰淇淋团中间存在空白区域，则空白区域的周长也应记入冰淇淋团的周长中，例如下图，则环形冰淇淋的内周长也要算入冰淇淋团的周长中
3. 探险家发现了一个各个洞穴相连的矿脉地区。经过仔细探查，探险家发现，矿脉地区的结构类似于一棵二叉树，经过勘测，得出了每个节点的矿脉的价值量，但是如果开采所有矿脉，则洞穴会坍塌，需要留下一些矿脉节点作为支撑，现在限制可开采的节点的相连个数不能超过k个，问最多能开采多少价值量的矿石？
4. 玩家操纵角色与恶龙交战，恶龙发动龙之咆哮预计将对玩家造成m点伤害。由于伤害太高，玩家一看大事不妙连忙加入了月影宗打开了数值修改器，希望通过删除伤害中的一些数字使得自己不被恶龙秒杀。由于害怕反作弊系统的制裁，玩家只能删除最多位数字。当然你希望最后受到的伤害最小。

挂了