首页 > 其他 > 详细

Codeforces Round #657 (Div. 2) A. Acacius and String(字符串模拟)

时间:2020-07-20 17:30:49      阅读:82      评论:0      收藏:0      [点我收藏+]

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

题意

给出一个由 ‘?‘ 和小写字母组成的字符串,可以将 ‘?‘ 替换为小写字母,判断是否存在一种替换方案使得字符串只包含一个 ‘abacaba‘ 子串。

题解

首先计算原字符串中所求子串的个数:

  • 如果个数多于一,则不存在满足要求的替换方案
  • 如果个数等于一,将所有 ‘?‘ 替换为 ‘abc‘ 外的字母即可
  • 如果个数少于一,判断是否有可以替换的子串,以及替换后是否只有一个子串,如 ‘abaca?acaba‘ 替换后有两个子串

代码

#include <bits/stdc++.h>
using namespace std;
const string str = "abacaba";

bool can_replace(string s) {
    for (int i = 0; i < str.size(); ++i) 
        if (s[i] != str[i] and s[i] != ?)
            return false;
    return true;
}

int count_str(string s) {
    int res = 0;
    for (int i = 0; i + str.size() - 1 < s.size(); ++i)
        if (s.substr(i, str.size()) == str)
            ++res;
    return res;
}

void solve() {
    int n; string s; cin >> n >> s;
    int cnt = count_str(s);
    if (cnt > 1) {
        cout << "No" << "\n";
    } else if (cnt == 1) {
        cas:;
        for (char &c : s)
            if (c == ?) c = z;
        cout << "Yes" << "\n" << s << "\n";
    } else {
        for (int i = 0; i + str.size() - 1 < s.size(); ++i) {
            string t = s.substr(i, str.size());
            if (can_replace(t)) {
                s.replace(i, str.size(), str);
                if (count_str(s) == 1) goto cas;
                s.replace(i, str.size(), t);
            }
        }
        cout << "No" << "\n";
    }    
}

int main() {
    int t; cin >> t;
    while (t--) solve();
}

 

Codeforces Round #657 (Div. 2) A. Acacius and String(字符串模拟)

原文:https://www.cnblogs.com/Kanoon/p/13345655.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!