程序员基德

昨天 13:22 中国科学技术大学 C++ 发布于浙江

关注

【笔试刷题】携程-2026.03.29-算法岗-改编真题

✅ 春招备战指南 ✅

💡 学习建议：

先尝试独立解题
对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

携程-2026.03.29-算法岗

这套算法岗和开发岗共享了 3 道通用题，中间夹了一道更偏计算实现的注意力题。前两题还是热身节奏，第 3 题需要把整套流程按矩阵规则完整落地，第 4 题继续是数论跳跃。

题目一：字母 a 的位置

固定长度、固定字符集，直接顺扫即可，是明显的热身题。

难度：Low

题目二：实时榜单

范围只有 $100 \times 100$ ，维护每人每题最高分再暴力统计排名就够了，不需要额外数据结构。

难度：Low

题目三：双门控加权器

这题核心不在“想算法”，而在把门控、Top-k、归一化和最终乘法一条链完整实现出来。边界主要在 s_max \le 0 和 Top-k 并列处理。

难度：Mid

题目四：min-gcd 迭代器

把 $\gcd$ 不变的一整段连续迭代压成一次跳跃，是这题唯一真正能过大数据的做法。

难度：High

1. 字母 a 的位置

问题描述

小基拿到了一段长度恰好为 $5$ 的标签串。

这段字符串只会由 a、b、c、d、e 这五个字符各出现一次组成，顺序可能被打乱。现在需要找出字符 a 出现在第几个位置。

位置从 $1$ 开始计数。

输入格式

输入一行，一个长度为 $5$ 的字符串 $s$ 。

保证字符串中恰好包含一个 a、一个 b、一个 c、一个 d、一个 e。

输出格式

输出一个整数，表示字符 a 的位置。

样例输入 1

abcde

样例输出 1

数据范围

$|s| = 5$
字符串只由 a、b、c、d、e 组成
这五个字符各出现且只出现一次

样例	解释说明
样例1	字符串的第 $1$ 个字符就是 `a`，所以答案为 $1$ 。

题解

这题没有任何隐藏条件，顺着扫一遍字符串就够了。

因为字符串长度固定为 $5$ ，所以直接从左到右枚举下标：

如果当前字符不是 a，继续往后看。
一旦遇到 a，立刻输出当前位置编号。

位置从 $1$ 开始计数，而程序里的下标通常从 $0$ 开始，所以输出时记得加 $1$ 。

时间复杂度是 $O(5)$ ，也就是常数复杂度。空间复杂度是 $O(1)$ 。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()


def solve():
    s = input()

    # 顺着找一遍，遇到 a 就输出 1-based 位置。
    for i, ch in enumerate(s):
        if ch == "a":
            print(i + 1)
            return


if __name__ == "__main__":
    solve()

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    // 长度固定为 5，直接线性扫描即可。
    for (int i = 0; i < 5; i++) {
        if (s[i] == 'a') {
            cout << i + 1 << '\n';
            return 0;
        }
    }
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();

        // 逐个字符检查，找到 a 后输出位置。
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'a') {
                System.out.println(i + 1);
                return;
            }
        }
    }
}

2. 实时榜单

问题描述

小基正在盯一场 $IOI$ 赛制训练赛的实时榜单。

比赛里一共有若干道互相独立的题。每名选手对同一道题可以提交很多次，但记分时只保留这道题的最高得分；选手总分等于自己所有题目最高分之和。

现在按时间顺序给出 $n$ 次提交记录。第 $i$ 次提交是三个整数 $(a_i, b_i, c_i)$ ，表示编号为 $a_i$ 的选手在编号为 $b_i$ 的题目上拿到了 $c_i$ 分。

每处理完一条提交记录，都要输出编号为 $1$ 的选手当前排名。

排名规则如下：

总分更高的选手排名更靠前。
总分相同的选手并列，且并列会占用名次。

例如分数从高到低依次为 $100,100,100,80$ ，那么对应名次就是 $1,1,1,4$ 。

输入格式

第一行输入一个整数 $n$ ，表示提交记录条数。

接下来 $n$ 行，每行输入三个整数 $a,b,c$ ，表示一条提交记录。

输出格式

输出 $n$ 行。

第 $i$ 行输出一个整数，表示处理完前 $i$ 条记录后，编号为 $1$ 的选手排名。

样例输入 1

样例输出 1

数据范围

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 100$
$1 \le b_i \le 100$
$0 \le c_i \le 100$

