Codeforces Round 910 (Div. 2)

Shiroha白羽的博客

Shiroha · 2024-01-17 · via Shiroha白羽的博客

A. Milica and String

大致题意

有一个 A/B 组成的字符串，每次允许选择前 $n$ 个字母，将他们都变成 A/B，问最少的操作次数

思路

简单题，最简单的方式就是枚举每一种可能，计算结果是否符合预期就行

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k;
        cin >> n >> k;
        string str;
        str.reserve(n);
        cin >> str;
        int cntB = 0;
        for (int i = 0; i < n; ++i) cntB += str[i] == 'B';
        if (cntB == k) {
            cout << 0 << endl;
            continue;
        }        const bool useA = cntB > k;
        for (int i = 0; i < n; ++i) {
            if (cntB > k) {
                cntB -= str[i] == 'B';
            } else {
                cntB += str[i] != 'B';
            }
            if (cntB == k) {
                cout << 1 << endl;
                cout << i + 1 << ' ' << (useA ? 'A' : 'B') << endl;
                break;
            }
        }
    }
}

B. Milena and Admirer

大致题意

允许不断的差分一个数组中的值，问至少需要拆多少次，才能让数组非递减

思路

也比较简单，从后往前遍历，如果当前值比后面的值大，则均匀的拆成 $x$ 份，使得恰好比后面的值小或者相同即可

AC code

#define int long longvoid solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        int ans = 0;
        for (int i = n - 2; i >= 0; --i) {
            if (data[i] > data[i + 1]) {
                const int cut = data[i] / data[i + 1] + (data[i] % data[i + 1] == 0 ? 0 : 1);
                data[i] /= cut;
                ans += cut - 1;
            }
        }
        cout << ans << endl;
    }
}

C. Colorful Grid

大致题意

有一个棋盘，允许在棋盘的边上染色，然后使得从最左上角到最右下角的某一条路径长度恰好为 $k$ 的同时，路径上一定上红蓝间隔染色的

思路

即然可以重复点，那么最好的办法是找一个可以旋转的环，在里面转到足够多次就行。

因为需要红蓝间隔，那么必然最小的环就是 $4$ 个单位长度的格子，所以如果 $k$ 恰好是最短的距离加上 $4n$ 的话，就可以这样解决

但是还有一种情况，也就是不满足 $4n$ 的时候，例如 $3 \times 2$ 的方格，走 5 步，也是可以到达的（可以自己绘制一下）

故所以需要兼容上面的两种情况，我给出的一种解法如下

首先根据矩形的长边，旋选择左边或者右边的，然后固定将左上角绘制成上述形状，然后再补充移动到右下角的路径即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m, k;
        cin >> n >> m >> k;
        const int mi = n - 1 + m - 1;
        if (k < mi) {
            cout << "NO" << endl;
            continue;
        }        if (const int cut = k - mi; cut != 0 && cut % 2 == 1) {
            cout << "NO" << endl;
            continue;
        }
        if (n == 2 && m == 2) {
            if (k % 4 != 2) cout << "NO" << endl;
            else cout << "B\nB\nR R" << endl;
            continue;
        }
        vector<vector<char>> a(n), b(n - 1);
        for (auto& i: a) i.resize(m - 1);
        for (auto& i: b) i.resize(m);
        if (n >= m) {
            a[0][0] = a[1][0] = a[2][0] = b[0][0] = 'B';
            b[0][1] = b[1][0] = b[1][1] = 'R';
            for (int i = 1; i < m - 1; ++i) a[2][i] = a[2][i - 1] == 'R' ? 'B' : 'R';
            const char last = b[1][m - 1];
            b[1][m - 1] = a[2][m - 2];
            for (int i = 2; i < n - 1; ++i) b[i][m - 1] = b[i - 1][m - 1] == 'R' ? 'B' : 'R';
            b[1][m - 1] = last;
        } else {
            a[0][0] = b[0][0] = b[0][1] = b[0][2] = 'R';
            a[0][1] = a[1][0] = a[1][1] = 'B';
            for (int i = 1; i < n - 1; ++i) b[i][2] = b[i - 1][2] == 'R' ? 'B' : 'R';
            const char last = a[n - 1][1];
            a[n - 1][1] = b[n - 2][2];
            for (int i = 2; i < m - 1; ++i) a[n - 1][i] = a[n - 1][i - 1] == 'R' ? 'B' : 'R';
            a[n - 1][1] = last;
        }
        cout << "YES" << endl;
        for (const auto& i: a) {
            for (const auto& j: i) cout << (j ? j : 'R') << ' ';
            cout << endl;
        }
        for (const auto& i: b) {
            for (const auto& j: i) cout << (j ? j : 'R') << ' ';
            cout << endl;
        }
    }
}

