[NOIP2007-提高] 字符串的展开

GitHub跳转原题关系图返回列表

扫描每个减号，判定它是否满足展开条件（两侧同类且左 < 右），再按 p1/p2/p3 三个参数生成中间填充段，O(n) 模拟。

OJ: roj

题目 ID: 3557

难度:普及

标签:模拟字符串NOIPpython

创建: 2026-10-02 07:19

更新: 2026-10-06 13:52

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

给定 p1,p2,p3p_1,p_2,p_3 和一个仅含小写字母、数字、减号 - 的字符串 ss（∣s∣≤100|s|\le 100）。 扫描每个 -：若两侧同为小写字母或同为数字，且右侧 ASCII 严格大于左侧，则把减号替换成两端字符之间的序列，按 p1p_1（1小写/2大写/3星号）、p2p_2（每个字符重复次数）、p3p_3（1正序/2逆序）生成填充段；否则保留原字符。输出展开后的字符串。

思路

遍历字符串，对每个 - 检查两侧是否同类且左<右，满足则按 p1,p2,p3p_1,p_2,p_3 生成中间字符序列并拼接。p1=2p_1=2 时仅字母转大写，数字不变；p1=3p_1=3 时全部用 * 代替。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 07:19
# update_at: 2026-10-02 07:19
import sys
from typing import List

data = iter(sys.stdin.buffer.read().split())
p1, p2, p3 = int(next(data)), int(next(data)), int(next(data))  # 展开方式 / 重复个数 / 是否逆序
s = next(data).decode()  # 第 2 行待展开字符串，行内无空白字符，正好是一个 token


def expand(left: str, right: str) -> str:
    """展开 left-right 中间的片段：按 p1 决定填充形式，p2 决定每个字符重复几次，p3 决定是否逆序。"""
    if p1 == 3:  # 星号填充：个数 = 中间字符数 × p2
        return '*' * (p2 * (ord(right) - ord(left) - 1))
    seg = ''.join(chr(c) for c in range(ord(left) + 1, ord(right)))
    if p1 == 2 and left.isalpha():  # 只有字母子串才转大写，数字保持原样
        seg = seg.upper()
    if p3 == 2:
        seg = seg[::-1]
    return ''.join(ch * p2 for ch in seg)


def solve() -> None:
    """扫描每个减号：能展开就替换成展开结果，否则原样保留。"""
    res: List[str] = []
    for i, ch in enumerate(s):
        can_expand = (
            ch == '-'
            and 0 < i < len(s) - 1
            and ((s[i - 1].islower() and s[i + 1].islower())
                 or (s[i - 1].isdigit() and s[i + 1].isdigit()))
            and s[i - 1] < s[i + 1]  # 右边必须严格大于左边，否则保留减号
        )
        res.append(expand(s[i - 1], s[i + 1]) if can_expand else ch)
    print(''.join(res))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 13:52
 * update_at: 2026-10-06 13:52
 */
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

typedef long long ll;

ll p1, p2, p3; // 展开方式 / 重复个数 / 是否逆序
string s;

// 生成 left 与 right 之间的展开段（不包括两端）
string expand(char left, char right) {
    if (p1 == 3) {
        // 星号填充，个数 = 中间字符数 × p2
        return string(p2 * (right - left - 1), '*');
    }
    string seg;
    for (char c = left + 1; c < right; ++c) {
        char out = c;
        if (p1 == 2 && left >= 'a' && left <= 'z') {
            out = c - 'a' + 'A'; // 字母子串转大写
        }
        seg.append(p2, out); // 每个字符重复 p2 次
    }
    if (p3 == 2) {
        reverse(seg.begin(), seg.end()); // 逆序
    }
    return seg;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> p1 >> p2 >> p3;
    cin >> s;
    string res;
    for (size_t i = 0; i < s.size(); ++i) {
        if (s[i] == '-' && i > 0 && i + 1 < s.size()) {
            char l = s[i - 1];
            char r = s[i + 1];
            bool same_alpha = (l >= 'a' && l <= 'z' && r >= 'a' && r <= 'z');
            bool same_digit = (l >= '0' && l <= '9' && r >= '0' && r <= '9');
            if ((same_alpha || same_digit) && l < r) {
                res += expand(l, r);
                continue;
            }
        }
        res += s[i];
    }
    cout << res << '\n';
    return 0;
}