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

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

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

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

本场题目难度不大，第一题是 双指针，第二题 贡献法，第三题可以 猜结论

🧷 01.LYA的珠宝展示顺序

问题描述

LYA是一位珠宝设计师，她正在准备一场珠宝展。她有一系列独特的珠宝作品，每件都有其独特的价值。为了让展览更有趣，LYA决定按照特殊的顺序展示她的作品。她想按照以下规则来决定展示顺序：

1. 首先选择价值居中的作品（如果作品数量为奇数）或两个中间价值的作品中较小的一个（如果作品数量为偶数）。
2. 展示选中的作品，并将其从列表中移除。
3. 重复步骤1和2，直到所有作品都被展示。

LYA想知道按照这个规则，她的珠宝作品会以什么顺序被展示。

输入格式

第一行包含一个正整数 （），表示珠宝作品的数量。 第二行包含 个正整数 （），表示每件珠宝作品的价值。

输出格式

输出一行，包含 个整数，表示珠宝作品展示的顺序。

样例输入

4
1 9 8 5

样例输出

5 8 1 9

样例说明

首先选择5（两个中间值中较小的一个），然后是8，接着是1，最后是9。

数据范围

题解

找规律+模拟。

1. 首先对输入的价值序列进行排序。
2. 使用两个指针，一个指向序列中间（偶数长度时指向中间偏左），另一个指向中间偏右。
3. 交替输出左指针和右指针指向的元素，并向两端移动指针。

这种方法能够保证每次都选择当前剩余元素中的中位数或两个中间值中较小的一个。

时间复杂度：排序需要 ，输出需要 ，总体时间复杂度为 。 空间复杂度：，用于存储排序后的序列。

参考代码

• Python

n = int(input())
a = list(map(int, input().split()))
a.sort()
l, r = (n-1)//2, n//2
result = []
while l >= 0 and r < n:
    if l == r:
        result.append(a[l])
    else:
        result.extend([a[l], a[r]])
    l -= 1
    r += 1
print(*result)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        int l = (n - 1) / 2, r = n / 2;
        while (l >= 0 && r < n) {
            if (l == r) {
                System.out.print(a[l] + " ");
            } else {
                System.out.print(a[l] + " " + a[r] + " ");
            }
            l--;
            r++;
        }
    }
}

• Cpp

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int l = (n - 1) / 2, r = n / 2;
    while (l >= 0 && r < n) {
        if (l == r) {
            cout << a[l] << " ";
        } else {
            cout << a[l] << " " << a[r] << " ";
        }
        l--, r++;
    }
    return 0;
}

🍿 02.LYA的字符串魔法

问题描述

LYA 是一位热爱魔法的少女。最近，她发现了一种神奇的字符串魔法。这种魔法可以从一个由小写字母组成的字符串中提取出各种子序列，并计算这些子序列中不同字符的总数。

给定一个长度为 的小写字母字符串 ，LYA 想知道所有非空子序列中不同字符的个数总和是多少。由于这个数字可能非常大，LYA 只需要知道这个总和对 取模后的结果。

你能帮助 LYA 完成这个魔法计算吗？

输入格式

输入一行，包含一个仅由小写字母组成的字符串 。

输出格式

输出一个整数，表示所有非空子序列中不同字符的个数总和对 取模后的结果。

样例输入

aaaa

样例输出

15

样例输入

abcde

样例输出

80

数据范围

题解

这道题目的关键在于理解子序列的性质和不同字符的计数方法。

1. 对于字符串中的每个字符，我们需要考虑它在多少个子序列中出现。

2. 假设字符 在原字符串中出现了 次，那么包含至少一个 的子序列数量为 （选择或不选择每个 ，减去全不选的情况）。

3. 对于不包含 的其他位置，有 种选择方式。

4. 因此，字符 对最终结果的贡献为 。

5. 我们需要对字符串中的每个不同字符重复这个计算过程，并将结果相加。

6. 最后，将总和对 取模即可得到最终答案。

这种方法的时间复杂度为 ，其中 是字符串的长度。我们只需要遍历一次字符串来统计每个字符的出现次数，然后对每个不同的字符进行一次计算。

参考代码

• Python

from collections import Counter

def sol