笔试时间：2025年5月4日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：波浪数

形如1212121这种由不同的2个数字交替出现的数称为波浪数，k重波浪数则是指在k种不同的进制下都是波浪数的数。特别规定只有一位的数字（如1）也是波浪数。

例如，606₍₇₎ = 454₍₈₎ = 363₍₉₎ = 300₍₁₀₎ = 1A1₍₁₃₎ 是一个四重波浪数。

需要在指定数字区间内根据给定所需要考虑的进制区间找到所有的k重波浪数。

输入描述

五个整数(a, b, l, r, k)，其中[a,b]表示应当考虑的进制区间，[l,r]以十进制表示询问的数字区间，k表示波浪数的重数。

数据范围：2 <= a <= b <= 32，1 <= l <= r <= 10000000，k ∈ {2,3,4}

输出描述

从小到大按十进制输出所有所求的波浪数，每行一个数字。

样例输入

2 3 10 15 2

样例输出

10

样例说明

样例要求在2进制和3进制下求[10,15]数字区间（十进制）内所有的波浪数。这个区间内只有一个波浪数10（十进制），转化为2进制和3进制分别为：10₍₂₎ = 101₍₂₎, 10₍₃₎ = 101₍₃₎

参考题解

解题思路：

对每个进制B，分两步生成该进制下的波浪数：

1. 单数字波浪数：遍历1到(B-1)的数字（进制B下首位不能为0），若其值在[l,r]内，标记为该进制下的波浪数。
2. 多数字波浪数：构造"x y x y..."模式（相邻位不同）的数。遍历可能的位数len，确定最高位x（1到B-1）和次高位y（0到B-1且x≠y），按模式生成数，若值在[l,r]内，标记为该进制下的波浪数。

C++：

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int a, b, l, r, k;
    cin >> a >> b >> l >> r >> k;
    
    int lenRange = r - l + 1;
    vector<int> counts(lenRange, 0);
    
    for (int B = a; B <= b; ++B) {
        int maxLen = 1;
        long long pow = B;
        while (pow <= r) {
            maxLen++;
            if (pow > (long long)r / B) break;
            pow *= B;
        }
        
        unordered_set<int> seenThisBase;
        
        // 处理1位波浪数
        for (int d = 1; d < B; ++d) {
            long long val = d;
            if (val >= l && val <= r) {
                seenThisBase.insert((int)val);
            }
        }
        
        // 处理2位及以上的波浪数
        for (int len = 2; len <= maxLen; ++len) {
            for (int x = 1; x < B; ++x) {
                for (int y = 0; y < B; ++y) {
                    if (x == y) continue;
                    
                    long long val = 0;
                    for (int pos = 0; pos < len; ++pos) {
                        int digit = (pos % 2 == 0) ? x : y;
                        val = val * B + digit;
                        if (val > r) break;
                    }
                    
                    if (val >= l && val <= r) {
                        seenThisBase.insert((int)val);
                    }
                }
            }
        }
        
        for (int v : seenThisBase) {
            counts[v - l]++;
        }
    }
    
    for (int i = 0; i < lenRange; ++i) {
        if (counts[i] == k) {
            cout << (l + i) << '\n';
        }
    }
    
    return 0;
}

Java：

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int a = Integer.parseInt(line[0]);
        int b = Integer.parseInt(line[1]);
        int l = Integer.parseInt(line[2]);
        int r = Integer.parseInt(line[3]);
        int k = Integer.parseInt(line[4]);
        
        int lenRange = r - l + 1;
        int[] counts = new int[lenRange];
        
        for (int B = a; B <= b; ++B) {
            int maxLen = 1;
            long pow = B;
            while (pow <= r) {
                maxLen++;
                if (pow > (long)r / B) break;
                pow *= B;
            }
            
            Set<Integer> seenThisBase = new HashSet<>();
            
            // 处理1位波浪数
            for (int d = 1; d < B; ++d) {
                long val = d;
                if (val >= l && val <= r) {
                    seenThisBase.add((int)val);
                }
            }
            
            // 处理2位及以上的波浪数
            for (int len = 2; len <= maxLen; ++len) {
                for (int x = 1; x < B; ++x) {
                    for (int y = 0; y < B; ++y) {
                        if (x == y) continue;
                        
                        long val = 0;
                        boolean overflow = false;
                        for (int pos = 0; pos < len; ++pos) {
                            int digit = (pos % 2 == 0) ? x : y;
                            val = val * B + digit;
                            if (val > r) {
                                overflow = true;
                                break;
                            }
                        }
                        
                        if (!overflow && val >= l && val <= r) {
                            seenThisBase.add((int)val);
                        }
                    }
                }
            }