526互联

Educational Codeforces Round 149 (Rated for Div.2) 题解 A~D

发布时间 2023-05-28 18:06:42作者: 叁纔

A. Grasshopper on a Line

题目大意

给定两个整数 \(x\) 和 \(k\)，我们需要规划一条路线，从 \((0,0)\) 走到 \((0, x)\)，同时满足我们每次走的距离不能整除 \(k\) 。

解题思路

首先我们可以考虑到如果总长度 \(x\) 就不能整除 \(k\)，那么直接走 \(x\) 长度直接到达终点即可。如果 \(x\) 可以整除 \(k\)，那么我们不妨将 \(x\) 划分为两个部分，第一个部分是 \((0, k + 1)\)，第二个部分是 \((k + 2, x)\)。显然 \(k+1\) 不能整除 \(k\)，而由于 \(x\) 整除 \(k\)，那么 \(x-(k + 1)\) 也不能整除 \(k\)，满足题述条件。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
    int x, k;
    cin >> x >> k;
    if (x % k) {
        cout << 1 << endl;
        cout << x << endl;
    } else {
        cout << 2 << endl;
        cout << k + 1 << ' ' << x - (k + 1) << endl;
    }
}

signed main() {
    ios;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

B. Comparison String

题目大意

给定一个仅由>和<组成的长度为 \(n\) 的字符串，代表一个有 \(n + 1\) 的元素的数组相邻元素间的大小关系。现在需要求这个数组中，不同的元素最少有几种。

解题思路

既然要求最少有几种，那么我们不妨思考一下在什么限制条件下才必须是不同的元素。很显然，是<<<<或者>>>>>>这样的连续相同的关系符，这样可以强制限定这一串的数不相等。而对于<<<>><<<这样的，每次变换关系符号，都必然可以利用先前出现过的数来组成数组。那么问题其实就转化为了最长连续相同字符的长度加一了。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
    int n;
    string s;
    cin >> n >> s;
    LL cnt = 1;
    LL res = 1;
    for (int i = 1; i < n; ++i) {
        if (s[i] == s[i - 1]) {
            cnt++;
        } else {
            cnt = 1;
        }
        res = max(cnt, res);
    }
    cout << res + 1 << endl;
}

signed main() {
    ios;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

C. Best Binary String

题目大意

给定一个仅含有0 1 ?三种字符的字符串，现在需要将?替换成0或者1，同时定义一种操作：选取字符串中某一连续区间，将这一个区间倒转。问将原串替换后得到的串转换为非递减序列需要的操作数最小为多少。

解题思路

非递减序列实际上要求的就是000000111111这种串，我们选取的区间只能是连续的，所以可以发现形如01010这种序列操作次数一定比01110多，那么对于01?10这样的，就应当尽量凑连续的1。而对于01?01这样的，?两测0 1数量一致，取哪一个都没有影响。所以我们可以让处在中间的?替换成它前面的字符，如果第一个字符就是?，为了减少逆序次数，可以替换为0，这样就可以得到操作数最小的串了。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '?') {
            if (!i) {
                s[i] = '0';
            } else {
                s[i] = s[i - 1];
            }
        }
    }
    cout << s << endl;

}

signed main() {
    ios;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

D. Bracket Coloring

题目大意

给定一个括号序列，定义关于括号序列的“美丽”的定义：如果它是匹配的，或者它逆序后是匹配的即可。

现在问给定的括号序列能否使用某种方式染色，使得每种颜色的序列都是”美丽“序列。

如果可以，输出染色方案。

解题思路

首先我们需要知道什么情况下不能染色成功，那就是无论如何都没办法匹配序列，由于本题逆序也可以匹配，那么不能染色的条件只有左右括号数量不一样。

判断完这个之后，我们可以发现，如果序列不能正向匹配，那么抽离它正向匹配的部分之后，剩下的恰好就是逆向匹配的部分。这是必然的，否则左右括号数量不一致。那么我们可以开两个栈模拟，使用一个数组存栈序答案（染色方案）。同时处理什么时候是一个栈存，什么时候是两个栈存即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
    int n;
    string s;
    cin >> n >> s;
    if (n & 1) {
        cout << -1 << endl;
        return;
    }
    int c1 = 0, c2 = 0;
    for (char i : s) {
        if (i == '(') {
            c1++;
        } else {
            c2++;
        }
    }
    if (c1 != c2) {
        cout << -1 << endl;
        return;
    }
    stack<int> stk1, stk2;
    vector<int> v;
    bool flag1 = false, flag2 = false;
    for (char i : s) {
        if (i == '(') {
            if (!stk2.empty()) {
                v.push_back(2);
                stk2.pop();
            } else {
                stk1.push(0);
                flag2 = true;
                v.push_back(1);
            }
        } else if (i == ')' && !stk1.empty()) {
            stk1.pop();
            v.push_back(1);
        } else if (i == ')') {
            stk2.push(0);
            flag1 = true;
            v.push_back(2);
        }
    }
    if (!flag1 || !flag2) {
        cout << 1 << endl;
        for (int i = 1; i <= n; ++i) {
            cout << 1 << ' ';
        }
        cout << endl;
    } else {
        cout << 2 << endl;
        for (auto i : v) {
            cout << i << ' ';
        }
        cout << endl;
    }
}

signed main() {
    ios;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}