携程笔试携程笔试题 0522

笔试时间：2025年5月22日

第一题

对于给定的三个小写字母a, b, c，定义它们到小写字母p之间的距离之和为：在字母表中字符p到字符a之间相差的字母数量，加上字符p到字符b之间相差的字母数量，再加上字符p到字符c之间相差的字母数量。需要注意的是，字母表中，'a'和'z'不相邻。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数T (1 ≤ T ≤ 10³) 代表数据组数。

每组测试数据描述如下：

第一行输入三个小写字母字符a, b, c；

第二行输入一个小写字母字符p。

输出描述

输出一个整数，表示所能获得的最大值。

样例输入

3

b b a

a

b a c

a

a a a

z

样例输出

0

1

72

解释：对于第一组测试数据，字符'b'到字符'a'之间没有字母；字符'a'到字符'a'之间更没有字母，所以距离和为0。对于第二组测试数据，字符'c'到字符'a'之间相差1个字母，即字符'b'。

参考题解

定义 dist(c,p)：计算字符 c 到字符 p 在字母表中的“中间隔”的字母数量。通过 abs(ord(p)-ord(c)) - 1 得到两字符之间的间隔长度。如果间隔小于 0（即相同或相邻），就认为距离为 0。对每个测试用例，读入三字符 u,v,w 和目标字符 p。分别调用 dist(u,p)、dist(v,p)、dist(w,p)，累加得到最终答案。该算法时间复杂度 O(1)／组，直接输出即可。

C++：

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

int dist_between(char c, char p) {
    int d = abs(p - c) - 1;
    return d > 0 ? d : 0;
}

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

    int t;
    cin >> t;
    while (t--) {
        char u, v, w, p;
        cin >> u >> v >> w;
        cin >> p;
        int ans = dist_between(u, p)
                + dist_between(v, p)
                + dist_between(w, p);
        cout << ans << "\n";
    }
    return 0;
}

Java：

// Java 8+
import java.io.*;
import java.util.*;

public class Main {
    static int distBetween(char c, char p) {
        int d = Math.abs(p - c) - 1;
        return d > 0 ? d : 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        while (t-- > 0) {
            String[] parts = br.readLine().split("\\s+");
            char u = parts[0].charAt(0);
            char v = parts[1].charAt(0);
            char w = parts[2].charAt(0);
            char p = br.readLine().charAt(0);

            int ans = distBetween(u, p)
                    + distBetween(v, p)
                    + distBetween(w, p);
            System.out.println(ans);
        }
    }
}

Python：

import sys
input = sys.stdin.readline

def dist(c, p):
    d = abs(ord(p) - ord(c)) - 1
    return d if d > 0 else 0

t = int(input().strip())
for _ in range(t):
    u, v, w = input().split()
    p = input().strip()
    ans = dist(u, p) + dist(v, p) + dist(w, p)
    print(ans)

第二题

给定一个长度为n的数组{a₁, a₂, …, aₙ}，定义数组的权值为数组所有元素之和。你可以执行任意次以下操作，以使数组权值最小化：选择两个索引i和j；任意选取两个正整数x和y，但需满足gcd(x, y) = gcd(aᵢ, aⱼ)；将aᵢ ← x，aⱼ ← y。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数T (1 ≤ T ≤ 10⁴)，表示测试组数；

随后对于每组数据，依次输入：

第一行输入一个整数n (1 ≤ n ≤ 2×10⁵)，表示数组长度；

第二行输入n个整数a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁹)，表示数组元素。

此外，保证所有测试数据中∑n ≤ 2×10⁵。

输出描述

对于每个测试用例，在一行上输出一个整数，表示经过任意次操作后能够得到的最小数组权值。

样例输入

2

2

1 2

3

3 7 9

样例输出

2

3

解释：在第二个测试用例中，可以先选择(i, j) = (1, 2)，gcd(3, 7) = 1。取x = y = 1得到{1, 1, 9}；再选择(i, j) = (2, 3)，gcd(1, 9) = 1，取x = y = 1得到{1, 1, 1}，权值为3。

参考题解

观察操作：可以任意次把一对(a_i,a_j)替换成(x,y)，只要 gcd(x,y)=gcd(a_i,a_j)。

最优地，替换后每对都取 x=y=g，使得这两项之和最小。

通过多次操作，可将所有元素“压缩”到整个数组的全局 gcd G。

最终数组每个元素都是 G，长度为 n，总和就是 n*G。计算方式：一次遍历求出 G，再乘以 n 即可。

C++：

// C++17
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        ll G = 0;
        for (int i = 0; i < n; i++) {
            ll x;
            cin >> x;
            if (i == 0) G = x;
            else G = gcd(G, x);
        }
        cout << G * n << "\n";
    }

    return 0;
}

Java：

// Java 8+
import java.io.*;
import java.util.*;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            StringTokenizer st = new StringTokenizer(br.readLine());
            long G = 0;
            for (int i = 0; i < n; i++) {
                long x = Long.parseLong(st.nextToken());
                if (i == 0) G = x;
                else G = gcd(G, x);
            }
            System.out.println(G * n);
        }
    }
}

Python：

import sys, math
input = sys.stdin.readline

t = int(input().strip())
for _ in range(t):
    n = int(input().strip())
    G = 0
    for i, x in enumerate(map(int, input().split())):
        G = x if i == 0 else math.gcd(G, x)
    print(G * n)

第三题

你有一个长度为n的数组a，游游定义了两个数组上的函数： - f(a) = a₁ + a₂ + … + aₘ（即数组中所有数字的和，其中m为数组长度）； - g(a) = a₁ | a₂ | … | aₘ（即数组中所有数字的按位或值）。现在，游游希望你将a分割成恰好两个非空的数组b和c，以最小化|f(b) - g(c)|的值。

输入描述

本题有多组测试数据。输入的第一行包含一个正整数T (1 ≤ T ≤ 100)，表示数据组数。接下来包含T组数据，每组数据的格式如下：第一行一个正整数n (2 ≤ n ≤ 2×10⁵)，表示数组a的长度；第二行n个整数aᵢ (0 ≤ aᵢ ≤ 10⁹)，表示数组a。（保证所有测试数据中，n的总和不超过2×10⁶）