✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺
• 配套练习题库

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

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

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

蚂蚁

题目一：数字排列大作战

1️⃣：将数字按降序排列得到最大值

2️⃣：比较排列后的数字长度和字典序

难度：中等

这道题目的关键在于理解双方都希望获得最大数字的原则。通过将数位按降序排列，可以得到数字的最大值，然后比较长度和字典序确定胜者。解法简洁高效，适合用字符串处理来实现。

题目二：销售数据预测

1️⃣：构建设计矩阵和响应向量

2️⃣：计算X^T X和X^T y

3️⃣：解线性方程组得到参数

难度：中等

这道题目结合了数据解析和线性代数，需要实现最小二乘法线性回归。关键在于构建正规方程并使用高斯消元法求解，得到能够预测销售额的模型参数。

题目三：数字连续性判定

1️⃣：使用数位DP统计满足条件的数字

2️⃣：预计算所有可能的数位集合是否满足连续性

3️⃣：递归处理每个数位，计算区间结果

难度：中等偏难

这道题目涉及数位DP技巧，需要高效统计区间内满足特定数位特性的整数。通过设计适当的状态表示和转移方程，可以在可接受的时间内处理高达10^18范围的区间查询。

01. 数字排列大作战

问题描述

小基和小A正在参加一场智力挑战赛。每轮比赛，他们各自会得到一个数字，比赛规则如下：

• 小基拿到的初始数字为
• 小A拿到的初始数字为
• 每人可以选择对自己的数字进行一次操作：将数字的各个数位任意重新排列
• 也可以选择不进行任何操作，保持原数字不变
• 双方都希望自己的最终数字尽可能大

请你判断，在双方都采取最优策略的情况下，谁的最终数字更大，或者两人的数字相等。

输入格式

每个测试文件包含多组测试数据。第一行输入一个整数 表示数据组数，每组测试数据描述如下：

第一行输入一个整数表示小基的数字 。

第二行输入一个整数表示小A的数字 。

输出格式

对于每一组测试数据，输出一行结果。如果小基的最终数字大于小A的，输出 ；如果小A的最终数字大于小基的，输出 ；如果两人的最终数字相等，输出 。

样例输入

3
1
2
123
321
12
9

样例输出

BLUE
EQUAL
RED

数据范围

• 
• 

样例 解释说明

样例1	小基的数字是1，无论如何排列仍是1；小A的数字是2，排列后仍是2。2大于1，所以输出BLUE。
样例2	小基的数字是123，排列后最大为321；小A的数字是321，排列后仍是321。两人数字相等，所以输出EQUAL。
样例3	小基的数字是12，排列后最大为21；小A的数字是9，排列后仍是9。21大于9，所以输出RED。

题解

这道题目乍看起来很复杂，但实际上有一个非常简洁的解法。

首先，我们需要理解的一个关键点是：无论是小基还是小A，他们都希望自己的数字尽可能大。对于任何一个数字，要使其最大，只需要将其所有数位按降序排列即可。例如，数字123排列后最大为321，数字1024排列后最大为4210。

知道了这一点，我们的解题思路就很清晰了：

1. 读取小基和小A的初始数字 和
2. 对这两个数字分别进行优化排列（数位降序排序）
3. 比较排列后的两个数字大小

比较两个大数的大小时，需要注意：

• 如果两个数字的位数不同，位数更多的数字一定更大
• 如果位数相同，则按照字典序比较

举个例子：

• 数字9和数字12，排列后分别是9和21，显然21更大
• 数字123和数字321，排列后都是321，所以相等
• 数字1和数字2，排列后仍然是1和2，2更大

实现上，我们可以直接将输入的数字作为字符串处理，然后进行排序和比较，这样可以避免处理超大整数的麻烦。

时间复杂度：对于每组测试数据，我们需要对两个数字的数位进行排序，假设最大位数为d，则时间复杂度为O(d log d)，总体时间复杂度为O(T * d log d)，其中T是测试数据的组数。

空间复杂度：O(d)，主要用于存储数字的字符串表示。

参考代码

• Python

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

# 读取测试用例数量
t = int(input())