样例	解释说明
样例1	第 $7$ 次提交后，编号为 $1$ 的选手在第 $1$ 题上的最高分从 $80$ 提升到 $90$ ，总分随之变化，因此排名也会重新计算。

题解

题目里的范围其实已经把做法写得很明显了：选手编号最多只有 $100$ ，题号最多也只有 $100$ 。

所以根本不需要平衡树或堆，直接维护两张表就够了：

best[u][p]：选手 $u$ 在题目 $p$ 上的历史最高分。
sum[u]：选手 $u$ 当前总分。

当读到一条新提交 $(a,b,c)$ 时：

如果 $c \le best[a][b]$ ，说明这次没有刷新这道题的最高分，总分不变。
如果 $c > best[a][b]$ ，就把总分增加 c - best[a][b]，再更新 best[a][b]。

接下来只要统计有多少名选手的总分严格大于 sum[1]。

因为并列要占名次，所以编号为 $1$ 的选手排名就是：

1 + \#\{u \mid sum[u] > sum[1]\}

为什么这样对？

总分更高的人一定排在前面。
总分相同的人和编号为 $1$ 并列，不会把他的名次继续往后推。

每次提交后扫描一次 $100$ 名选手就行，因此总时间复杂度是 $O(100n)$ ，在这里完全够用。空间复杂度是 $O(100 \times 100)$ 。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()


def solve():
    n = int(input())

    # best[u][p] 记录选手 u 在题目 p 上的最高分。
    best = [[0] * 101 for _ in range(101)]
    total = [0] * 101

    out = []
    for _ in range(n):
        u, p, sc = map(int, input().split())

        # 只有刷新最高分时，总分才会变大。
        if sc > best[u][p]:
            total[u] += sc - best[u][p]
            best[u][p] = sc

        my_score = total[1]
        rank = 1
        for i in range(1, 101):
            if total[i] > my_score:
                rank += 1
        out.append(str(rank))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // best[u][p]：选手 u 在题目 p 上的最高分。
    int best[101][101] = {};
    int sum[101] = {};

    while (n--) {
        int u, p, sc;
        cin >> u >> p >> sc;

        // 如果这次提交更好，就把差值补到总分里。
        if (sc > best[u][p]) {
            sum[u] += sc - best[u][p];
            best[u][p] = sc;
        }

        int rank = 1;
        for (int i = 1; i <= 100; i++) {
            if (sum[i] > sum[1]) {
                rank++;
            }
        }
        cout << rank << '\n';
    }
    return 0;
}

Java

import java.io.BufferedInputStream;

