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

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

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

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

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

🍒 本专栏已收集 140+ 套题，算法题 会在第一时间跟新

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

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

🌈 B度秋招笔试，来啦！！！

🍥 本次百度有三套卷会陆续更新的哦～，本套的三题都是比较 智慧 的找规律题，前两题码量不大。

1️⃣ 找规律，分析k与 (n + 1) / 2 的大小关系

2️⃣ 可以打表找一找 0123456789 的分布，应该能出结论，也可以双链表模拟，或者上数据结构直接 模拟

3️⃣ 打表找规律，打表发现与杨辉三角有关，难度较大，代码较长

🍓 01.LYA的果园收成评测链接🔗

问题描述

LYA 是一个热爱园艺的女孩，她有一个长长的果园，里面种植了 棵果树。每棵果树都按照 1 到 的顺序编号。今年是丰收年，LYA 决定邀请她的朋友们来采摘水果。

为了让采摘过程更有趣，LYA 制定了一个游戏规则：每个人可以选择 棵果树进行采摘。但是，如果一个人选择了编号为 的果树，而编号为 的果树没有被选中，那么这个人就可以获得一分奖励。

LYA 想知道，在这个游戏规则下，一个人最多能获得多少分奖励。你能帮助她计算出这个最高分数吗？

输入格式

第一行输入一个整数 ，表示测试数据的组数。

接下来的 行，每行包含两个整数 和 ，分别表示果树的总数和可以选择的果树数量。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示在给定条件下能获得的最高奖励分数。

样例输入1

2
1 1
4 2

样例输出1

1
2

样例解释

样例 解释说明

样例1	在第一个测试用例中，只有一棵果树，选择它就可以得到1分。
样例2	在第二个测试用例中，一种最优策略是选择编号为1和3的果树，这样可以得到2分奖励。

数据范围

• 
• 
• 

题解

找规律/猜结论

1. 首先，要理解得分的规则：只有当我们选择了一棵树，而没有选择它相邻的下一棵树时，才能得分。
2. 考虑极端情况：
   • 如果 ，我们只能得到1分（选择第一棵或最后一棵树）。
   • 如果 ，也只能得一分，最后一颗树能得分。
3. 关键观察：要最大化得分，应该尽可能地选择不相邻的树。
4. 最优策略：
   • 如果 ，可以选择所有奇数编号的树（或所有偶数编号的树），这样每选择一棵树都能得分。
   • 如果 ，就要反过来思考：有多少棵树没被选中。未被选中的树的数量是 ，决定能得多少分，但要考虑最后一颗树，所以还要加1。
5. 综上所述，最终的答案就是 。
   • 当 时，答案就是 。
   • 当 时，答案是 （加1是因为最后一棵树如果被选中也能得分）。

参考代码

• Python

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

# 处理每个测试用例
for _ in range(t):
    # 读取果树总数和可选择的数量
    n, k = map(int, input().split())
    
    # 计算最高得分
    # 得分为k和n-k+1中的较小值
    score = min(k, n - k + 1)
    
    # 输出结果
    print(score)

• 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 n = scanner.nextLong();
            long k = scanner.nextLong();
            
            // 计算最高得分
            // 得分为k和n-k+1中的较小值
            long score = Math.min(k, n - k + 1);
            
            // 输出结果
            System.out.println(score);
        }
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;  // 读取测试用例数量
    
    while (t--) {
        long long n, k;
        cin >> n >> k;  // 读取果树总数和可选择的数量
        
        // 计算最高得分
        // 得分为k和n-k+1中的较小值
        long long score = min(k, n - k + 1);
        
        // 输出结果
        cout << score << endl;
    }
    
    return 0;
}

✨ 02.字符串魔法师评测链接🔗

题目描述

K小姐是一位神奇的字符串魔法师。她最近发明了一种新的魔法，可以对字符串进行特殊的变换。这个魔法的效果如下：

对于一个长度为 的只包含小写字母的字符串 ，K小姐会进行 次操作。在第 次操作中，她会将字符串的第 个字符移动到字符串的末尾。

