Beautiful String

Codeforces Round #604 (Div. 2)

题目链接:https://codeforces.com/contest/1265/problem/A

题目描述:

如果没有两个连续的字符是相等的,则称字符串为beautiful。例如,“ababcb”、“a”和“abab”是漂亮的字符串,而“aaaaaa”、“abaa”和“bb”不是。构造一个漂亮的字符串。有一个字符串s,只由字符“a”、“b”、“c”和“?”组成。要用'a', 'b'或'c'其中一个字符替换每个字符'?',这样的结果字符串是美丽的。更正式地说,在替换了所有字符之后?,当si≠si+1时,应满足1≤i≤|s|−1,其中|s|为字符串s的长度。

输入

第一行包含正整数t(1≤t≤1000)——测试用例的数量。接下来的t行包含测试用例的描述。
每一行包含一个非空字符串,该字符串仅由字符“a”、“b”、“c”和“?”组成。
保证在每个测试用例中,字符串s至少有一个字符'?'。所有测试用例中字符串长度s的总和不超过1e5。

输出

对于输入中的每个测试用例,请按照以下格式打印答案:
如果无法创建一个漂亮的字符串,请打印“-1”(不带引号);
否则,打印出美丽的字符串后,取代所有'?的字符。如果有多个答案,您可以打印任何一个。

例子

1

思路:

给你一个字符串,首先判断元素是不是一个‘?’,如果是‘?’需要让它与前后位置的字符不一样,如果‘?’在字符串首位只需让它与后一位(后一位不为‘?’的情况) 不同即可,如果‘?’在字符串末尾只需让它与前一位不同即可(前一位不可能出现是‘?’的情况),用一个bool vis[4]标记'a','b','c'是否被使用过。

代码:

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
const int maxn=1e5+5;
char a[maxn];
bool vis[4];
int main(){
    int t;
    #ifdef HH
    freopen("G:/input.txt","r",stdin);
    #endif // HH
    scanf("%d",&t);
    int res;
    while(t--){
        scanf("%s",a);
        int i,j;
        i=0;
        j=strlen(a);
        res=0;
        while(i<j){
            memset(vis,0,sizeof(vis));
            if(a[i]=='?'){
                if(i>0){
                    vis[a[i-1]-'a']=1;
                }
                if(i<j-1&&a[i+1]!='?'){
                    vis[a[i+1]-'a']=1;
                }
                for(int k=0;k<3;k++){
                    if(vis[k]==0){
                        a[i]=k+'a';
                    }
                }
                i++;
            }
            else{
                if(a[i]==a[i+1]){
                    res=-1;
                    break;
                }
                else i++;
            }
        }
        if(res==-1){
            cout<<-1<<endl;
        }
        else cout<<a<<endl;
    }
    return 0;
}
Last modification:December 6th, 2019 at 11:28 pm
如果觉得我的文章对你有用,请随意赞赏