✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺
• 配套练习题库

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

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

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

题目一：循环字符串的行首提取

1️⃣：理解循环字符串的概念和特殊排版规则

2️⃣：使用指针模拟书写过程，提取每行首字母

难度：简单

这道题目主要考察模拟能力和对循环字符串的理解。通过维护一个指针来跟踪当前在循环字符串中的位置，我们可以在 O(p) 的时间复杂度内解决问题，其中 p 是行数。

题目二：字符串优化删除

1️⃣：设计状态表示，考虑字符串末尾的不同状态

2️⃣：根据当前字符和前一状态进行状态转移

3️⃣：使用动态规划求解最大价值

难度：中等

这道题目考察动态规划和状态设计能力。关键是识别出字符串末尾可能的状态，并设计合适的状态转移方程。通过 O(n) 的时间复杂度可以求解，其中 n 是字符串长度。

题目三：L型方阵的边界元素

1️⃣：分析L型方阵的生成规则和元素1的位置特点

2️⃣：发现数学规律，推导出公式 2^(n+1) - 4

3️⃣：使用快速幂算法计算大数幂取模

难度：中等

这道题目结合了数学推理和算法实现。通过观察小规模例子，我们发现了答案与二项式系数的关系，并使用快速幂算法在 O(log n) 的时间复杂度内计算结果。

01. 循环字符串的行首提取

问题描述

小兰是一位文字艺术家，她发明了一种特殊的文本排版方式。她有一个由小写字母组成的字符串 ，她将这个字符串无限循环拼接，然后按照以下规则进行书写：

第1行：写下接下来的 个字母，然后换行； 第2行：写下接下来的 个字母，然后换行； 第3行：写下接下来的 个字母，然后换行； ... 第 行：写下接下来的 个字母，然后换行； ...

小兰想要提取每一行的第一个字母，从上到下连接起来形成一个新的字符串。现在，给定原始字符串 和行数 ，请你帮她计算出这个新字符串。

输入格式

第一行包含一个仅由小写字母组成的字符串 ，长度为 。

第二行包含一个整数 （），表示书写的行数。

输出格式

输出一个字符串，表示每一行行首字母从上到下连接形成的新字符串。

样例输入

helloworld
6

样例输出

helohw

样例 解释说明

样例1	书写过程如下： 第1行：h（取1个字母） 第2行：el（取2个字母） 第3行：low（取3个字母） 第4行：orld（取4个字母） 第5行：hello（取5个字母） 第6行：worldh（取6个字母） 每行的首字母依次为：h、e、l、o、h、w，连接起来就是"helohw"。

数据范围

• 
• 

题解

这道题目要求我们模拟一个特殊的文本排版过程，然后提取每行的首字母。

首先，我们需要理解题目中的循环字符串概念。原始字符串 会被无限循环拼接，形成一个无限长的字符串。例如，如果 = "abc"，那么循环拼接后就是 "abcabcabc..."。

接下来，我们按照规则进行书写：第 行写 个字母。关键是要跟踪我们在循环字符串中的当前位置。

一个直观的解法是使用一个指针来记录当前在循环字符串中的位置。每次我们写完一行后，指针会向前移动该行的字母数量。由于字符串是循环的，所以当指针超出原始字符串长度时，我们需要对字符串长度取模。

对于每一行，我们只需要记录该行的第一个字母，然后将这些字母连接起来就得到了答案。

时间复杂度分析：我们只需要模拟 行的书写过程，每行只提取首字母，所以总时间复杂度是 ，这对于给定的数据范围（）是完全可接受的。

参考代码

• Python

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

def solve():
    # 读取输入
    s = input()
    p = int(input())
    
    # 初始化结果字符串和当前位置
    result = ""
    pos = 0
    n = len(s)
    
    # 模拟p行书写过程
    for i in range(1, p+1):
        # 添加当前行的首字母
        result += s[pos % n]
        
        # 更新位置，跳过当前行的i个字母
        pos += i
    
    # 输出结果
    print(result)

if __name__ == "__main__":
    solve()

• Cpp

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

void solve() {
    // 读取输入
    string s;
    int p;
    cin >> s >> p;
    
    // 初始化结果字符串和当前位置
    string result = "";
    int pos = 0;
    int n = s.length();
    
    // 模拟p行书写过程
    for (int i = 1; i <= p; i++) {
        // 添加当前行的首字母
        result += s[pos % n];
        
        // 更新位置，跳过当前行的i个字母
        pos += i;
    }
    
    // 输出结果
    cout << result << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

• Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        String s = sc.nextLine();
        int p = sc.nextInt();
        
        // 初始化结果字符串和当前位置
        StringBuilder result = new StringBuilder();
        int pos = 0;
        int n = s.length();
        
        // 模拟p行书写过程
        for (int i = 1; i <= p; i++) {
            // 添加当前行的首字母
            result.append(s.charAt(pos % n));
            
            // 更新位置，跳过当前行的i个字母
            pos += i;
        }
        
        // 输出结果
        System.out.println(result.toString());
    }
}