K小姐想知道，在进行完 次操作后，字符串会变成什么样子。你能帮她预测最终的结果吗？

输入格式

输入一行，包含一个由小写字母构成的字符串 ，长度为 （）。

输出格式

输出一行，包含一个字符串，表示经过 次操作后的字符串。

样例输入1

paectc

样例输出1

accept

样例输入2

abqde

样例输出2

bdaeq

样例解释

样例 解释说明

样例1	第一步：aectcp 第二步：actcpe 第三步：accpet 第四步：accetp 第五步：accept 第六步：accept
样例2	第一步：bqdea 第二步：bdeaq 第三步：bdaqe 第四步：bdaeq 第五步：bdaeq

数据范围

• 

题解

找规律/双链表模拟/Treap

本题的做法就很多了，大家可以自行尝试，题解是找规律的做法

直接模拟这个过程，每次将字符串的第一个加入答案(后面这个字符不会再被移到后面)，以及第二个加入字符串末尾。

参考代码

• Python

# 读取输入
s = input().strip()
n = len(s)
left = 0
res = ""

# 进行n次操作
for i in range(n):
    s += s[left]
    left += 1
    res += s[left]
    left += 1

# 输出结果
print(res)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int n = s.length();
        int left = 0;
        StringBuilder res = new StringBuilder();
        StringBuilder sb = new StringBuilder(s);

        for (int i = 0; i < n; i++) {
            sb.append(sb.charAt(left++));
            res.append(sb.charAt(left++));
        }

        System.out.println(res.toString());
    }
}

• Cpp

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    string s; cin >> s;
    int n = s.size();
    int left = 0;
    string res = "";
    for(int i = 0; i < n; i++)
    {
        s += s[left++];   	
        res += s[left++]; // 当前字符不会再输出了
    }
    cout << res << "\n";
    return 0;
}

💬 03.魔法师的连锁反应评测链接🔗

问题描述

魔法师 K 小姐正在研究一种新的魔法连锁反应。她有一排魔法宝石，每颗宝石都有自己的能量值。K 小姐发现，当她以特定的方式激活这些宝石时，会产生一种奇妙的连锁反应。

具体来说，魔法连锁反应的过程如下：

1. 首先，K 小姐会在相邻的宝石之间交替施加"增强"和"减弱"魔法。
2. 然后，受到魔法影响的相邻宝石会产生新的能量值，形成新的一排宝石。
3. 这个过程会不断重复，直到最后只剩下一颗宝石为止。

K 小姐想知道，给定一排初始的魔法宝石，最后剩下的那颗宝石的能量值是多少。

输入格式

第一行输入一个整数 （），表示初始魔法宝石的数量。

第二行输入 个整数 （），表示每颗魔法宝石的初始能量值。

输出格式

输出一个整数，表示最后剩下的魔法宝石的能量值。由于这个值可能非常大，请输出它对 取模的结果。

样例输入1

4
1 2 3 4

样例输出1

1000000005

样例解释

样例 解释说明

样例1	初始宝石能量为 [1,2,3,4]。第一次连锁反应后变为 [3,-1,7]（1+2, 2-3, 3+4）。第二次变为 [4,6]（3-(-1), -1+7）。最后变为 [-2]（4-6）。取模后得到 1000000005。

数据范围

• 
• 

题解

找规律

1. 连锁反应的本质： 每次反应都是相邻元素的加减交替运算。这个过程会不断重复，直到只剩下一个元素。

2. 关键观察：

   • 当序列长度为 4k+1 时（k为非负整数），最终结果的系数分布呈现特殊模式。
   • 其他长度的序列经过若干次操作后，最终都会变成长度为 4k+1 的情况。

3. 系数分布规律： 对于长度为 4k+1 的序列，最终结果的系数分布类似于杨辉三角的某一行，但只保留奇数位置的数。

4. 算法步骤： a) 预处理阶乘和逆元，用于快速计算组合数。 b) 计算最终的系数分布。 c) 对原序列进行处理，使其长度变为 4k+1。 d) 将处理后的序列与系数相乘并求和。

参考代码

• Python

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

MOD = 10**9 + 7  # 模数，用于