for _ in range(t):
    # 读取两个数字
    a = input()
    b = input()
    
    # 将数字字符串转为字符列表，排序后逆序排列得到最大值
    max_a = ''.join(sorted(a, reverse=True))
    max_b = ''.join(sorted(b, reverse=True))
    
    # 比较数字长度
    if len(max_a) > len(max_b):
        print("RED")
    elif len(max_a) < len(max_b):
        print("BLUE")
    else:
        # 长度相同时比较字典序
        if max_a > max_b:
            print("RED")
        elif max_a < max_b:
            print("BLUE")
        else:
            print("EQUAL")

• Cpp

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    // 加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        string a, b;
        cin >> a >> b;
        
        // 将数位排序得到最大数字
        sort(a.rbegin(), a.rend());
        sort(b.rbegin(), b.rend());
        
        // 比较长度和字典序
        if (a.size() > b.size()) {
            cout << "RED" << endl;
        } else if (a.size() < b.size()) {
            cout << "BLUE" << endl;
        } else {
            if (a > b) cout << "RED" << endl;
            else if (a < b) cout << "BLUE" << endl;
            else cout << "EQUAL" << endl;
        }
    }
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < t; i++) {
            // 读取两个数字
            String a = br.readLine();
            String b = br.readLine();
            
            // 将数字转为字符数组并排序
            char[] aArr = a.toCharArray();
            char[] bArr = b.toCharArray();
            Arrays.sort(aArr);
            Arrays.sort(bArr);
            
            // 反转得到降序排列
            String maxA = new StringBuilder(new String(aArr)).reverse().toString();
            String maxB = new StringBuilder(new String(bArr)).reverse().toString();
            
            // 比较结果
            if (maxA.length() > maxB.length()) {
                System.out.println("RED");
            } else if (maxA.length() < maxB.length()) {
                System.out.println("BLUE");
            } else {
                if (maxA.compareTo(maxB) > 0) {
                    System.out.println("RED");
                } else if (maxA.compareTo(maxB) < 0) {
                    System.out.println("BLUE");
                } else {
                    System.out.println("EQUAL");
                }
            }
        }
    }
}

02. 销售数据预测

问题描述

小柯是某电商平台的数据分析师，她正在研究如何根据历史数据预测产品的未来销售额。根据她的经验，产品销售额可能与产品价格、广告投入和市场竞争度等因素相关。她决定使用最小二乘法线性回归模型来建立预测模型，以实现更精准的销售预测。

作为她的助手，你需要帮助她实现这个预测模型，计算出最佳的模型参数，从而支持公司的库存管理和生产规划决策。

输入格式

输入数据为一个二维列表，表示历史销售数据样本。列表中的每个子列表代表一个样本，其格式为 ，其中：

• 表示产品价格
• 表示广告投入金额
• 表示市场竞争对手数量
• 表示实际销售额

例如：

输出格式

输出为一个列表，包含预测模型的参数，格式为 ，其中：

• 为模型截距
• 为产品价格的系数
• 为广告投入的系数
• 为市场竞争度的系数

输出结果保留三位小数。

样例输入

[[100,2000,5,30000],[150,2500,6,35000],[120,2100,4,28000],[130,2300,5,32000]]

样例输出

[-1666.667,-100.0,16.667,1666.667]

数据范围

• 输入列表的长度不超过
• 所有数值范围在 之间
• 保证输入数据矩阵可逆，存在唯一解

样例 解释说明

样例1	从4组销售数据中，我们得到的线性回归方程为：sales = -1666.667 - 100.0 * price + 16.667 * advertising + 1666.667 * competitors

题解

这道题目考察的是最小二乘法线性回归的实现。我们需要根据给定的样本数据，计算出最佳拟合直线的参数。

首先，让我们回顾一下线性回归的基本原理。线性回归模型假设因变量y与自变量x之间存在线性关系：

其中，是我们需要求解的参数，是误差项。

在最小二乘法中，我们的目标是找到一组参数，使得预测值与实际值之间的平方误差之和最小。这可以通过解正规方程来实现：

其中，X是设计矩阵（第一列全为1，其余列为自变量的值），y是因变量向量，是我们要求解的参数向量。

解决这个方程的标准方法是：

