大厂真题 / 上海AILab

上海AILab 5.16 笔试真题 - 通用岗

本场考试概述

考试时间：2026年5月16日 考试岗位：通用 难度评级：中等

考点分析：

第一题：井字棋模拟（难度简单）
第二题：排序贪心 + 前缀和（难度中等）
第三题：数论 + 质因数分解 + 计数原理（难度中等）

建议策略：

第一题是纯模拟题，按落子顺序维护棋盘状态并逐步检查违规和胜负即可，优先稳拿满分
第二题核心洞察是”每轮存活前一半”——排序后用前缀和累加即可
第三题将 $\text{lcm}(a, b) = x$ 转化为每个质因数上的指数约束，再用乘法原理计数

第一题：井字棋

题目描述

在一个 $3 \times 3$ 的棋盘上，两位玩家依次下子，先手执 “X”，后手执 “O”。棋盘格子用行坐标 $x$ 和列坐标 $y$ 表示，均从 $1$ 开始编号。给出完整的落子过程，判断这盘棋的最终结果：

若存在不合法操作（包括在一方胜利后仍继续落子，或下在已有棋子的位置），输出 $-1$
若先手获胜（形成三子连线），输出 $0$
若后手获胜，输出 $1$
若处理完所有落子后无人获胜且不存在不合法操作，输出 $2$

第一行输入整数 $T$ 表示测试组数。每组第一行输入 $n$ 表示总落子次数，接下来 $n$ 行每行输入 $x, y$ 表示落子位置。奇数步为先手下 “X”，偶数步为后手下 “O”。

样例

输入

输出

思路分析

第一步：明确需要维护的状态

这是一道模拟题，核心在于按照游戏规则逐步执行并检测两类违规：

重叠落子：目标格已有棋子
胜后继续：有人已经赢了还在落子

同时还需要在每次合法落子后检查是否产生了胜者。

第二步：高效的胜负判定

$3 \times 3$ 棋盘上，三子连线只可能出现在 8 条线上（3行 + 3列 + 2对角线）。但每次落子只需要检查经过该点的线（最多4条），不需要遍历全部8条。

第三步：处理优先级

违规优先于胜负：如果整个过程中出现了任何违规操作，不管有没有人赢，都输出 $-1$。一旦检测到违规就标记，但仍需继续消耗剩余输入。

题解代码

import sys
input = sys.stdin.readline

def solve():
    T = int(input())
    for _ in range(T):
        n = int(input())
        board = [['.'] * 3 for _ in range(3)]
        illegal = False
        won = False
        winner = '.'
        for i in range(n):
            x, y = map(int, input().split())
            if illegal:
                continue
            if won:
                illegal = True
                continue
            r, c = x - 1, y - 1
            if board[r][c] != '.':
                illegal = True
                continue
            p = 'X' if i % 2 == 0 else 'O'
            board[r][c] = p
            # 检查经过 (r, c) 的行、列、对角线
            if (board[r][0] == board[r][1] == board[r][2] == p or
                board[0][c] == board[1][c] == board[2][c] == p or
                (r == c and board[0][0] == board[1][1] == board[2][2] == p) or
                (r + c == 2 and board[0][2] == board[1][1] == board[2][0] == p)):
                won = True
                winner = p
        if illegal:
            print(-1)
        elif won:
            print(0 if winner == 'X' else 1)
        else:
            print(2)

solve()

复杂度分析

时间复杂度：$O(T \cdot n)$，每步落子检查常数条线，单组 $O(n)$ 空间复杂度：$O(1)$，仅维护一个 $3 \times 3$ 棋盘

第二题：单败淘汰赛

题目描述

你要举办一场单败淘汰赛，共有 $n$ 支队伍，第 $i$ 支队伍的能力值为 $a_i$，保证任意两队能力值不同。

比赛按轮进行：每一轮，若剩余队伍为偶数，将它们两两配对；若为奇数，任选一支轮空直接晋级，其余两两配对。你可以自由安排配对方式及每场对决的胜负。

定义某一轮的观赏值为”该轮开始时仍在赛场的所有队伍的能力值总和”。当场上只剩 $1$ 支队伍时比赛结束（该轮不计入观赏值）。

请你安排策略使得所有轮次观赏值之和最大，输出这个最大值。

每个测试文件包含 $T$ 组数据。每组第一行输入 $n$，第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

样例

输入

输出

0
10
29

思路分析

第一步：分析淘汰节奏

每轮有 $m$ 支队伍参赛，结束后存活 $\lceil m/2 \rceil$ 支。无论 $m$ 是奇是偶，下一轮队伍数都是 $\lceil m/2 \rceil$。

第二步：贪心策略——让强队留得更久

每轮观赏值 = 当前存活队伍的能力总和。要让总和最大，就应该让能力值大的队伍尽可能多出现在每一轮中。

关键洞察：我们可以自由安排配对和胜负，所以每轮可以让任意队伍被淘汰。最优策略是每轮淘汰能力值最小的那些队伍，即第 $k$ 轮的存活集合恰好是能力值前 $\lceil m/2 \rceil$ 大的队伍。

