美团 4.18 笔试真题 - 算法岗

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))
    # 按 (值, 下标) 排序，前 m 个标记为删除
    indices = sorted(range(n), key=lambda i: (arr[i], i))
    removed = [False] * n
    for i in range(m):
        removed[indices[i]] = True
    result = [str(arr[i]) for i in range(n) if not removed[i]]
    print(' '.join(result))

T = int(input())
for _ in range(T):
    solve()

import json
import numpy as np

line = input()
data = json.loads(line)

train_raw = data["train"]
test_raw = data["test"]

# 解析训练数据：每行最后一个是标签 y
train_arr = np.array(train_raw, dtype=np.float64)
X_train = train_arr[:, :-1]
y = train_arr[:, -1]

X_test = np.array(test_raw, dtype=np.float64)

# 超参数
l = 1.0
sigma_f2 = 1.0
sigma_n2 = 0.1

# RBF 核函数（向量化）
def rbf_kernel(A, B):
    # A: (m, d), B: (n, d) -> K: (m, n)
    sq_A = np.sum(A ** 2, axis=1, keepdims=True)  # (m, 1)
    sq_B = np.sum(B ** 2, axis=1, keepdims=True)  # (n, 1)
    dist_sq = sq_A + sq_B.T - 2.0 * A @ B.T      # (m, n)
    return sigma_f2 * np.exp(-dist_sq / (2.0 * l ** 2))

# 训练点之间的核矩阵 + 噪声
n_train = X_train.shape[0]
K = rbf_kernel(X_train, X_train) + sigma_n2 * np.eye(n_train)

# 求解 alpha = K^{-1} y
alpha = np.linalg.solve(K, y)

# 测试点与训练点的核向量
K_star = rbf_kernel(X_test, X_train)  # (n_test, n_train)

# 预测均值
y_pred = K_star @ alpha

# 输出
result = [round(float(v), 6) for v in y_pred]
print(json.dumps(result))

import sys
from collections import defaultdict
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    def decompose(x):
        """分离奇数因子和 2 的幂次"""
        k = 0
        while x % 2 == 0:
            x //= 2
            k += 1
        return x, k  # (奇数因子, 2的幂次)

    # 按奇数因子分组
    groups_a = defaultdict(list)
    groups_b = defaultdict(list)
    for x in a:
        odd, pw = decompose(x)
        groups_a[odd].append(pw)
    for x in b:
        odd, pw = decompose(x)
        groups_b[odd].append(pw)

    # 检查分组是否对应
    if set(groups_a.keys()) != set(groups_b.keys()):
        print(-1)
        return
    for key in groups_a:
        if len(groups_a[key]) != len(groups_b[key]):
            print(-1)
            return

    total_ops = 0
    for odd_part in groups_a:
        pa = sorted(groups_a[odd_part])
        pb = sorted(groups_b[odd_part])
        # 一一配对：最小对最小
        # 收集所有需要经过的层
        layers = set()
        for ka, kb in zip(pa, pb):
            if kb < ka:
                print(-1)
                return
            for t in range(ka, kb):
                layers.add(t)
        total_ops += len(layers)

    print(total_ops)

T = int(input())
for _ in range(T):
    solve()

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))

    # pos_q[v] = v 在 q 中的位置 (0-indexed)
    pos_q = [0] * (n + 1)
    for i, v in enumerate(q):
        pos_q[v] = i

    # pos_p[v] = v 在 p 中的位置 (0-indexed)
    pos_p = [0] * (n + 1)
    for i, v in enumerate(p):
        pos_p[v] = i

    # c[i] = pos_q[p[i]]，LCS(p,q) 等价于 c 的 LIS
    c = [pos_q[p[i]] for i in range(n)]

    # 树状数组（后缀最大值）：翻转索引实现 "查询值域 >= x 的最大值"
    bit = [0] * (n + 2)

    def bit_update(x, val):
        x = n - x
        while x <= n:
            if bit[x] < val:
                bit[x] = val
            x += x & (-x)

    def bit_query(x):
        """查询值域 >= x 的最大 LIS 长度"""
        x = n - x
        res = 0
        while x > 0:
            if bit[x] > res:
                res = bit[x]
            x -= x & (-x)
        return res

    # 从右到左计算 lis_from[i]：以 c[i] 开头的 LIS 长度
    lis_from = [0] * n
    for i in range(n - 1, -1, -1):
        cv = c[i] + 1  # 映射到 1-indexed
        best = bit_query(cv + 1)  # 严格大于 c[i] 的后缀最大值
        lis_from[i] = best + 1
        bit_update(cv, lis_from[i])

    L = max(lis_from)  # LCS 长度

    # 贪心构造：从大到小扫描值 v
    # 关键观察：lis_from[pos_p[v]] 计算的是以 c[pos_p[v]] 开头的 LIS 长度，
    # 后续元素的 c 值都严格大于 c[pos_p[v]] = pos_q[v] > iq_bound，
    # 因此 iq_bound 的约束被自动满足，无需额外数据结构。
    result = []
    remain = L
    ip_bound = -1
    iq_bound = -1

    for v in range(n, 0, -1):
        if remain == 0:
            break
        pi = pos_p[v]
        qi = pos_q[v]
        if pi > ip_bound and qi > iq_bound and lis_from[pi] >= remain:
            result.append(v)
            remain -= 1
            ip_bound = pi
            iq_bound = qi

    print(' '.join(map(str, result)))

solve()