灵犀互娱笔试思路分享

20道选择，5道编程，2道游戏调研，编程不让用本地编译器。时间很长：可以做三个小时

第四题：

题目：玩家走迷宫，可以向上向右向下走，起点（0，0），终点（m-1, n-1)，每个格子一个分数，不能走已经走过的格子，求最大得分（注意：走到上下边缘的时候，可以自动重置分数，向贪吃蛇一样从迷宫另一边出来）。数据范围给的比较宽松，行列都是100。

这个题有个坑，前面说M*N，后面输入的时候又是N行M列，让人搞不清上下是在M上还是在N上。提交的时候要是因为这个不过，可以把MN的输入顺序调换一下。

思路：

dp：定义dp[m][n][3]. dp[i][j][k]表示，通过k方向（k=0:上，1：下，2：右）走到（i，j）的最大得分。

一列一列去遍历.

递推公式如下：

dp[i][j][2] = max({dp[i][j - 1][0] + w[i][j],
                   dp[i][j - 1][1] + w[i][j],
                   dp[i][j - 1][2] + w[i][j]});
dp[i][j][1] = max({dp[i - 1][j][1] + w[i][j],
                   dp[i - 1][j][2] + w[i][j]});
dp[i][j][0] = max({dp[i - 1][j][0] + w[i][j],
                   dp[i - 1][j][2] + w[i][j]});

然后记得处理一下边界情况，就可以了，复杂度O(m*n*3)。

第五题：

两个字符串 a，b。可以对a进行两种操作：1、把a的某些小写字母变成大写；2、把a的某些小写字母删掉

问，通过这两操作能不能a变成b.

q组数据，每组的a长度(n)和b长度(m)不大于1000。q不大于10

可以采用O(q*n*m)的方法

思路：

还是dp，dp[i][j]表示：【a的前i个字符的子串】是否可以 通过这两种操作转换成【b的前j个字符的子串】

这个比较简单，递推公式如下：

if (dp[i - 1][j] == 1 && islower(a[i - 1])) dp[i][j] = 1;
if (dp[i - 1][j - 1] == 1 && a[i - 1] == b[j - 1]) dp[i][j] = 1;
if (dp[i - 1][j - 1] == 1 && (
	islower(a[i - 1]) && isupper(b[j - 1]) && (a[i - 1] - 'a' + 'A' == b[j - 1]) 
  )) dp[i][j] = 1;