D. Absolute Beauty

大致题意

有两个数组，允许交换 $b$ 数组中的两个值一次，问使得 $\sum^n_{i=1} \left | a_i - b_i \right |$ 最大的可能是多少

思路

首先得画几个图来理解，为了方便，此处先假定 $a_i < b_i$（后续可以证明可以恒定满足此等式）

那么可以得到主要有两种情况

可见，只有右边的情况是能够真正有意义的，有意义的部分是 $a_j - b_i$

那么就需要找到最大的 $a_j - b_i$ 即可

然后我们再来看看如何证明最开始说的 $a_i < b_i$。你可以尝试将图里的 $a,b$ 交换位置，你会发现对最终的结果没有影响

AC code

#define int long longvoid solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for (auto& i: a) cin >> i;
        for (auto& i: b) cin >> i;
        for (int i = 0; i < n; ++i) if (a[i] > b[i]) swap(a[i], b[i]);
        int mib = 0, maa = 0;
        for (int i = 0; i < n; ++i) {
            if (b[i] < b[mib]) mib = i;
            if (a[i] > a[maa]) maa = i;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) ans += abs(a[i] - b[i]);
        ans += max(0LL, 2 * (a[maa] - b[mib]));
        cout << ans << endl;
    }
}

E. Sofia and Strings

大致题意

有一个字符串 $a$，允许你无数次操作如下的两个方法其中之一

选择其中一个片段，进行排序
删掉一个指定的字符

问是否能够变成 $b$ 字符串

思路

这里的选择片段排序，实际上最有用的就是选择两个相邻的字母排序，这样就可以最小的改动的情况下，将一个值往前移动

而需要达成这个目标，就意味着每次移动的时候，前面的值都需要比当前值大，否则前面的值只能删除。

故可以考虑遍历 $b$ 的字母，找到当前可用的最小的在 $a$ 中的位置，并将前面的那些字符移动到后面（比当前字母大），或者删除

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m;
        cin >> n >> m;
        string sn, sm;
        sn.reserve(n);
        sm.reserve(m);
        cin >> sn >> sm;
        vector<queue<int>> v(26);
        for (int i = 0; i < n; ++i) v[sn[i] - 'a'].push(i);        bool flag = true;
        for (int i = 0; i < m; ++i) {
            if (v[sm[i] - 'a'].empty()) {
                flag = false;
                break;
            }
            int t = v[sm[i] - 'a'].front();
            v[sm[i] - 'a'].pop();
            for (int j = 0; j < sm[i] - 'a'; ++j) while (!v[j].empty() && v[j].front() < t) v[j].pop();
        }
        cout << (flag ? "YES" : "NO") << endl;
    }
}

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Shiroha白羽的博客

A. Milica and String

大致题意

思路

AC code

B. Milena and Admirer

大致题意

思路

AC code

C. Colorful Grid

大致题意

思路

AC code

D. Absolute Beauty

大致题意

思路

AC code

E. Sofia and Strings

大致题意

思路

AC code