🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🌈 阿里云秋招笔试，来啦！！！

🍥 本次三题都不是很好写，前两题有点诈骗题，第三题需要一定的知识基础

1️⃣ 暴力模拟，很容易被题意骗去找规律，其实不如直接模拟

2️⃣ 刚好和第一题反过来，比起写数位DP，还是直接找规律容斥比较简单

3️⃣ 并查集+数据结构维护，由于 K 很小，每次暴力找就可以

📚 01.字母拼词大挑战 评测链接🔗

问题描述

LYA 是一位热爱文字游戏的语言学家。她最近发明了一种新的单词规则，称为"ABA 模式"。这种模式要求单词必须恰好由三个字母组成，其中第一个和第三个字母相同，但第二个字母必须与它们不同。例如，"bob" 和 "aza" 符合这个模式，但 "aaa" 不符合。

LYA 现在手头有 26 种小写字母，每种字母的数量各不相同。她想知道，使用这些字母，最多能组成多少个符合 "ABA 模式" 的单词。

你能帮助 LYA 解决这个问题吗？

输入格式

输入的第一行是一个整数 （），表示测试用例的数量。

对于每个测试用例：

• 输入一行包含 26 个整数，分别表示从 'a' 到 'z' 每个字母的数量 （）。

输出格式

对于每个测试用例，输出一个整数，表示最多可以组成的符合 "ABA 模式" 的单词数量。

样例输入1

2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 0 0 0 0 0 2 3

样例输出1

0
3

样例输入2

1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

样例输出2

117

样例解释

数据范围

• 
• ，其中 表示第 个字母的数量
• 保证单个测试用例中所有字母的总数不超过

题解

贪心+暴力模拟

需要理解 "ABA 模式" 的要求：三个字母，首尾相同，中间不同。

让我们一步步来分析这个问题：

1. 对于每个符合要求的单词，需要使用两个相同的字母（作为首尾）和一个不同的字母（作为中间）。

2. 关键点在于：应该如何选择这些字母来最大化单词的数量？

   • 直觉告诉我们，应该优先使用数量最多的字母作为首尾字母。
   • 对于中间的字母，可以使用任何与首尾不同的字母。

3. 基于这个思路，可以设计一个贪心算法：

   • 每次选择当前数量最多的字母作为首尾字母（减去 2）。
   • 选择当前数量最少的不同字母作为中间字母（减去 1）。
   • 重复这个过程，直到无法继续组成新的单词。

4. 为了高效地实现这个策略，cpp中可以使用一个多重集（multiset）来存储字母的数量，其他语言可以自行尝试其他的数据结构，python中可以用 sortedlist。

5. 算法的主要步骤：

   • 将所有非零数量的字母放入多重集。
   • 当多重集中至少有两个元素时：
     • 取出最大元素（作为首尾字母）和最小元素（作为中间字母）。
     • 如果可以组成单词（最大元素 >= 2 且最小元素 >= 1），增加计数。
     • 更新字母数量，如果还有剩余，重新插入多重集。

参考代码

• Cpp

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

int maxABAWords(vector<int>& letterCounts) {
    // 创建一个降序排列的多重集，用于存储字母的数量
    multiset<int, greater<int>> counts;
    for (int count : letterCounts) {
        if (count > 0) {
            counts.insert(count);  // 只插入数量大于0的字母
        }
    }
    
    int wordCount = 0;  // 用于记录可以组成的ABA单词数量
    while (counts.size() >= 2) {  // 至少需要两种不同的字母才能组成ABA单词
        auto maxIt = counts.begin();  // 获取数量最多的字母
        auto minIt = prev(counts.end());  // 获取数量最少的字母
        
        int maxCount = *maxIt;  // 最多字母的数量
        int minCount = *minIt;  // 最少字母的数量
        
        // 从多重集中移除这两个字母
        counts.erase(maxIt);
        counts.erase(minIt);
        
        if (maxCount >= 2 && minCount >= 1) {  // 检查是否能组成ABA单词
            wordCount++;  // 可以组成一个ABA单词
            // 更新字母数量并重新插入多重集
            if (maxCount - 2 > 0) counts.insert(maxCount - 2);
            if (minCount - 1 > 0) counts.insert(minCount - 1);
        } else {
            break;  // 如果不能组成ABA单词，退出循环
        }
    }
    
    return wordCount;  // 返回可以组成的ABA单词总数
}

