阿里21年4星题_Python

子集

import bisect

T = int(input())
for i in range(T):
    n = int(input())
    l1 = list(map(int, input().split(' ')))
    l2 = list(map(int, input().split(' ')))
    X = list(zip(l1, l2))
    X = sorted(X, key=lambda x: (x[0], -x[1]))
    # 求不降子序列
    s = [0 for i in range(n + 1)]
    total = 0
    for j in range(n):
        t = bisect.bisect_left(a=s, x=X[j][1], lo=0, hi=total)  # 二分插入序列
        if t == total:  # 放在有序序列的最后一个
            total += 1
        s[t] = X[j][1]
    print(total)

小强爱数学

3/10AC...

n = int(input())
res = []
ll = 10 ** 9 + 7
for i in range(n):
    A, B, m = list(map(int, input().split(' ')))
    a, b = 2, A  # f(0) f(1)
    if m == 0:
        print(2)
        continue
    for j in range(2, m + 1):
        c = (A * b % ll - B * a % ll + ll) % ll
        a, b = b, c
    res.append(b)
for r in res:
    print(r)

以下Java代码可以：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        long ll = 1000000007;
        for (int i = 0; i < T; i++) {
            long A = sc.nextInt();
            long B = sc.nextInt();
            int n = sc.nextInt();
            if (n == 0) {
                System.out.println(2);
                continue;
            }
            long a = 2;  //f(0)
            long b = A; //f(1)
            for (int j = 2; j <= n; j++) {
                long c = (A * b % ll - B * a % ll + ll) % ll;
                a = b;
                b = c;
            }
            System.out.println(b);
        }

    }
}

二叉树

n, m = list(map(int, input().split()))
ll = 1000000007
dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]  # i个节点且高度不超过j的个数
for j in range(m):
    dp[0][j] = 1  # 空树
for i in range(1, n + 1):
    for j in range(1, m + 1):
        for k in range(0, i):  # 左子树节点数, 不超过i-1个节点
            dp[i][j] = (dp[i][j] + dp[k][j - 1] * dp[i - 1 - k][j - 1]) % ll
print(dp[n][m])

对称飞行器

from collections import deque


def dfs(matrix, sx, sy, ex, ey):
    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    q = deque()
    q.append((sx, sy, 5, 0))  # 剩余飞行步数, 步数
    matrix[sx][sy] = '#'
    while len(q) > 0:
        x, y, c, s = q.popleft()
        if x == ex and y == ey:
            return s
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == '.':
                q.append((nx, ny, c, s + 1))
                matrix[nx][ny] = '#'

        nx, ny = n - 1 - x, m - 1 - y
        if c >= 1 and matrix[nx][ny] == '.':
            q.append((nx, ny, c - 1, s + 1))
            matrix[nx][ny] = '#'
    return -1


sx, sy, ex, ey = 0, 0, 0, 0
n, m = list(map(int, input().split()))
matrix = []
for i in range(n):
    l = list(input())
    if 'S' in l:  # 起点坐标
        sx, sy = i, l.index('S')
    if 'E' in l:
        ex, ey = i, l.index('E')  # 终点坐标
    matrix.append(l)
matrix[ex][ey] = '.'
print(dfs(matrix, sx, sy, ex, ey))

知识竞赛

n = int(input())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split(' '))))
res = 0
ab.sort(key=lambda x: abs(x[0] - x[1]))
max_a = ab[0][0]
max_b = ab[0][1]
for a, b in ab:
    if a > b:
        res = max((max_b + b) / 2, res)
    else:
        res = max((max_a + a)/2, res)
    if a > max_a:
        max_a = a
    if b > max_b:
        max_b = b
print(res)

树上最短链

def dfs(u, fa, root, depth):  # 当前节点、上一个访问的节点、根节点、深度
    global w
    if w[u] == w[root] and u != root:  # 找到等级一样的其他节点
        global ans
        ans = min(ans, depth)

    for v in g[u]:
        if v == fa:
            continue
        dfs(v, u, root, depth + 1)


n = int(input())
w = list(map(int, input().split()))
g = [[] for _ in range(n)]
for i in range(n - 1):
    u, v = list(map(int, input().split()))
    g[u - 1].append(v - 1)
    g[v - 1].append(u - 1)  # 邻接表, 下标从0开始
ans = 10000
for i in range(n):
    dfs(i, -1, i, 0)
print(ans)

Python 4/10 AC, PyPy 6/10AC, 由C++改写过来，理论上复杂度应该是0(n^2)...

7. 牛牛吃糖果

n, m = list(map(int, input().split()))
weights = list(map(int, input().split()))  # 吃糖数
weights.insert(0, 0)
profits = [1 for _ in range(n)]
profits.insert(0, 0)
k = int(input())
for i in range(k):
    j1, j2 = list(map(int, input().split()))
    # 将约定的牛牛绑定在一起
    weights[j1] += weights[j2]
    profits[j1] += 1
    profits[j2] = 0
    weights[j2] = 0
# 二维dp只能9/10AC...
dp = [0 for _ in range(m + 1)]  # dp[i][j]表示前i个牛牛吃j个糖果
for i in range(1, n + 1):
    for j in range(m, weights[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - weights[i]] + profits[i])  # 让吃和不让吃
print(dp[m])

方案数量

T = int(input())
for t in range(T):
    n, m = list(map(int, input().split()))
    matrix = []
    for i in range(n):
        matrix.append(list(map(int, input().split())))
    dp = [[0 for _ in range(m)] for _ in range(n)]
    dp[0][0] = 1  # 从[0,0]到[0,0]的方案数目
    for i in range(n):
        for j in range(m):
            e = matrix[i][j]
            for dx in range(e + 1):
                for dy in range(e + 1 - dx):
                    if dx == dy == 0:
                        continue
                    nx, ny = dx + i, dy + j
                    if nx < n and ny < m:
                        dp[nx][ny] = (dp[i][j] + dp[nx][ny]) % 10000
    print(dp[n - 1][m - 1])

合法连续子段

from collections import defaultdict

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 0
d = defaultdict(int)
l, r = 0, 0  # [l,r]
while r < n:
    d[a[r]] += 1
    while l <= r and d[a[r]] >= m: # 先找到刚好只有一个最大重复为m的所有区间。每个区间求向后的区间数
        ans += n - r
        d[a[l]] -= 1   
        l += 1 # 移动左指针
    r += 1  # 右指针
print(ans)

两个序列

_ = input()
a, b = list(input().split(' ')), list(input().split(' '))
_m = dict()
for i in range(len(b)):
    _m[b[i]] = i
for i in range(len(a)):
    a[i] = [_m[a[i]]]
ans, cnt = 1, 1
for i in range(1, len(a)):   # 不降连续序列
    if a[i] > a[i - 1]:
        cnt += 1
        ans = max(cnt, ans)
    else:
        cnt = 1
print(len(a) - ans)