✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

淘天

题目一：小兰的学术影响力评估

1️⃣：将论文按引用次数降序排序并分组处理

2️⃣：使用前缀和技术计算权威评分总和

3️⃣：利用数学分析找到最优的综合影响力指数

难度：中等

这道题目的核心在于理解加权H指数的定义，通过排序和前缀扫描的方法，将复杂的条件判断转化为简单的数学计算。关键洞察是发现随着前缀扩展，权威评分总和单调递增而引用次数单调递减，因此可以通过一次扫描找到最优解。

题目二：小基的魔法药剂配制

1️⃣：理解平方自由核的数学概念和性质

2️⃣：使用线性筛法预处理质因数分解

3️⃣：按平方自由核分组实现最优排列策略

难度：中等偏难

这道题目结合了数论和贪心算法，需要深入理解完全平方数的性质。通过平方自由核的概念，将看似复杂的乘积判断转化为分组问题。算法的巧妙之处在于利用数学理论简化了问题的复杂度。

题目三：小毛的神秘宝石收藏

1️⃣：分析因子个数的数学性质，发现圣石等价于质数平方

2️⃣：使用埃拉托斯特尼筛法预处理质数

3️⃣：利用前缀和数组实现区间查询的快速响应

难度：中等

这道题目考查数论基础和算法优化。关键在于识别出"恰有三个因子"等价于"质数的平方"这一数学性质，然后通过区间转换和前缀和优化实现高效查询。算法设计体现了预处理与查询分离的经典思想。

01. 小兰的学术影响力评估

问题描述

小兰是一位知名学者，最近她被邀请参加一个重要的学术评估会议。评估委员会决定使用一种新的"综合影响力指数"来评估学者的学术贡献。

在这个评估体系中，小兰的每篇研究论文都有两个重要属性：被其他学者引用的次数，以及该论文在学术界的权威性评分。评估委员会定义"综合影响力指数"为满足以下条件的最大非负整数 ：在所有被引用次数至少为 次的论文中，这些论文的权威性评分总和至少为 。

作为小兰的助理，你需要帮助她计算出这个综合影响力指数，以便她能够在评估会议上展示自己的学术成就。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 （），代表数据组数。

每组测试数据描述如下：

• 第一行输入一个整数 （），表示小兰发表的论文数量。

• 第二行输入 个整数 （），其中 表示第 篇论文的被引用次数。

• 第三行输入 个整数 （），其中 表示第 篇论文的权威性评分。

此外，保证单个测试文件中所有测试用例的 之和不超过 。

输出格式

每组测试数据输出一行一个整数，表示小兰的综合影响力指数。

样例输入

1
5
5 3 1 4 2
1 2 1 3 2

样例输出

4

数据范围

• 
• 
• 
• 
• 单个测试文件中所有测试用例的 之和不超过

样例	解释说明
样例1	论文引用次数为 [5,3,1,4,2]，权威评分为 [1,2,1,3,2]。当 时，引用次数 的论文有第1篇和第4篇，权威评分和为 ，满足条件。当 时，只有第1篇论文引用次数 ，权威评分为1 < 5，不满足条件。因此答案为4。

题解

这道题目的核心在于理解"综合影响力指数"的定义。我们需要找到最大的非负整数 ，使得引用次数至少为 的论文的权威评分总和也至少为 。

首先分析问题的本质：对于任意给定的 值，我们需要统计所有满足 的论文，然后计算这些论文的权威评分总和 。如果 ，那么这个 就是一个可行解。我们要找的是最大的可行解。

解题思路如下：

1. 排序分组：将所有论文按照引用次数从大到小排序，引用次数相同的论文放在同一组。

2. 前缀扫描：从引用次数最高的论文开始，逐组加入论文。每次加入一组论文后，我们得到：

   • 当前已加入论文的权威评分总和
   • 当前组的引用次数

3. 候选值计算：对于当前状态，我们可以考虑将 设为 。这样设置的原因是：

   • 所有已加入的论文引用次数都
   • 权威评分总和
   • 因此条件得到满足

4. 最优解选择：在扫描过程中， 单调递增， 单调递减。我们记录所有候选值中的最大值作为最终答案。

为什么这种方法是正确的？关键观察是：对于任意可行的 ，必然存在某个前缀使得该前缀的权威评分总和至少为 ，且前缀中引用次数最小的论文的引用次数也至少为 。我们的算法恰好枚举了所有这样的前缀。

时间复杂度为 ，主要消耗在排序上。空间复杂度为 。

参考代码

• Python

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

def solve():
    n = int(input())
    # 读取引用次数
    a = list(map(int, input().split()))
    # 读取权威评分
    w = list(map(int, input().split()))
    
    # 将论文信息配对并按引用次数降序排序
    papers = [(a[i], w[i]) for i in range(n)]
    papers.sort(key=lambda x: x[0], reverse=True)
    
    total = 0  # 当前权威评分总和
    ans = 0    # 最终答案
    i = 0
    
    while i < n:
        cite = papers[i][0]  # 当前组的引用次数
        # 将相同引用次数的论文全部加入
        while i < n and papers[i][0] == cite:
            total += papers[i][1]
            i += 1
        # 更新答案为当前候选值的最大值
        ans = max(ans, min(total, cite))
    
    return ans

