题解：P12984 [GCJ 2022 #1A] Double or One Thing

yyz0526 · 2025-07-12 21:33:53 · 题解

思路

从左往右对字符串 S 进行高亮操作，使结果为所有可能的字符串中字典序最小的一个。其中高亮共有 3 种情况：

代码

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int main(){
    int T;
    cin>>T;
    for(int i=1;i<=T;i++){
        s1="";
        s2="";
        cin>>s1;
        int len=s1.length();
        for(int j=0;j<len-1;j++){
            if(s1[j]<s1[j+1]){ // 第一种情况。
                s2+=s1[j];
                s2+=s1[j];
            }else if(s1[j]>s1[j+1]){ // 第二种情况。
                s2+=s1[j];
            }else{ // 第三种情况。
                int k=j;
                while(s1[j]==s1[k]){
                    k++;
                }
                if(s1[j]<s1[k]){
                    s2+=s1[j];
                    s2+=s1[j];
                }else{
                    s2+=s1[j];
                }
            }
        }
        s2+=s1[len-1]; // 加上最后一个没判断的字符。
        cout<<"Case #"<<i<<": "<<s2<<endl;
    }
    return 0;
}