public class Main {
    static class FastScanner {
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws Exception {
            if (ptr >= len) {
                len = System.in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        int nextInt() throws Exception {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int x = 0;
            while (c > ' ') {
                x = x * 10 + c - '0';
                c = read();
            }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder sb = new StringBuilder();

        int n = fs.nextInt();
        int[][] best = new int[101][101];
        int[] sum = new int[101];

        for (int i = 0; i < n; i++) {
            int u = fs.nextInt();
            int p = fs.nextInt();
            int sc = fs.nextInt();

            // 只在刷新题目最高分时更新总分。
            if (sc > best[u][p]) {
                sum[u] += sc - best[u][p];
                best[u][p] = sc;
            }

            int rank = 1;
            for (int j = 1; j <= 100; j++) {
                if (sum[j] > sum[1]) {
                    rank++;
                }
            }
            sb.append(rank).append('\n');
        }

        System.out.print(sb.toString());
    }
}

3. 双门控加权器

问题描述

现在给定一组单头注意力的输入矩阵 $Q,K,V$ ，需要按照下面的 TG-SA 规则计算注意力矩阵 $A$ 和最终输出矩阵 $O$ 。

设：

$Q,K,V \in \mathbb{R}^{L \times d}$ ；
$1 \le k_{top} \le L$ ；
阈值参数固定为 $\alpha = 0.2,\ \beta = 0.6$ 。

先计算原始打分矩阵：

S = \frac{QK^T}{\sqrt{d}}

对第 $i$ 行，记：

s_{max} = \max_j S_{ij}

然后做双门控映射：

\widetilde{S}_{ij} = \begin{cases} 0, & s_{max} \le 0 \\ 0, & S_{ij} \le \alpha s_{max}, \ s_{max} > 0 \\ \dfrac{S_{ij} - \alpha s_{max}}{(\beta - \alpha)s_{max}}, & \alpha s_{max} < S_{ij} \le \beta s_{max}, \ s_{max} > 0 \\ 1, & S_{ij} > \beta s_{max}, \ s_{max} > 0 \end{cases}

之后对每一行执行两步操作：

只保留该行数值最大的 $k_{top}$ 个位置，其余位置全部置为 $0$ 。如果出现边界并列，优先保留下标更小的位置。
若这一行和为 $0$ ，则把整行改成均匀分布；否则将整行归一化，使这一行元素和为 $1$ 。

归一化后的矩阵记为 $A$ ，最终输出矩阵为：

O = AV

你需要输出矩阵 $A$ 和矩阵 $O$ 。

输入格式

输入是一行 JSON 对象，包含以下字段：

"Q"：一个 $L \times d$ 的二维数组；
"K"：一个 $L \times d$ 的二维数组；
"V"：一个 $L \times d$ 的二维数组；
"k_top"：一个整数。

保证三组矩阵的行数相同，且列数相同。

输出格式

输出一个 JSON 对象，格式为：

{"A":[...],"O":[...]}

其中：

A 为 $L \times L$ 的注意力矩阵；
O 为 $L \times d$ 的输出矩阵。

你的实数答案只要满足绝对误差或相对误差不超过 $10^{-6}$ ，就会被判定为正确。

样例输入 1

{"Q":[[1,0],[0,1]],"K":[[1,0],[0,1]],"V":[[1,2],[3,4]],"k_top":1}

样例输出 1

{"A":[[1.0,0.0],[0.0,1.0]],"O":[[1.0,2.0],[3.0,4.0]]}

数据范围

$1 \le L,d \le 30$
$1 \le k_{top} \le L$
输入矩阵元素的绝对值不超过 $20$
阈值参数固定为 $\alpha = 0.2,\ \beta = 0.6$

样例	解释说明
样例1	$Q$ 与 $K$ 都是单位矩阵时，两行都会把注意力集中到自己对应的位置上，因此 $A$ 也是单位矩阵，最终 $O=V$ 。

题解

这题本质上就是一次按规则改造过的注意力计算，流程完全固定。

第一步：计算原始打分矩阵

直接按照定义做矩阵乘法：

S_{ij} = \frac{\sum_{t=1}^{d} Q_{it}K_{jt}}{\sqrt{d}}

第二步：逐行做双门控映射

对每一行先求最大值 $s_{max}$ 。

若 $s_{max} \le 0$ ，这一行门控后的结果直接全是 $0$ 。
否则就按题目给的分段函数，把每个值映射到区间 $[0,1]$ 。

第三步：Top-k 稀疏化

每一行只保留最大的 $k_{top}$ 个位置，其余清零。

为了让答案唯一，需要处理并列边界。这里按题意规定：若数值相同，则优先保留下标更小的位置。

第四步：行归一化

如果一整行都是 $0$ ，就改成均匀分布。
否则把整行除以它的行和，得到注意力矩阵 $A$ 。

第五步：计算输出矩阵

最后再做一次矩阵乘法：

O = AV

总时间复杂度是 $O(L^2 d + L^2 \log L)$ ，空间复杂度是 $O(L^2)$ 。

参考代码

Python

import json
import math
import sys

input = lambda: sys.stdin.readline().strip()


def normalize_num(x):
    s = f"{x:.10f}".rstrip("0").rstrip(".")
    if "." not in s:
        s += ".0"
    return float(s)


def solve():
    raw = sys.stdin.read().strip()
    data = json.loads(raw)

    q = data["Q"]
    k = data["K"]
    v = data["V"]
    k_top = data["k_top"]

    l = len(q)
    d = len(q[0])
    inv = 1.0 / math.sqrt(d)

    score = [[0.0] * l for _ in range(l)]
    for i in range(l):
        for j in range(l):
            cur = 0.0
            for t in range(d):
                cur += q[i][t] * k[j][t]
            score[i][j] = cur * inv

    att = [[0.0] * l for _ in range(l)]
    for i in range(l):
        s_max = max(score[i])
        row = [0.0] * l

        if s_max > 0:
            lo = 0.2 * s_max
            hi = 0.6 * s_max
            for j in range(l):
                val = score[i][j]
                if val <= lo:
                    row[j] = 0.0
                elif val <= hi:
                    row[j] = (val - lo) / (hi - lo)
                else:
                    row[j] = 1.0

        order = list(range(l))
        order.sort(key=lambda idx: (-row[idx], idx))
        keep = set(order[:k_top])
        for j in range(l):
            if j not in keep:
                row[j] = 0.0

        sm = sum(row)
        if sm == 0:
            row = [1.0 / l] * l
        else:
            row = [x / sm for x in row]

        att[i] = row

    out = [[0.0] * d for _ in range(l)]
    for i in range(l):
        for j in range(l):
            if att[i][j] == 0:
                continue
            for t in range(d):
                out[i][t] += att[i][j] * v[j][t]

    ans = {
        "A": [[normalize_num(x) for x in row] for row in att],
        "O": [[normalize_num(x) for x in row] for row in out],
    }
    print(json.dumps(ans, separators=(",", ":")))


if __name__ == "__main__":
    solve()

#include <bits/stdc++.h>
using namespace std;

void skip_spaces(const string &s, int &p) {
    while (p < (int)s.size() && isspace((unsigned char)s[p])) {
        p++;
    }
}

vector<vector<double>> parse_2d(const string &s, int &p) {
    skip_spaces(s, p);
    vector<vector<double>> res;
    if (p >= (int)s.size() || s[p] != '[') {
        return res;
    }

    p++;
    skip_spaces(s, p);

    while (p < (int)s.size() && s[p] == '[') {
        p++;
        skip_spaces(s, p);

        vector<double> row;
        while (p < (int)s.size()) {
            int st = p;
            if (s[p] == '+' || s[p] == '-') {
                p++;
            }
            while (p < (int)s.size() &&
                   (isdigit((unsigned char)s[p]) || s[p] == '.' || s[p] == 'e' ||
                    s[p] == 'E' || s[p] == '+' || s[p] == '-')) {
                p++;
            }
            row.push_back(strtod(s.c_str() + st, nullptr));
            skip_spaces(s, p);
            if (p < (int)s.size() && s[p] == ',') {
                p++;
                skip_spaces(s, p);
            } else if (p < (int)s.size() && s[p] == ']') {
                p++;
                break;
            } else {
                break;
            }
        }

        res.push_back(row);
        skip_spaces(s, p);
        if (p < (int)s.size() && s[p] == ',') {
            p++;
            skip_spaces(s, p);
        } else {
            break;
        }
    }

    if (p < (int)s.size() && s[p] == ']') {
        p++;
    }
    return res;
}

int parse_int_after_key(const string &s, const string &key) {
    int p = s.find(key);
    p = s.find(':', p);
    p++;
    skip_spaces(s, p);
    int sign = 1;
    if (s[p] == '-') {
        sign = -1;
        p++;
    }
    int val = 0;
    while (p < (int)s.size() && isdigit((unsigned char)s[p])) {
        val = val * 10 + (s[p] - '0');
        p++;
    }
    return sign * val;
}

string format_num(double x) {
    ostringstream out;
    out << fixed << setprecision(10) << x;
    string s = out.str();
    while (!s.empty() && s.back() == '0') {
        s.pop_back();
    }
    if (!s.empty() && s.back() == '.') {
        s.push_back('0');
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string raw, line;
    while (getline(cin, line)) {
        raw += line;
    }

    int p = raw.find("\"Q\"");
    p = raw.find('[', p);
    vector<vector<double>> q = parse_2d(raw, p);

    p = raw.find("\"K\"");
    p = raw.find('[', p);
    vector<vector<double>> k = parse_2d(raw, p);

    p = raw.find("\"V\"");
    p = raw.find('[', p);
    vector<vector<double>> v = parse_2d(raw, p);

    int k_top = parse_int_after_key(raw, "\"k_top\"");

    int l = (int)q.size();
    int d = (int)q[0].size();
    double inv = 1.0 / sqrt((double)d);

    vector<vector<double>> score(l, vector<double>(l, 0.0));
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < l; j++) {
            double cur = 0;
            for (int t = 0; t < d; t++) {
                cur += q[i][t] * k[j][t];
            }
            score[i][j] = cur * inv;
        }
    }

    vector<vector<double>> att(l, vector<double>(l, 0.0));
    for (int i = 0; i < l; i++) {
        double s_max = *max_element(score[i].begin(), score[i].end());
        vector<double> row(l, 0.0);

        if (s_max > 0) {
            double lo = 0.2 * s_max;
            double hi = 0.6 * s_max;
            for (int j = 0; j < l; j++) {
                double val = score[i][j];
                if (val <= lo) {
                    row[j] = 0.0;
                } else if (val <= hi) {
                    row[j] = (val - lo) / (hi - lo);
                } else {
                    row[j] = 1.0;
                }
            }
        }

        vector<int> ord(l);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int x, in

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

互联网刷题笔试宝典文章被收录于专栏

互联网刷题笔试宝典，这里涵盖了市面上大部分的笔试题合集，希望助大家春秋招一臂之力