T = int(input())
for _ in range(T):
    print(solve())

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        cin >> n;
        
        vector<ll> a(n), w(n);
        // 读取引用次数
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        // 读取权威评分
        for (int i = 0; i < n; i++) {
            cin >> w[i];
        }
        
        // 配对并排序
        vector<pair<ll, ll>> data(n);
        for (int i = 0; i < n; i++) {
            data[i] = {a[i], w[i]};
        }
        // 按引用次数降序排序
        sort(data.begin(), data.end(), [](const pair<ll, ll>& x, const pair<ll, ll>& y) {
            return x.first > y.first;
        });
        
        ll sum = 0, res = 0;
        int idx = 0;
        
        while (idx < n) {
            ll cite_cnt = data[idx].first;
            // 处理相同引用次数的所有论文
            while (idx < n && data[idx].first == cite_cnt) {
                sum += data[idx].second;
                idx++;
            }
            // 更新答案
            res = max(res, min(sum, cite_cnt));
        }
        
        cout << res << "\n";
    }
    
    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));
        PrintWriter pw = new PrintWriter(System.out);
        
        int T = Integer.parseInt(br.readLine());
        
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            
            // 读取引用次数
            String[] aStr = br.readLine().split(" ");
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(aStr[i]);
            }
            
            // 读取权威评分
            String[] wStr = br.readLine().split(" ");
            long[] w = new long[n];
            for (int i = 0; i < n; i++) {
                w[i] = Long.parseLong(wStr[i]);
            }
            
            // 创建论文对象并排序
            Paper[] papers = new Paper[n];
            for (int i = 0; i < n; i++) {
                papers[i] = new Paper(a[i], w[i]);
            }
            
            // 按引用次数降序排序
            Arrays.sort(papers, (x, y) -> Long.compare(y.cite, x.cite));
            
            long totalScore = 0;
            long maxIdx = 0;
            int i = 0;
            
            while (i < n) {
                long curCite = papers[i].cite;
                // 处理所有相同引用次数的论文
                while (i < n && papers[i].cite == curCite) {
                    totalScore += papers[i].weight;
                    i++;
                }
                // 更新最大综合影响力指数
                maxIdx = Math.max(maxIdx, Math.min(totalScore, curCite));
            }
            
            pw.println(maxIdx);
        }
        
        pw.close();
        br.close();
    }
    
    static class Paper {
        long cite, weight;
        
        Paper(long cite, long weight) {
            this.cite = cite;
            this.weight = weight;
        }
    }
}

02. 小基的魔法药剂配制

问题描述

小基是一位技艺高超的炼金术师，她正在为即将到来的魔法大会准备一种特殊的药剂。这种药剂需要使用 种不同的魔法原料，每种原料都有一个独特的魔力值，分别为 。

根据古老的炼金术法则，药剂的效果取决于原料的排列顺序。当两种相邻原料的魔力值乘积恰好是一个完全平方数时，它们之间会产生魔法共鸣，大大增强药剂的效力。

小基希望找到一种原料的排列方式，使得产生魔法共鸣的相邻原料对数量达到最大值。作为小基的助手，你需要帮助她设计出最优的排列方案。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 （），表示测试用例数。

此后 行，每行输入一个整数 （），表示魔法原料的种类数量。

此外，保证所有测试用例的 之和不超过 。

输出格式

对于每组测试数据，新起一行，输出一个长度为 的排列，表示能产生最多魔法共鸣的原料排列方案。

如果存在多个最优解决方案，您可以输出任意一个。

样例输入

2
5
10

样例输出

2 3 1 4 5
10 7 6 1 4 9 2 8 3 5

数据范围

• 
• 
• 所有测试用例的 之和不超过

样例	解释说明
样例1	对于 的情况，排列 [2,3,1,4,5] 中，没有相邻元素的乘积是完全平方数，所以共鸣次数为0。但这是该规模下的最优解。
样例2	对于 的情况，可以通过合理分组相同平方自由核的数字来获得较多的魔法共鸣。

题解

这道题目的关键在于理解什么时候两个数的乘积是完全平方数。

首先，我们需要知道一个重要的数学性质：两个正整数的乘积是完全平方数，当且仅当它们的"平方自由核"相同。

什么是平方自由核？对于任意正整数 ，将其进行质因数分解：，其平方自由核就是所有指数为奇数的质因子的乘积。

例如：

• （只有3的指数为奇数）
• （只有2的指数为奇数）
• 

只有当 时， 才是完全平方数。

基于这个理论，解题策略就很清晰了：

1. 分组策略：将所有数字 到 按照它们的平方自由核进行分组。

2. 最优性分析：

   • 每个组内的任意两个数字都可以相邻放置（它们的乘积是完全平方数）
   • 不同组之间的数字不能产生魔法共鸣
   • 对于大小为 的组，最多可以产生 次魔法共鸣（将组内元素连续排列）

3. 实现方法：

   • 使用线性筛法预处理每个数的最小质因子
   • 通过质因数分解计算每个数的平方自由核
   • 将相同平方自由核的数字归为一组
   • 依次输出各组的元素

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

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

def get_core(x, s