✅ 春招备战指南 ✅

💡 学习建议：

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

互联网必备刷题宝典🔗

01. 彩灯装饰计划

问题描述

小基有一串由不同颜色组成的彩灯串，他想要按照一个特殊的规则来装饰这串彩灯：

首先，他将彩灯按照以下方式从上到下排列：

• 第1行放置1个彩灯
• 第2行放置2个彩灯
• 第3行放置3个彩灯
• 以此类推...

当剩余的彩灯数量不足以满足当前行需要放置的彩灯数量时，将剩余的彩灯全部放在最后一行。

现在，小基想要知道，如果从上到下依次取出每一行的第一个彩灯的颜色，这些颜色组成的彩灯串会是什么样子。

输入格式

一行，一个仅由小写字母组成的字符串 ，表示彩灯串的颜色序列，其中每个字母代表一个彩灯的颜色。字符串长度满足 。

输出格式

一行，一个字符串，表示从上到下依次取出每一行第一个彩灯的颜色组成的彩灯串。

样例输入

样例 输入 输出 解释说明

样例1	helloworld	helo	按照规则排列后： h el low orld 取每行第一个彩灯的颜色：helo

数据范围

• 
• 字符串 仅包含小写字母

题解

这道题目的关键在于理解彩灯的排列规则。对于长度为 的彩灯串，我们需要：

1. 确定每一行应该放置多少个彩灯
2. 记录每一行的第一个彩灯的颜色
3. 将这些颜色按顺序连接起来

具体实现时，我们可以：

1. 使用一个指针 记录当前处理到的位置
2. 对于第 行，取出 个彩灯（如果剩余彩灯不足，则全部取出）
3. 记录每行第一个彩灯的颜色
4. 最后将所有记录的颜色连接起来

时间复杂度为 ，因为我们需要遍历整个彩灯串一次。对于给定的数据范围，这个复杂度是可以接受的。

参考代码

• Python

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

def get_first_chars(lamp_str):
    n = len(lamp_str)
    first_chars = []
    curr_pos = 0
    row_num = 1
    
    while curr_pos < n:
        first_chars.append(lamp_str[curr_pos])
        curr_pos += row_num
        row_num += 1
    
    return ''.join(first_chars)

def main():
    lamp_str = input()
    print(get_first_chars(lamp_str))

if __name__ == "__main__":
    main()

• Cpp

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

string get_first_chars(const string& lamp_str) {
    int n = lamp_str.length();
    string first_chars;
    int curr_pos = 0, row_num = 1;
    
    while (curr_pos < n) {
        first_chars += lamp_str[curr_pos];
        curr_pos += row_num;
        row_num++;
    }
    
    return first_chars;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string lamp_str;
    cin >> lamp_str;
    cout << get_first_chars(lamp_str) << endl;
    
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    private static String getFirstChars(String lampStr) {
        int n = lampStr.length();
        StringBuilder firstChars = new StringBuilder();
        int currPos = 0, rowNum = 1;
        
        while (currPos < n) {
            firstChars.append(lampStr.charAt(currPos));
            currPos += rowNum;
            rowNum++;
        }
        
        return firstChars.toString();
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String lampStr = sc.nextLine();
        System.out.println(getFirstChars(lampStr));
        sc.close();
    }
}

02. 礼物包装计划

问题描述

小柯准备为她的朋友们准备一些礼物。她有 个不同的礼物，每个礼物都有其独特的价值。小柯想要选择一些礼物进行精美的包装，她的包装计划得分计算方式为：所选礼物中价值最小的那个礼物的价值，加上她选择的礼物数量。

请你帮小柯计算一下，她最高可以得到多少分。

输入格式

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

接下来对于每组测试数据，输入包含两行。

第一行一个正整数 ，表示礼物的数量。

第二行 个整数 ，表示每个礼物的价值。

（保证所有测试数据中 的总和不超过 。）

输出格式

输出 行，每行一个整数表示答案。

样例输入

样例 输入 输出 解释说明

样例1	1 5 3 5 4 2 2	7	小柯可以选择包装所有礼物，得分为 2 + 5 = 7 最大。

数据范围

• 
• 
• 
• 所有测试数据中 的总和不超过

题解

这道题目的关键在于理解得分的计算方式。对于任意一个选择方案，得分由两部分组成：所选礼物中价值最小的那个礼物的价值，加上选择的礼物数量。

考虑一个简单的贪心策略：对于每个礼物，我们都可以尝试将其作为最小价值，然后选择所有价值大于等于它的礼物。这样，对于每个礼物 ，我们都可以计算一个可能的得分：，其中 是价值大于等于 的礼物数量。

具体实现时，我们可以：

1. 先将所有礼物按价值排序
2. 对于每个礼物，计算将其作为最小价值时的得分
3. 取所有可能得分中的最大值

时间复杂度为 ，主要来自排序的开销。对于给定的数据范围，这个复杂度是可以接受的。

参考代码

• Python

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

def calc_max_score(gift_vals):
    gift_vals.sort()
    max_score = 0
    n = len(gift_vals)
    
    for i in range(n):
        curr_score = gift_vals[i] + (n - i)
        max_score = max(max_score, curr_score)
    
    return max_score

def main():
    T = int(input())
    for _ in range(T):
        n = int(input())
        gift_vals = list(map(int, input().split()))
        print(calc_max_score(gift_vals))

if __name__ == "__main__":
    main()

• Cpp

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

int calc_max_score(vector<int>& gift_vals) {
    sort(gift_vals.begin(), gift_vals.end());
    int max_score = 0;
    int n = gift_vals.size();
    
    for (int i = 0; i < n; i++) {
        int curr_score = gift_vals[i] + (n - i);
        max_score = max(max_score, curr_score);
    }
    
    return max_score;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> gift_vals(n);
        for (int i = 0; i < n; i++) {
            cin >> gift_vals[i];
        }
        cout << calc_max_score(gift_vals) << endl;
    }
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    private static int calcMaxScore(int[] giftVals) {
        Arrays.sort(giftVals);
        int maxScore = 0;
        int n = giftVals.length;
        
        for (int i = 0; i < n; i++) {
            int currScore = giftVals[i] + (n - i);
            maxScore = Math.max(maxScore, currScore);
        }
        
        return maxScore;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            int n = sc.nextInt();
            int[] giftVals = new int[n];
            for (int i = 0; i < n; i++) {
                giftVals[i] = sc.nextInt();
            }
            System.out.println(calcMaxScore(giftVals));
        }
        
        sc.close();
    }
}

03. 宝石能量优化

问题描述

小兰有一串神奇的宝石，每颗宝石都有其独特的能量值。宝石的能量值等于它的能量因子数量（能量因子是指质因子的数量）。

现在，小兰想要移除一段连续的长度为 的宝石，使得剩下的宝石的能量总和最大。请你帮她计算这个最大能量总和。

输入格式

第一行两个整数 , ，分别表示宝石的数量和需要移除的连续宝石数量。

接下来一行 个正整数 ，表示每颗宝石的能量值。

输出格式

输出一个整数，表示移除一段长度为 的连续宝石后，剩余宝石的能量总和的最大值。

样例输入

样例 输入 输出 解释说明

样例1	5 2 6 2 4 1 3	4	宝石的能量因子数量： 6：2个（2和3） 2：1个（2）