P1098 [NOIP 2007 提高组] 字符串的展开——题解

解题思路

顺序扫描字符串。遇到减号时检查左右字符是否满足同类且递增。满足时生成两端之间的字符序列，按 $p_1$ 转换并重复 $p_2$ 次，再根据 $p_3$ 决定是否整体逆序；不满足时直接保留减号。

复杂度分析

设展开后字符串长度为 $L$，时间复杂度和空间复杂度均为 $O(L)$。

易错点

逆序针对整个填充序列；减号两端字符由原扫描过程保留，不能重复输出。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int p1,p2,p3;string s;cin>>p1>>p2>>p3>>s;
    string ans;
    for(int i=0;i<(int)s.size();i++){
        if(s[i]=='-'&&i>0&&i+1<(int)s.size()){
            char l=s[i-1],r=s[i+1];
            bool same=(isdigit((unsigned char)l)&&isdigit((unsigned char)r))||(islower((unsigned char)l)&&islower((unsigned char)r));
            if(same&&l<r){
                if(r==l+1) continue;
                string mid;
                for(char c=l+1;c<r;c++){
                    char z=c;
                    if(p1==2&&islower((unsigned char)z)) z=toupper(z);
                    if(p1==3) z='*';
                    mid.append(p2,z);
                }
                if(p3==2) reverse(mid.begin(),mid.end());
                ans+=mid;continue;
            }
        }
        ans+=s[i];
    }
    cout<<ans<<'\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int p1,p2,p3;string s;cin>>p1>>p2>>p3>>s; string ans; for(int i=0;i<(int)s.size();i++){ if(s[i]'-'&&i>0&&i+1<(int)s.size()){ char l=s[i-1],r=s[i+1]; bool same=(isdigit((unsigned char)l)&&isdigit((unsigned char)r))||(islower((unsigned char)l)&&islower((unsigned char)r)); if(same&&l<r){ if(rl+1) continue; string mid; for(char c=l+1;c<r;c++){ char z=c; if(p12&&islower((unsigned char)z)) z=toupper(z); if(p13) z='*'; mid.append(p2,z); } if(p3==2) reverse(mid.begin(),mid.end()); ans+=mid;continue; } } ans+=s[i]; } cout<<ans<<'\n'; return 0; }