2020-09-25 0bf1681b56bba9764317662acfa0e745 99+ 6 分钟 0.9 k

【AK题解】搜狗2021校招【研究】笔试（第二场）

第一题

汪汪做完有N道单选题题的试卷后，跟朋友对答案，已知朋友对了K题，求汪汪最多和最少做对多少题。

只需要知道两人相同的答案有哪些，因为题目是相同的，只需一次遍历即可。
得到相同答案个数之后，分情况讨论：

1）最少：汪汪跟朋友一样的答案和朋友所有做错的题目成包含关系，不一样的答案可以两人都错。于是只需排除汪汪被强行做对的题目即可（有可能没有），即 $\max(0, m - (n-k))$。

2）最多：汪汪跟朋友一样的答案和朋友做对的答案成包含关系，其余一样的必须为错，即 $\max(m, k)$中有 $\min(m, k)$为正确的，剩余的 $n - \max(m, k)$ 可以全部做对。

后台坑：Interval的注释必须去掉

class Interval:
    def __init__(self, a=0, b=0):
        self.start = a
        self.end = b

class Solution:
    def solve(self , n , k , str1 , str2 ):
        m = 0
        for i in range(n):
            m += (str1[i] == str2[i])
        return Interval(a = max(0, m - (n - k)), 
                        b = min(m, k) + n - max(m, k))


sol = Solution()
ret = sol.solve(3, 1, "ABC", "CCC")
print(ret.start, ret.end)

第二题

考察矩阵旋转

两张格子纸，一张是透明的，每个格子黑色或白色；另一张对应的每个格子都包含一个字符。解码信息时，重叠两张格子纸，按从上到下，从左到右的顺序提取白色方格对应的字符。连续顺时针旋转90度，读取四个角度下的解码信息。

class Solution:
    def rotate(self, s, N):
        i0, i1 = 0, N-1
        while i0 < i1:
            s[i0], s[i1] = s[i1], s[i0]
            i0, i1 = i0 + 1, i1 - 1
        
        for i in range(N):
            for j in range(i+1, N):
                s[i][j], s[j][i] = s[j][i], s[i][j]
        return s

    def rotatePassword(self , s1 , s2 ):
        s1 = list(map(list, s1))
        s2 = list(map(list, s2))
        
        N = len(s1)

        res = []

        for i in range(N):
            for j in range(N):
                if s1[i][j] == '0':
                    res.append(s2[i][j])
        self.rotate(s1, N)
        
        for i in range(N):
            for j in range(N):
                if s1[i][j] == '0':
                    res.append(s2[i][j])
        self.rotate(s1, N)

        for i in range(N):
            for j in range(N):
                if s1[i][j] == '0':
                    res.append(s2[i][j])
        self.rotate(s1, N)

        for i in range(N):
            for j in range(N):
                if s1[i][j] == '0':
                    res.append(s2[i][j])
        
        return ''.join(res)

s1 = ["1101","1010","1111","1110"]
s2 = ["ABCD","EFGH","IJKL","MNPQ"]
sol = Solution()
ret = sol.rotatePassword(s1, s2)
print(ret)

第三题

Nim游戏

甲和乙玩取石子游戏，开始有N个石子，双方每次可以拿1-3个，每次取完石子后裁判等概率取掉0或1个石子，最后不能取石子的一方算输。假定甲和乙都取最优决策，求甲的胜率。

实际上这是一个minimax game，每次一方取完石子，问题都会归约到一个更小规模的问题上，并且在归约的同时有0.5概率变成另一个状态（少一个石子）。

考虑到每次取完石子后，裁判都有相同操作，因此甲和乙的状态是等价的。因此乙的最优决策步骤可以隐藏在子状态 ${\tt dp}(i-k)$ 和 ${\tt dp}(i-k-1)$ 中。同时，乙的败率就是甲的胜率，所以有：

$dp(i)=\max_{k\in(1,2,3)}0.5\times(1-dp(i-k))+0.5\times(1-dp(i-k-1))$

于是动态规划。

class Solution:
    def calcProb(self , n ):
        if n <= 3: return 1
        
        dp = [0 for _ in range(n+1)]
        dp[1] = 1; dp[2] = 1; dp[3] = 1
        
        for i in range(4, n+1):
            for k in (1,2,3):
                val = (0.5 * (1 - dp[i-k]) + 0.5 * (1 - dp[i-k-1]))
                dp[i] = max(dp[i], val)
        
        return dp[n]