Educational Codeforces Round 153 (Rated for Div. 2) A-A题解

Sleeping_Knight / 2023-08-21 / 原文

A. Not a Substring

题解

对于这个题，我们可以考虑两种可能的连续的子串：

有两个及以上的相同的字符，比如(((，()))，那么我们就需要尽可能地构造出连续不相同的字符串，比如()()()就非常符合我们的要求，每一对都不一样。
有两个及以上的不相同的字符，比如)()(，那么我们就可以按照上面的想法，尽可能地构造出连续相同的字符串，那么((((()))))就是满足条件的最佳的字符串，因为它只有一对不相同的字符，而这一对是必须需要的。

所以呢，对于每个长度为n的串s，我们只需要构造出长度为2n的类似()()的串和类似(())的串，然后判断s是不是它们的子串，判断的方法就是使用cpp的string的find()函数查找

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SZ(x) (int)(x.size())
#define FOR(i,x,y) for (int i = (x),_##i = (y);i < _##i;i++)
#define FORD(i,x,y) for (int i = (x),_##i = (y);i > _##i;i--)
inline void solve();
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t = 1;
    cin >> t;
    FOR (id, 1, t + 1) {solve();}
    return 0;
}
inline void solve() {
    string s, s1 = "", s2 = "";
    cin >> s;
    int n = SZ(s);
    FOR (i, 0, n) { // i 从 0 到 n - 1
        // 构造出类似()()的字符串s1
        s1 += "()";
    }
    FOR (i, 0, 2 * n) { // i 从 0 到 2 * n - 1，
        // 构造出类似(())的字符串s2
        if (i < n) {
            s2 += "(";
        } else {
            s2 += ")";
        }
    }
    if (s1.find(s) == s1.npos) {    // 如果s不是s1的子串
        cout << "YES\n";
        cout << s1 << "\n";
    } else if (s2.find(s) == s2.npos) { // 如果s不是s2的子串
        cout << "YES\n";
        cout << s2 << "\n";
    } else {    // 否则就是不存在了
        cout << "NO\n";
    }
}