第三步：前缀和累加

将能力值降序排序，令 $\text{cum}[k]$ 表示前 $k$ 大能力之和。每轮存活 $m$ 支队伍时该轮观赏值为 $\text{cum}[m]$，然后 $m \leftarrow \lceil m/2 \rceil$，循环直到 $m = 1$。

验证样例：$n=4$，排序后 $[8, 5, 2, 1]$，$\text{cum} = [0, 8, 13, 15, 16]$。

$m=4$：观赏值 $\text{cum}[4] = 16$，$m \leftarrow 2$
$m=2$：观赏值 $\text{cum}[2] = 13$，$m \leftarrow 1$
总和 $= 16 + 13 = 29$

题解代码

import sys
input = sys.stdin.readline

def solve():
    T = int(input())
    for _ in range(T):
        n = int(input())
        a = list(map(int, input().split()))
        a.sort(reverse=True)
        # cum[k] = 能力值前 k 大之和
        cum = [0] * (n + 1)
        for i in range(n):
            cum[i + 1] = cum[i] + a[i]
        ans = 0
        m = n
        while m > 1:
            ans += cum[m]
            m = (m + 1) // 2
        print(ans)

solve()

复杂度分析

时间复杂度：$O(n \log n)$，瓶颈在排序，累加只需 $O(\log n)$ 轮 空间复杂度：$O(n)$，前缀和数组

第三题：lcm计数

题目描述

给定两个正整数 $x$ 与 $a$，计算有多少个正整数 $b$ 满足 $\text{lcm}(a, b) = x$。

每个测试文件包含 $T$ 组数据，每组输入两个正整数 $x, a$。

样例

输入

输出

思路分析

第一步：前提条件判断

$\text{lcm}(a, b)$ 一定是 $a$ 的倍数。所以如果 $a \nmid x$（$x$ 不能被 $a$ 整除），则不存在满足条件的 $b$，答案为 $0$。

第二步：将问题转化为质因数指数约束

将 $x$ 分解为质因数形式 $x = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$。设 $a$ 在 $p_i$ 上的指数为 $\alpha_i$，$b$ 在 $p_i$ 上的指数为 $\beta_i$。

由 $\text{lcm}$ 的定义：$\text{lcm}(a, b)$ 在每个质数 $p_i$ 上的指数等于 $\max(\alpha_i, \beta_i)$。

条件 $\text{lcm}(a, b) = x$ 等价于对每个质数 $p_i$：$\max(\alpha_i, \beta_i) = e_i$。

第三步：逐质数分析自由度

令 $d = x / a$。对每个质因数 $p_i$ 分两种情况：

若 $\alpha_i = e_i$（即 $p_i \nmid d$）：$a$ 已经把指数顶到了 $e_i$，所以 $\beta_i$ 可以在 $[0, e_i]$ 中任取，共 $e_i + 1$ 种选择
若 $\alpha_i < e_i$（即 $p_i \mid d$）：必须靠 $b$ 把指数顶上去，$\beta_i$ 被锁死为 $e_i$，只有 $1$ 种选择

第四步：乘法原理

各质数的选择互相独立，总方案数 = 各质数贡献的乘积。

验证样例：$x = 12 = 2^2 \times 3^1$，$a = 4 = 2^2 \times 3^0$，$d = 3$。

$p = 2$：$e = 2$，$d \% 2 \neq 0$，贡献 $2 + 1 = 3$
$p = 3$：$e = 1$，$d \% 3 = 0$，贡献 $1$（锁死）
答案 $= 3 \times 1 = 3$，对应 $b \in {4, 12, 36}$… 等等，让我重新验证：$b$ 满足 $\text{lcm}(4, b) = 12$，所以 $b \in {3, 6, 12}$，确实是 $3$ 个

题解代码

import sys
input = sys.stdin.readline

def count_b(x, a):
    if x % a != 0:
        return 0
    d = x // a
    res = 1
    temp = x
    p = 2
    while p * p <= temp:
        if temp % p == 0:
            e = 0
            while temp % p == 0:
                temp //= p
                e += 1
            # p 不整除 d 说明 a 已顶满该质数，b 有 e+1 种选择
            if d % p != 0:
                res *= e + 1
        else:
            p += 1
    # 剩余大质因数
    if temp > 1:
        if d % temp != 0:
            res *= 2
    return res

def solve():
    T = int(input())
    for _ in range(T):
        x, a = map(int, input().split())
        print(count_b(x, a))

solve()

复杂度分析

时间复杂度：$O(\sqrt{x})$，试除法分解质因数 空间复杂度：$O(1)$，只用若干计数变量

小结

第一题是经典的模拟题，关键在于区分两种违规（重叠落子 vs 胜后继续）并正确处理优先级，难度不大但细节多
第二题的核心洞察是”自由安排配对”意味着每轮可以选择淘汰谁，贪心地保留能力值最大的队伍，排序+前缀和即可高效求解
第三题是数论经典问题，把 $\text{lcm}$ 条件拆解到每个质因数上的指数约束后，问题变为简单的乘法原理计数

这篇文章有帮助吗？

| GitHub 留言