阿里21年2星题_Python

完美对

也即是a_{i+1}-a_{i}=-(b_{i+1}-b_{i}.

from collections import defaultdict

n, k = list(map(int, input().split(' ')))
d = defaultdict(lambda: 0)
ans = 0
for i in range(n):
  a = list(map(int, input().split(' ')))
  t = tuple((a[i] - a[i - 1] for i in range(1, k)))  # 差分序列做Key
  ans += d[t]  # 实际上查的是相反序列
  t2 = tuple((-i for i in t))
  d[t2] += 1  # 相反序列+1
print(ans)

选择物品

个人理解为排列数, 52/55AC, 超时...

m, n = list(map(int, input().split(' ')))
vis = [False for _ in range(0, m + 1)]
nums = [0 for _ in range(n)]

all_res = set()


def dfs(index):
    if index == n:
        if str(sorted(nums)) not in all_res:
            all_res.add(str(sorted(nums)))
            print(*nums, sep=' ')
        return
    for i in range(1, m + 1):
        if not vis[i]:
            vis[i] = True
            nums[index] = i
            dfs(index + 1)
            vis[i] = False


dfs(0)

小强去春游

这一题Python完全不能AC, 但是相同逻辑的Java代码可以，下面附上。

T = int(input())
for i in range(T):
    n = int(input())
    weights = list(map(int, input().split()))
    weights.sort()
    ans = 0
    while n >= 4:
        p1 = weights[0] * 2 + weights[-2] + weights[-1]  # 最轻地带两个最重的
        p2 = weights[0] + weights[1] * 2 + weights[-1]  # 最轻和次轻过去, 然后两个重的, 最轻和次轻都要回来
        ans += min(p1, p2)
        n -= 2
    if n == 3:
        ans += sum(weights[:3])
    if n == 2:
        ans += weights[1]
    if n == 1:
        ans += weights[0]
    print(ans)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            int[] weights = new int[n];
            for (int j = 0; j < n; j++) weights[j] = sc.nextInt();
            Arrays.sort(weights);
            int ans = 0;
            while (n >= 4) {
                int p1 = weights[0] * 2 + weights[n - 2] + weights[n - 1];    // 最轻的依次带两个最重的
                int p2 = weights[0] + weights[1] * 2 + weights[n - 1];    //两个最轻的也过去
                ans += Math.min(p1, p2);
                n -= 2;
            }
            if (n == 3) ans += weights[0] + weights[1] + weights[2];
            if (n == 2) ans += weights[1];
            if (n == 1) ans += weights[0];
            System.out.println(ans);
        }

    }
}

比例问题

这道题好像是Python超时...

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong();
        long B = sc.nextLong();
        long a = sc.nextLong();
        long b = sc.nextLong();
        // 求最大公约数
        long c = gcd(a, b);
        a /= c;
        b /= c;
        long x, y;
        x = y = 0;
        while (x + a <= A && y + b <= B) {
            x += a;
            y += b;
        }
        System.out.printf("%d %d", x, y);
    }

    public static long gcd(long a, long b) {
        long c = 0;
        while (b != 0) {
            c = a % b;
            a = b;
            b = c;
        }
        return a;
    }
}

小强修水渠

n = int(input())
points = [0 for _ in range(n)]
for i in range(n):
    x, _ = list(map(int, input().split(' ')))
    points[i] = x
points.sort()  # 排序后, 两边相减, 多余的奇数不算
if n % 2 == 0:
    mid = n // 2
    print(sum(points[mid:]) - sum(points[:mid]))
else:
    mid = n // 2
    print(sum(points[mid + 1:]) - sum(points[:mid]))

国际交流会

n = int(input())
points = list(map(int, input().split()))
points.sort()
low, high = 0, len(points) - 1
res = []
while low < high:
    res.append(points[low])   # 一次将最大和最小放入
    res.append(points[high])
    low += 1
    high -= 1
if low == high:  # 奇数长
    res.append(points[low])
ans = 0
for i in range(0, n):
    ans += abs(res[i] - res[i - 1])
print(ans)
print(*res, sep=' ')

小强的神奇矩阵

n = int(input())
arr = []
for i in range(3):
    arr.append(list(map(int, input().split(' '))))
dp = [[0 for _ in range(n)] for _ in range(3)]

for j in range(1, n):
    for i in range(3):
        d1 = abs(arr[i][j] - arr[0][j - 1]) + dp[0][j - 1]  # 当前列与前一列相比, 分别三行
        d2 = abs(arr[i][j] - arr[1][j - 1]) + dp[1][j - 1]
        d3 = abs(arr[i][j] - arr[2][j - 1]) + dp[2][j - 1]
        dp[i][j] = min(d1, d2, d3)
res = []
for i in range(3):
    res.append(dp[i][-1])
print(min(res))

蚂蚁森林之王

n = int(input())
votes = [1 for i in range(n + 1)]
choices = list(map(int, input().split()))
choices.insert(0, 0)
for i in range(n, 0, -1):
    if choices[i] != 0:
        votes[choices[i]] += votes[i]  # 将所有票投给偶像, 动态规划
print(*votes[1:], sep='\n')

另一个不完全90%AC的代码：超时

n = int(input())
votes = [1 for i in range(n + 1)]
choices = list(map(int, input().split()))
choices.insert(0, 0)
for i in range(n, 0, -1):
    c = choices[i]
    while c != 0:
        votes[c] += 1  # 类似于并查集，其偶像的偶像...都要+1
        c = choices[c]
print(*votes[1:], sep='\n')

删除字符

6/15AC, 个人感觉这个解法不错...

T = int(input())


def method(s, n, m, chars):
    m = min(n, m)
    if m == 0:
        print(chars + s)
        return
    # 最小字符
    index = 0
    for i in range(0, m + 1):  # 在前m+1个字符中选择最小的
        if s[index] > s[i]:
            index = i
    chars += s[index]  # 前m+1个字符
    method(s[index + 1:], n - index - 1, m - index, chars)  # 去掉删掉的部分


for i in range(T):
    n, m = list(map(int, input().split()))
    s = input()
    chars = ''
    method(s, n, m, chars)

视力表

8/10AC...

def comb(n, m, ll):
    ans = 1
    for i in range(1, m + 1):
        ans = ans * (n - m + i) / i
    return ans % ll


ll = 998244353
N, *l = list(map(int, input().split(' ')))
l.sort()
a, b, c, d = l
print(int((comb(N * N, a, ll) * comb(N * N - a, b, ll) * comb(N * N - a - b, c, ll)) % ll))

暴力解法能全部通过: from math import factorial.