笔试时间：2025年8月19日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

众所周知，斐波那契数列为 1, 1, 2, 3, 5, …，即从第三项开始每一项都等于前两项之和。现在，Tk 对这串由神奇的数列元素构成的字符串，他想知道连续若干项数列的子项区间内有多少个奇数。

输入描述

第一行输入一个整数 T (1 ≤ T ≤ 10^4)，表示查询次数。

此后每组测试数据一行，包含两个整数 l 和 r (1 ≤ l ≤ r ≤ 10^9)，分别对应区间的左右端点。

输出描述

对于每组测试数据，输出一行一个整数，表示该区间内斐波那契数列第 l 项到第 r 项之间的奇数个数。

样例输入

2

1 2

6 6

样例输出

2

0

参考题解

可以发现：数列的奇偶性是 1 1 0 1 1 0.... 的循环，前 i 个数中有 (i / 3) * 2 + min(2, i % 3)个。

C++：

#include <bits/stdc++.h>

const int inf = 0x3f3f3f3f;
using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
        auto get = [&](int x) {
        return x / 3 * 2 + std::min(2, x % 3);
    };
    for (int i = 0; i < n; ++i) {
        int l, r;
        std::cin >> l >> r;
        std::cout << get(r) - get(l - 1) << "\n"; 
    }

}

int main() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    
    solve();

    return 0;
}

Java：

import java.io.*;
import java.util.*;

public class Main {
    // 统计 [1..x] 中不是 3 的倍数的个数
    static long get(long x) {
        if (x <= 0) return 0; // 防止 l=0 时出现负模
        return (x / 3) * 2 + Math.min(2, (int)(x % 3));
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder out = new StringBuilder();

        int n = fs.nextInt();
        for (int i = 0; i < n; i++) {
            long l = fs.nextLong();
            long r = fs.nextLong();
            out.append(get(r) - get(l - 1)).append('\n');
        }
        System.out.print(out.toString());
    }

    // 简洁快速输入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) { in = is; }

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

        long nextLong() throws IOException {
            int c; long sgn = 1, val = 0;
            do { c = read(); } while (c <= ' ' && c != -1);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') { val = val * 10 + (c - '0'); c = read(); }
            return val * sgn;
        }

        int nextInt() throws IOException { return (int) nextLong(); }
    }
}

Python：

import sys

def get(x: int) -> int:
    """统计 [1..x] 中不是 3 的倍数的个数"""
    if x <= 0:
        return 0  # 防止 l=0 时 l-1 为负导致行为差异
    return (x // 3) * 2 + min(2, x % 3)

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    n = next(it)
    out_lines = []
    for _ in range(n):
        l = next(it); r = next(it)
        out_lines.append(str(get(r) - get(l - 1)))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

第二题

Tk 有两个长度为 n 的数组 {a1, a2, …, an} 和 {b1, b2, …, bn}。

其中，Tk 定义这两个数组的匹配度为满足 ai = bi 的下标 i 的数目。为了最大化匹配度，Tk 将针对数组做如下的两个阶段的操作，分别是删除阶段和调整阶段：删除阶段（至少执行一次，可以执行多次）：选择任意一个下标 i，删除 ai 和 bi，删掉后，剩余的元素按照原顺序重新拼接为长度为 n-1 的数组。调整阶段：修改 ai 的值为 bi+1，或不进行操作；修改 bi 的值为 ai+1，或不进行操作。记此时的数组长度为 m，Tk 按照 1 ≤ v ≤ m-1 的顺序对每个索引 i 依次执行以下两种操作：保证输出在最佳策略下能够得到的最大匹配度。

输入描述

输入包含多组测试数据。

第一行输入一个整数 T，表示测试数据的组数。

对于每组数据：

第一行输入一个整数 n (2 ≤ n ≤ 10^5)。

第二行输入 n 个整数 a1, a2, …, an (1 ≤ ai ≤ 10^9)。

第三行输入 n 个整数 b1, b2, …, bn (1 ≤ bi ≤ 10^9)。

输出描述

对于每组测试数据，输出一个整数，表示能够得到的最大匹配度。

样例输入

2

3

1 2 3

3 2 1

3

1 2 3

3 1 2

样例输出

2

0

参考题解

C++：

Java：

import java.io.*;
import java.util.*;

public class Main {

    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c; int sgn = 1; int val = 0;
            do { c = read(); } while (c <= ' ' && c != -1);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') { val = val * 10 + (c - '0'); c = read(); }
            return val * sgn;
        }
    }

    public static void solve(FastScanner fs, StringBuilder out) throws Exception {
        int n = fs.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) a[i] = fs.nextInt();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            b[i] = fs.nextInt();
            if (a[i] == b[i]) ans++;
        }

        int[] pre = new int[n];
        int[] suf = new int[n];

        for (int i = 0; i < n; i++) {
            int x = (a[i] == b[i]) ? 1 : 0;
            int y = 0, z = 0, t = 0;
            if (i + 1 < n) {
                y = (a[i] == a[i + 1]) ? 1 : 0;
                z = (b[i] == b[i + 1]) ? 1 : 0;
                t = (b[i + 1] == a[i + 1]) ? 1 : 0;
            }
            pre[i] = Math.max(Math.max(x, y), Math.max(z, t));
            if (i > 0) pre[i] += pre[i - 1];
        }

        for (int i = n - 1; i >= 0; i--) {
            int x = (a[i] == b[i]) ? 1 : 0;
            int y = 0, z = 0, t = 0;
            if (i + 1 < n) {
                y = (a[i] == a[i + 1]) ? 1 : 0;
                z = (b[i] == b[i + 1]) ? 1 : 0;
                t = (b[i + 1] == a[i + 1]) ? 1 : 0;
            }
            suf[i] = Math.max(Math.max(x, y), Math.max(z, t));
            if (i < n - 1) suf[i] += suf[i + 1];
        }

        if (n >= 1) {
            ans = Math.max(ans, pre[n - 1]);
            ans = Math.max(ans, suf[0]);
        }
        if (n >= 2) {
            ans = Math.max(ans, Math.max(pre[n - 2], suf[1]));
        }

        if (n >= 3) {
            for (int i = 1; i < n - 1; i++) {
                int cur = (i > 1 ? pre[i - 2] : 0);
                cur += suf[i + 1];
                // a[i - 1], a[i] 都会被影响