8.30 文远知行笔试 AC3 题解PythonCpp

占个坑，等结束发题解。

另外求算法岗内推，救救孩子。

第一题

动态规划，可以压到1维。
按照代价值来做DP，同时记录收益值，当代价值相同的时候取收益最大的那个。

"""
3 4
1 6 3  20
8 4 2 2
1 1 3 1
1 2 2 2
2 2 2 2
2 3 2 2
"""


def solve(row, col, costs, values):
    dp1 = [0] * col
    dp2 = [0] * col
    for j in range(col):
        if j == 0:
            dp1[j] = costs[0][j]
            dp2[j] = values[0][j]
            continue
        dp1[j] = dp1[j - 1] + costs[0][j]
        dp2[j] = dp2[j - 1] + values[0][j]
    for i in range(1, row):
        cdp1 = [0] * col
        cdp2 = [0] * col
        for j in range(col):
            if j == 0:
                cdp1[j] = costs[i][j] + dp1[j]
                cdp2[j] = values[i][j] + dp2[j]
                continue
            if cdp1[j - 1] < dp1[j]:
                cdp1[j] = cdp1[j - 1] + costs[i][j]
                cdp2[j] = cdp2[j - 1] + values[i][j]
            elif cdp1[j - 1] > dp1[j]:
                cdp1[j] = dp1[j] + costs[i][j]
                cdp2[j] = dp2[j] + values[i][j]
            else:
                cdp1[j] = cdp1[j - 1] + costs[i][j]
                cdp2[j] = values[i][j] + max(cdp2[j - 1], dp2[j])
        dp1 = cdp1[:]
        dp2 = cdp2[:]
    print("{} {}".format(dp1[-1], dp2[-1]))


if __name__ == '__main__':
    row, col = map(int, input().split())
    costs = []
    values = []
    for i in range(row):
        costs.append(list(map(int, input().split())))
    for i in range(row):
        values.append(list(map(int, input().split())))
    solve(row, col, costs, values)

第二题

禁用了Python，题目的大意是制定一个字母，然后指定次数和每次变换跳的步数，求最终字母编程多少。 给的次数和每次跳的步数范围很大。利用：
防止溢出就可以。 c++ 字符操作不太会写，用的强制类型转换。

#include <iostream>
using namespace std;
int main(){
    int MOD= 26;
    int _;
    cin >> _;
    for(int i =0; i < _; ++i){
        char a;
        long long int n, k;
        cin >> a >> n >> k;
        long long int ret = ((n % MOD) * (k % MOD)) % MOD;
        long long int out = ret + a;
        if(out > 'z'){
            out = out - 'z' + 'a' - 1;
        }
        cout << char(out) << endl;
    }
}

第三题

BFS。N个点 N-1个边，因此是一棵树，直接BFS就可以

from collections import defaultdict, deque
def solve(N, Q, graph, samples):
    def bfs(s, e, c):
        que = deque()
        que.append([s, 0])
        visited = set()
        visited.add(s)
        while que:
            node, cnt = que.popleft()
            for _node in graph[node]:
                if _node not in visited:
                    visited.add(_node)
                    distance = graph[node][_node]
                    times = distance // c
                    ccnt = cnt
                    if times == 0:
                        ccnt = cnt + 1
                    elif times * c == distance:
                        ccnt = cnt + times
                    else:
                        ccnt = cnt + times + 1
                    if _node == e:
                        return ccnt + 1
                    que.append([_node, ccnt])

    for [s, e, c] in samples:
        ret = bfs(s, e, c)
        print(ret)


if __name__ == '__main__':
    N, Q = map(int, input().split())
    graph = defaultdict(dict)
    for i in range(N - 1):
        u, v, d = map(int, input().split())
        graph[u][v] = d
        graph[v][u] = d
    samples = []
    for i in range(Q):
        samples.append(list(map(int, input().split())))
    solve(N, Q, graph, samples)