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

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

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

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

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

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

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

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

🍠 携程秋招第一场笔试，来啦！！！

🍥 本次难度其实不大的，前三题比较容易

1️⃣ 看着很唬人！简单的构造题

2️⃣ 看着很唬人！猜结论题

3️⃣ 比较基础的 DFS

4️⃣ 贪心+拓展版的滑动窗口，双端队列

3️⃣ 01. 数字排序的挑战

问题描述

在一个宁静的小镇上，K小姐是一位热爱数字的数学家。她最近遇到了一个有趣的问题：她希望构造一个包含从 到 的所有整数的排列 ，并且这个排列的最长上升子序列的长度恰好为 。更有趣的是，K小姐希望这个排列在所有符合条件的排列中字典序最小。

为了帮助 K小姐，您需要编写一个程序来生成这样的排列。排列是由 到 的整数按任意顺序组成，每个整数恰好出现一次。例如，排列 是有效的，但 不是，因为数字 出现了两次。

输入格式

输入包含一行两个整数 ，，表示排列的长度和最长上升子序列的长度。

输出格式

输出包含一行一个整数，表示字典序最小的长度为 的排列 的值。

样例输入

5 3

样例输出

1 2 5 4 3

数据范围

• 

题解

构造题

1. 构造前 个元素：将 到 的数字按顺序放入排列中。这确保了我们有一个递增的子序列。

2. 处理剩余元素：将剩余的元素降序（从 到 ）放入排列中。

3. 组合结果：将前 个元素和剩余的元素组合起来，形成最终的排列。

参考代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, k; 
    cin >> n >> k; // 读取输入的 n 和 k
    for(int i = 0; i < k - 1; i++) 
        cout << i + 1 << " "; // 输出前 k-1 个数字
    for(int i = n - 1; i >= k - 1; i--)
        cout << i + 1 << " \n"[i == k - 1]; // 输出剩余数字，确保字典序最小
    return 0;
}

• Python

def construct_permutation(n, k):
    # 构造前 k-1 个数字
    result = list(range(1, k))
    # 添加剩余的数字，按降序排列
    result += list(range(n, k - 1, -1))
    return result

# 主函数
if __name__ == "__main__":
    n, k = map(int, input().split())
    permutation = construct_permutation(n, k)
    print(" ".join(map(str, permutation)))  # 输出结果

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        
        // 输出前 k-1 个数字
        for (int i = 1; i < k; i++) {
            System.out.print(i + " ");
        }
        
        // 输出剩余的数字，按降序排列
        for (int i = n; i >= k; i--) {
            System.out.print(i + (i == k ? "\n" : " "));
        }
    }
}

• Cpp

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, k; 
    cin >> n >> k; // 读取输入的 n 和 k
    for(int i = 0; i < k - 1; i++) 
        cout << i + 1 << " "; // 输出前 k-1 个数字
    for(int i = n - 1; i >= k - 1; i--)
        cout << i + 1 << " \n"[i == k - 1]; // 输出剩余数字，确保字典序最小
    return 0;
}

🍰 02.奇数长度子串的反转权值

问题描述

在一个神秘的游戏中，K小姐需要将一个由字符 0 和 1 组成的字符串转换为全 1 的状态。每次操作中，她可以选择一个下标 i (满足 )，然后将从第一个字符到第 i 个字符的所有字符取反（即 0 变为 1，1 变为 0）。K小姐希望知道，在给定字符串中，有多少个长度为奇数的非空子串的权值是奇数。

例如，字符串 00110 的操作过程可以如下进行：

1. 选择 i=5，字符串变为 11001；
2. 选择 i=4，字符串变为 00111；
3. 选择 i=2，字符串变为 11111。

在这个例子中，K小姐至少需要进行 3 次操作才能将字符串变为全 1，因此该字符串的权值为 3。

输入格式

第一行包含一个整数 ()，表示字符串的长度。

第二行包含一个长度为 的 字符串。

输出格式

输出包含一行一个整数，表示长度和权值都是奇数的非空子串数量。

样例输入

5
01010

样例输出

6

数据范围

• 字符串长度 的范围为 到 。

题解

结论题

观察到数据范围为 ，这题肯定不能暴力统计

手玩几个样例，或者打表后，后会发现

最终的答案就是，所有 0 开始并且长度为奇数的子串数量

参考代码

• Python

def solve():
    n = int(input())
    s = input().strip()
    ans = 0

    # 遍历字符串
    for i in range(n):
        # 如果当前字符是 '0'
        if s[i] == '0':
            # 计算从当前字符到字符串末尾的奇数长度子串数量
            res = n - 1 - i # 剩余字符数
            ans += res // 2 + 1 # 计算奇数长度子串的数量
    print(ans) # 输出结果

if __name__ == "__main__":
    solve()

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String s = scanner.next();
        int ans = 0;

        // 遍历字符串
        for (int i = 0; i < n; i++) {
            // 如果当前字符是 '0'
            if (s.charAt(i) == '0') {
                // 计算从当前字符到字符串末尾的奇数长度子串数量
                int res = n - 1 - i; // 剩余字符数
                ans += res / 2 + 1; // 计算奇数长度子串的数量
            }
        }
        System.out.println(ans); // 输出结果
    }
}

• Cpp

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

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;

    // 遍历字符串
    for (int i = 0; i < n; i++) {
        // 如果当前字符是 '0'
        if (s[i] == '0') {
            // 计算从当前字符到字符串末尾的奇数长度子串数量
            int res = n - 1 - i; // 剩余字符数
            ans += res / 2 + 1; // 计算奇数长度子串的数量
        }
    }
    cout << ans << endl; // 输出结果
}

signed main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1; // 测试用例数量
    while (T--) {
        solve(); // 解决问题
    }
    return 0;
}

📝 03.K小姐的密码生成器

问题描述

K小姐是一家科技公司的安全专家。她正在设计一个新的密码生成系统，该系统使用从 到 的数字来生成 位的密码（每个数字最多只能使用一次）。为了确保密码的安全性，K小姐想知道在所有可能生成的密码中，有多少个密码的数值大于给定的阈值 。

输入格式

一行输入三个整数 、 和 ，分别表示可用的最大数字、密码的位数和安全阈值。

输出格式

输出一个整数，表示大于安全阈值 的密码数量。

样例输入

5 1 0 

样例输出

5

样例说明

在这个例子中，可以生成的1位密码有6个（0,1,2,3,4,5），其中大于0的有5个（1,2,3,4,5）。

样例输入

4 2 35

样例输出

4

样例说明

在这个例子中，可以生成的2位密码中，大于35的有4个（40,41,42,43）。注意，44不能生成，因为4已经使用过了。

数据范围

• 
• 
• 

题解

经典的DFS题

1. 首先，用一个二进制掩码 mask 来记录哪些数字已经被使用。
2. 实现一个DFS函数，它有三个参数：
   • u：当前生成的密码位数
   • s：当前生成的密码数值
3. 在DFS过程中，有以下几个关键点：
   • 如果已经生成了m位密码，检查它是否大于k，如果是，就增加计数。
   • 对于每一位，我尝试使用0到n的每个数字（如果还没被使用的话）。
   • 特别注意，如果是第一位（u==0），不能使用0，因为密码不能以0开头。

参考代码

• Python

def solve():
    n, m, k = map(int, input().split())
    mask = 0
    res = 0

    def dfs(u, s):
        nonlocal res, mask
        if u == m:
            if s > k:
                res += 1
            return