[NOIP 2007 提高组] 字符串的展开

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

逐字符扫描字符串，遇到减号时按可展开性、字符变换、重复次数和正逆序规则做分类模拟。

OJ: luogu

题目 ID: P1098

难度:普及/提高-

标签:字符串模拟python

日期: 2026-06-19 10:06

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

给定参数 p1,p2,p3 和一个字符串。字符串中某些减号可以展开成中间的连续字符；展开时还要控制大小写、重复次数和正逆序。

思路

从左到右扫描字符串。普通字符直接加入答案。遇到 - 时，检查它左右两边字符：

  • 两边同为数字或同为小写字母；
  • 右边字符 ASCII 严格大于左边字符。

不满足则保留 -。满足时枚举中间字符，不包括两端字符：

text
ord(left)+1 ... ord(right)-1

再按 p3 决定是否反转顺序，按 p1 决定输出原字符、大写或 *，按 p2 决定重复次数。

Python 知识

  • /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：字符串支持下标访问、isdigit()、islower()。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：构造长答案时用列表收集片段再 join。
  • ord() 和 chr() 可以在字符和 ASCII 编码之间转换。
  • chars.reverse() 原地反转列表。

代码

python
def same_expand_type(left, right):
    return (left.isdigit() and right.isdigit()) or (
        left.islower() and right.islower()
    )


def expand_middle(left, right):
    if not same_expand_type(left, right) or ord(right) <= ord(left):
        return "-"

    chars = [chr(code) for code in range(ord(left) + 1, ord(right))]
    if p3 == 2:
        chars.reverse()

    result = []
    for ch in chars:
        if p1 == 3:
            result.append("*" * p2)
        elif p1 == 2 and ch.islower():
            result.append(ch.upper() * p2)
        else:
            result.append(ch * p2)
    return "".join(result)


p1, p2, p3 = map(int, input().split())
s = input().strip()
answer = []

for i, ch in enumerate(s):
    if ch == "-" and 0 < i < len(s) - 1:
        answer.append(expand_middle(s[i - 1], s[i + 1]))
    else:
        answer.append(ch)

print("".join(answer))

复杂度

设原串长度为 n，展开后新增字符总数为 L，时间复杂度是 O(n+L)O(n+L)，空间复杂度是 O(n+L)O(n+L)。

总结

本题关键是先判断减号是否有资格展开，再处理大小写、星号、重复和顺序。把展开逻辑封装成函数可以减少主循环分支。