奇安信8.01笔试记录

20道单选，10道多选，2道编程，全程2小时。

• 选择题涉及的内容较多，对计算机网络和操作系统的内容还需要好好复习。

• 编程题 难度尚可

1. 物资价值计算

大概的题目：给定总的预算，然后之后给n个物品的价格和价值，求出价值最高的购买方案。

个人感觉这种题有点像n-背包问题，但是缺少对重量的考察，所以整体可是比较简单的。

• 根据money数来计算，因为用动态规划需要开数组比较麻烦，笔者使用了带memo的递归，使用dict来存储会计算到的那些预算值。

• 转移方程就是根据当前预算以及所有的价格，如果预算大于该价格就尝试购买并计算之后的价值

f(money) = max(f(money-price)+value,f(money)) ,遍历所有price,value对

• basecase ：当money数小于任何的price时为0

from collections import defaultdict

def recur(money,values,memo):
    min_price = min([p for p,w in values])
    if money < min_price:
        memo[money] = 0
    if money in memo.keys():
        return memo[money]
    else:
        for p,w in values:
            if money >= p:
                memo[money] = max(recur(money-p,values,memo)+w,memo[money])
    return memo[money]

money = int(input())
N = int(input())

values = []
for _ in range(N):
    [p,w] = map(int,input().split())
    values.append([p,w])

memo =defaultdict(int)
res = recur(money,values,memo)
print(res)

2.亲7数

大致问题是：给定一些个位数如[1,1,2,0]这种，计算完全使用这些数字构成的数能整除7的个数

问题不难，但是有几个小坑在这里记录下：

• 相同值的数字互相交换也算一种：如112这种，其实是2种情况，所以笔者的做法是根据每个元素出现的次数计算了其阶乘(即排列数)的乘积。

• 如果有0的话，0是可以出现在第一位的

• 具体的实现方式：就是先计算每个元素出现次数dict，然后通过这个dict回溯计算可能的种类，之后再乘以之前提到的阶乘的乘积。

from collections import defaultdict

def calc_multip(x):
    res = 1
    for i in range(1,x+1):
        res *= i
    return res

class Solution:
    def __init__(self):
        self.res = 0
        self.digit_conut = defaultdict(int)

    def reletive_7(self, digit):
        for val in digit:
            self.digit_conut[val] += 1
        self.orig_digit_cnt = self.digit_conut.copy()

        for key,val in self.digit_conut.items():
            if val > 0:
                self.digit_conut[key] -= 1
                self.solver(str(key))
                self.digit_conut[key] += 1

        cnt = 1
        for key,val in self.orig_digit_cnt.items():
            cnt *= calc_multip(val)
        return self.res * cnt

    def solver(self,val_str):
        if sum(self.digit_conut.values()) == 0:
            if int(val_str) % 7 == 0:
                self.res+=1
            return
        for key,val in self.digit_conut.items():
            if val > 0:
                self.digit_conut[key] -= 1
                self.solver(val_str+str(key))
                self.digit_conut[key] += 1

a = Solution()
print(a.reletive_7([1,1,2,0,0,0]))