在这道题中，我们需要解一个4×4的线性方程组。可以使用高斯消元法来实现，或者利用线性代数库中的矩阵求逆功能。

具体步骤如下：

1. 解析输入数据，构建设计矩阵X和响应向量y
2. 计算和
3. 解线性方程组
4. 输出参数向量

通过这个模型，我们可以预测销售额与产品价格、广告投入和竞争对手数量之间的关系。例如，在样例中，我们发现产品价格对销售额有负面影响（系数为-100），而广告投入和竞争对手数量对销售额有正面影响（系数分别为16.667和1666.667）。

时间复杂度：主要在于解线性方程组，对于4×4的矩阵，时间复杂度为O(1)。如果考虑输入数据的规模n，则构建的复杂度为O(n)。总体时间复杂度为O(n)。

空间复杂度：O(1)，我们只需要存储固定大小的矩阵和向量。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()
import numpy as np #  本oj不支持numpy，python请用别的方式

def solve(data):
    # 创建设计矩阵X和响应向量y
    X = np.ones((len(data), 4))
    y = np.zeros(len(data))
    
    for i, row in enumerate(data):
        X[i, 1:] = row[:3]  # 前三个元素是自变量
        y[i] = row[3]       # 最后一个元素是因变量
    
    # 计算最小二乘解
    XTX = X.T @ X
    XTy = X.T @ y
    beta = np.linalg.solve(XTX, XTy)
    
    # 格式化输出
    return [round(b, 3) for b in beta]

# 解析输入
line = input()
data = []
num = ""
stack = []

for c in line:
    if c.isdigit() or c == '-':
        num += c
    elif num:
        stack.append(int(num))
        num = ""
        if c == ']' and len(stack) == 4:
            data.append(stack)
            stack = []

if num:
    stack.append(int(num))
    if len(stack) == 4:
        data.append(stack)

# 计算结果并输出
result = solve(data)
print(f"[{result[0]},{result[1]},{result[2]},{result[3]}]")

• Cpp

#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <cmath>
using namespace std;

// 高斯消元法解方程组
vector<double> gauss(vector<vector<double>>& A, vector<double>& b) {
    int n = A.size();
    vector<vector<double>> aug(n, vector<double>(n+1));
    
    // 构建增广矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            aug[i][j] = A[i][j];
        }
        aug[i][n] = b[i];
    }
    
    // 高斯消元
    for (int i = 0; i < n; i++) {
        // 选主元
        int maxRow = i;
        for (int j = i + 1; j < n; j++) {
            if (abs(aug[j][i]) > abs(aug[maxRow][i])) {
                maxRow = j;
            }
        }
        swap(aug[i], aug[maxRow]);
        
        // 消元
        for (int j = i + 1; j < n; j++) {
            double ratio = aug[j][i] / aug[i][i];
            for (int k = i; k <= n; k++) {
                aug[j][k] -= ratio * aug[i][k];
            }
        }
    }
    
    // 回代
    vector<double> x(n);
    for (int i = n - 1; i >= 0; i--) {
        x[i] = aug[i][n];
        for (int j = i + 1; j < n; j++) {
            x[i] -= aug[i][j] * x[j];
        }
        x[i] /= aug[i][i];
    }
    
    return x;
}

int main() {
    // 读取输入
    string line;
    getline(cin, line);
    
    vector<vector<int>> data;
    vector<int> curr;
    string num = "";
    
    for (char c : line) {
        if (c == '-' || isdigit(c)) {
            num += c;
        } else if (!num.empty()) {
            curr.push_back(stoi(num));
            num = "";
            if (c == ']' && curr.size() == 4) {
                data.push_back(curr);
                curr.clear();
            }
        }
    }
    
    int n = data.size();
    
    // 构建设计矩阵和响应向量
    vector<vector<double>> X(n, vector<double>(4));
    vector<double> y(n);
    
    for (int i = 0; i < n; i++) {
        X[i][0] = 1;  // 截距项
        X[i][1] = data[i][0];  // 价格
        X[i][2] = data[i][1];  // 广告费用
        X[i][3] = data[i][2];  // 竞争对手数量
        y[i] = data[i][3];     // 销售额
    }
    
    // 计算X^T X和X^T y
    vector<vector<double>> XTX(4, vecto