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

知识点

字符串处理、分类讨论、模拟

解题思路

逐字符扫描原串，只有连字符两侧同为数字或小写字母且严格递增时才展开。枚举两端之间的字符，按p3决定方向，按p1转为大写、小写或星号，并重复p2次。其余字符原样输出，两端字符由普通扫描各输出一次。

正确性说明

合法展开的判定与题意完全对应。每个普通字符保留，合法连字符恰被其规定的中间字符序列替换；中间字符不含两端，方向、重复和字符类型依参数唯一确定。因此拼接后的整体字符串正确。

易错点

相邻字符只删除横杠；左右相等或降序要保留；连续横杠或数字字母混搭不能展开；判断使用原始邻居。

复杂度

时间O(L·26·p2)，输出空间同量级。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int p1,p2,p3;string s;cin>>p1>>p2>>p3>>s;for(int i=0;i<(int)s.size();i++){bool ok=false;if(s[i]=='-'&&i&&i+1<(int)s.size()){char a=s[i-1],b=s[i+1];bool same=(a>='0'&&a<='9'&&b>='0'&&b<='9')||(a>='a'&&a<='z'&&b>='a'&&b<='z');ok=same&&a<b;if(ok){string mid;for(char c=a+1;c<b;c++)mid+=c;if(p3==2)reverse(mid.begin(),mid.end());for(char c:mid){if(p1==3)c='*';else if(p1==2&&c>='a'&&c<='z')c=c-'a'+'A';for(int j=0;j<p2;j++)cout<<c;}}}if(!ok)cout<<s[i];}cout<<'\n';}