int main() {
    int T;
    cin >> T;  // 读取测试用例数量
    
    while (T--) {
        vector<int> letterCounts(26);  // 创建一个向量存储26个字母的数量
        for (int i = 0; i < 26; i++) {
            cin >> letterCounts[i];  // 读取每个字母的数量
        }
        cout << maxABAWords(letterCounts) << endl;  // 输出结果
    }
    
    return 0;
}

☕️ 02.卢小姐的咖啡店优惠 评测链接🔗

问题描述

卢小姐经营着一家小型咖啡店。为了吸引更多顾客，她制定了一个特殊的优惠策略：如果一位顾客的消费金额是 6 元的倍数或 7 元的倍数，就可以获得一杯免费的特调咖啡。

现在，卢小姐想要统计在不同的价格区间内，有多少种消费金额可以享受这个优惠。她需要你的帮助来快速计算这个数字。

输入格式

第一行输入一个整数 （），表示询问的次数。

接下来的 行，每行包含两个整数 和 （），表示一个价格区间。

输出格式

对于每次询问，输出一行，包含一个整数，表示在给定价格区间内可以享受优惠的消费金额数量。

样例输入

3
1 100
114 514
114514 1919810

样例输出

28
114
515799

样例解释

数据范围

题解

容斥原理

看起来需要数位DP，但注意到条件比较简单，可以利用容斥原理来解决这个问题。

首先，需要明白，一个数是"好数"（可以享受优惠）的条件是：它是 6 的倍数或 7 的倍数。这意味着我们需要计算以下三类数字：

1. 6 的倍数的数量
2. 7 的倍数的数量
3. 既是 6 的倍数又是 7 的倍数的数量（即 42 的倍数）

根据容斥原理，区间 内的"好数"数量可以表示为：

这个公式看起来复杂，但实际上非常直观。先计算到 为止的"好数"数量，然后减去到 为止的"好数"数量，就得到了区间 内的"好数"数量。

在代码实现中，只需要使用整数除法来计算各个倍数的数量。例如， 中 6 的倍数数量就是 。

参考代码

• Python

# 读取询问次数
t = int(input())

# 处理每次询问
for _ in range(t):
    # 读取区间左右端点
    l, r = map(int, input().split())
    
    # 计算右端点r的好数数量
    c6_r = r // 6  # 6的倍数数量
    c7_r = r // 7  # 7的倍数数量
    c42_r = r // 42  # 42的倍数数量
    good_r = c6_r + c7_r - c42_r
    
    # 计算左端点l-1的好数数量
    l -= 1
    c6_l = l // 6
    c7_l = l // 7
    c42_l = l // 42
    good_l = c6_l + c7_l - c42_l
    
    # 输出区间内好数的数量
    print(good_r - good_l)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取询问次数
        int t = scanner.nextInt();
        
        for (int i = 0; i < t; i++) {
            // 读取区间左右端点
            long l = scanner.nextLong();
            long r = scanner.nextLong();
            
            // 计算右端点r的好数数量
            long c6R = r / 6;  // 6的倍数数量
            long c7R = r / 7;  // 7的倍数数量
            long c42R = r / 42;  // 42的倍数数量
            long goodR = c6R + c7R - c42R;
            
            // 计算左端点l-1的好数数量
            l--;
            long c6L = l / 6;
            long c7L = l / 7;
            long c42L = l / 42;
            long goodL = c6L + c7L - c42L;
            
            // 输出区间内好数的数量
            System.out.println(goodR - goodL);
        }
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;  // 读取询问次数
    
    while (t--) {
        long long l, r;
        cin >> l >> r;  // 读取区间左右端点
        
        // 计算右端点r的好数数量
        long long c6R = r / 6;