02. 字符串优化删除

问题描述

小基正在开发一个文本处理系统，她需要处理一些由字符'0'和'1'组成的二进制字符串。系统中有一个特殊规则：任何包含连续子串"110"的文本都会被标记为不安全。

为了确保文本安全，小基决定删除字符串中的一些字符。每个位置的字符都有一个价值，删除后剩余字符的总价值应尽可能高。

给定一个长度为 的二进制字符串 和每个位置的价值 ，请计算在确保删除后的字符串不包含连续子串"110"的前提下，剩余字符的最大可能总价值。

输入格式

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

第二行包含 个整数 （），表示每个位置的价值。

第三行包含一个长度为 的二进制字符串 ，仅由字符'0'和'1'组成。

输出格式

输出一个整数，表示删除后剩余字符的最大可能总价值。

样例输入

4
4 3 2 1
1100

样例输出

7

样例 解释说明

样例1	最优策略是删除第二个字符（价值为3），剩余字符串为"100"，不包含子串"110"，总价值为4+2+1=7。

样例输入

5
1 1 1 1 1
00000

样例输出

5

样例 解释说明

样例2	字符串全为'0'，不可能形成子串"110"，因此不需要删除任何字符，总价值为5。

样例输入

12
5 5 1 1 1 1 1 1 1 1 1 1
110101100100

样例输出

14

数据范围

• 
• 
• 字符串 仅由字符'0'和'1'组成

题解

这道题目要求我们删除字符串中的一些字符，使得剩余字符串不包含连续子串"110"，并且剩余字符的总价值最大。

我们可以使用动态规划来解决这个问题。关键是要考虑如何表示状态，以及如何进行状态转移。

首先，我们需要考虑的是，对于一个不包含"110"的字符串，它的最后几个字符可能的状态有哪些。实际上，我们只需要关注最后的0到2个字符，因为只有这些字符才可能与后续添加的字符组成"110"。

我们定义状态 表示处理到第 个字符，且当前字符串的最后状态为 时，剩余字符的最大总价值。这里 有三种可能的值：

• ：最后一个字符是'0'
• ：最后一个字符是'1'
• ：最后两个字符是"11"

状态转移时，我们需要考虑当前字符是'0'还是'1'，以及之前的状态：

1. 如果当前字符是'0'：

   • 如果之前的状态是0或1，可以直接添加'0'
   • 如果之前的状态是2（即"11"），添加'0'会形成"110"，这是不允许的

2. 如果当前字符是'1'：

   • 如果之前的状态是0，可以直接添加'1'，变成状态1
   • 如果之前的状态是1，添加'1'后变成状态2（即"11"）
   • 如果之前的状态是2，添加'1'后仍然是状态2（因为我们只关心最后两个字符）

此外，对于每个位置，我们还可以选择不使用当前字符（即删除它），这样状态保持不变。

最终的答案是 ，即处理完所有字符后，三种状态下的最大价值。

时间复杂度分析：我们需要填充一个大小为 的动态规划表，每个状态的计算是常数时间的，因此总时间复杂度为 ，这对于给定的数据范围（）是完全可接受的。

参考代码

• Python

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

def solve():
    # 读取输入
    n = int(input())
    values = list(map(int, input().split()))
    s = input()
    
    # 初始化dp数组，dp[i][j]表示处理到第i个字符，最后状态为j时的最大价值
    # j=0: 最后一个字符是'0'
    # j=1: 最后一个字符是'1'
    # j=2: 最后两个字符是"11"
    dp = [[-1] * 3 for _ in range(n)]
    
    # 初始化第一个字符的状态
    if s[0] == '0':
        dp[0][0] = values[0]
    else:  # s[0] == '1'
        dp[0][1] = values[0]
    
    # 动态规划过程
    for i in range(1, n):
        # 可以选择不使用当前字符（即删除它）
        for j in range(3):
            dp[i][j] = dp[i-1][j]
        
        if s[i] == '0':
            # 如果当前字符是'0'
            # 可以从状态0或1转移过来
            if dp[i-1][0] != -1 or dp[i-1][1] != -1:
                dp[i][0] = max(dp[i][0], max(dp[i-1][0] if dp[i-1][0] != -1 else -float('inf'), 
                                            dp[i-1][1] if dp[i-1][1] != -1 else -float('inf')) + values[i])
        else:  # s[i] == '1'
            # 如果当前字符是'1'
            # 从状态0转移到状态1
            if dp[i-1][0] != -1:
                dp[i][1] = max(dp[i][1], dp[i-1][0] + values[i])
            
            # 从状态1或2转移到状态2
            if dp[i-1][1] != -1 or dp[i-1][2] != -1:
                dp[i][2] = max(dp[i]