题目链接

REAL746 字符串和声！

题目描述

小歪正在学习字符串和声。字符串由小写字母、连接线 - 和竖线 | 构成。竖线 | 用来划分小节。例如，|do-do-re|re---| 代表两个小节。

字符串的和声规则如下： 和声的小节数量和各小节长度与原字符串一致。唯一的区别是，和声会比原字符串晚 个长度单位出现。具体操作为：

  1. 在每一个小节的内容前加上 条下划线 _。
  2. 截取新字符串的前 位（ 为原小节内容长度），得到该小节的和声。
  3. 和声未出现时使用下划线 _ 替代空白位置。

例如，当 时，对于小节内容 do-do-re（长度为8），先变为 __do-do-re，再截取前8位，得到和声 __do-do-。

思路分析

本题是一个字符串处理的模拟题。核心任务是正确地解析输入字符串，识别出由 | 分隔的各个“小节”，然后对每个小节的内容应用题目给定的“和声”变换规则。

考虑到输入可能包含多行，并且需要保持输出格式与输入一致，最稳妥的策略是逐行读取和处理。

内存优化

一个关键的陷阱是延迟长度 （题目中为 ）的最大值可达 。如果直接构造一个含有 个下划线的字符串，将会导致内存超限。

正确的做法是分析变换的最终结果：对于一个长度为 的小节内容 ：

  • 如果 ，那么变换后的结果就是由 个下划线组成的字符串。
  • 如果 ，那么变换后的结果是由 个下划线和 的前 个字符组成的字符串。

通过这种分情况讨论的方式，我们避免了创建超长字符串，从而解决了内存问题。

具体步骤如下：

  1. 读取整数 和 。
  2. 循环读取输入的每一行字符串。
  3. 对于每一行，按 | 分割成多个子串。
  4. 对于每个小节内容 ，获取其长度 ，然后根据上述优化逻辑生成变换后的内容。
  5. 将所有变换后的内容重新用 | 连接起来，形成最终的输出行，并打印。

例如，对于输入行 |do-do-re|re---| 和 ：

  • 按 | 分割得到 ["", "do-do-re", "re---", ""]。
  • 处理 "do-do-re"：长度 ，。，结果是 个 _ 加上 "do-do-re" 的前 个字符 do-do-，即 __do-do-。
  • 处理 "re---"：长度 ，。，结果是 个 _ 加上 "re---" 的前 个字符 re-，即 __re-。
  • 重新组合得到 |__do-do-|__re-|。

代码

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, k;
    cin >> n >> k;

    string line;
    // 使用 cin >> line 读取被空格或换行符分隔的每个音乐片段字符串
    while (cin >> line) {
        stringstream ss(line);
        string segment;
        string output_line = "";

        // 每行的首末均为竖线，所以第一个字符总是 '|'
        output_line += '|';
        
        // getline 会消耗掉第一个'|'，所以我们从第二个开始处理
        getline(ss, segment, '|'); // consume the part before the first real segment

        while (getline(ss, segment, '|')) {
            int len = segment.length();
            if (k >= len) {
                output_line += string(len, '_');
            } else {
                output_line += string(k, '_');
                output_line += segment.substr(0, len - k);
            }
            output_line += '|';
        }
        
        cout << output_line << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long k = sc.nextLong();

        while (sc.hasNext()) {
            String line = sc.next();
            // 按'|'分割。对于"|a|b|"，会得到["", "a", "b", ""]
            String[] parts = line.split("\\|", -1); 
            
            StringBuilder sb = new StringBuilder();
            // parts[0]是'|'之前的部分，总是空的。我们从parts[1]开始处理真正的小节。
            for (int i = 1; i < parts.length - 1; i++) {
                sb.append("|");
                String measure = parts[i];
                int len = measure.length();
                
                if (k >= len) {
                    for (int j = 0; j < len; j++) {
                        sb.append('_');
                    }
                } else {
                    for (int j = 0; j < k; j++) {
                        sb.append('_');
                    }
                    sb.append(measure.substring(0, (int)(len - k)));
                }
            }
            sb.append("|"); // 添加最后一个'|'
            System.out.println(sb.toString());
        }
    }
}

import sys

def solve():
    try:
        # 读取 n 和 k
        line = sys.stdin.readline()
        if not line: return
        n, k = map(int, line.split())
    except (IOError, ValueError):
        return

    # 逐行读取音乐字符串
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        
        # 按'|'分割，对于"|a|b|"，会得到['', 'a', 'b', '']
        parts = line.split('|')
        
        transformed_parts = []
        # parts[1:-1]是实际的小节内容
        for part in parts[1:-1]:
            original_len = len(part)
            if k >= original_len:
                transformed_parts.append('_' * original_len)
            else:
                # 拼接 k 个 '_' 和 截取后的原小节内容
                transformed_parts.append('_' * k + part[:original_len - k])
        
        # 重新组合成一行输出
        result = '|' + '|'.join(transformed_parts) + '|'
        print(result)

solve()

算法及复杂度

  • 算法：字符串模拟（内存优化）
  • 时间复杂度：，其中 是输入所有字符串的总长度。我们只需要遍历每个字符一次来进行分割、变换和重组。
  • 空间复杂度：，其中 是最长一行的长度。我们每次只处理一行，因此空间消耗与最长行的长度成正比。