专栏文章

AT_arc157_b 题解

II_like_magic
AT_arc157_b题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqm6ums
此快照首次捕获于
2025/12/04 07:04
3 个月前
此快照最后确认于
2025/12/04 07:04
3 个月前
查看原文
这道题其实不难。
首先我们简化问题。
用 cntXcnt_X 表示字符串中字符 X 的个数，
如果 k≤cntXk \le cnt_X，那么我们显然要从字符串中找到 kk 个 X，并将它们变为 Y；
如果 k>cntXk > cnt_X，那么我们可以将问题变为：将字符串中每一位反转，再从新字符串中选取 n−kn - k 个 X 变为 Y。
然后再来解决问题。
下文相邻的一对 Y 代表两个 Y 之间只有 X，或什么字符都没有。
首先特判两种情况：
显而易见地，
如果 cntX=ncnt_X = n，那么直接输出 k−1k - 1。
如果 cntX=0cnt_X = 0，那么直接输出 n−k−1n - k - 1。
接下来，我们发现，对于两个相邻的 Y，如果它们之间隔着 aa 个 X，那么，我们用掉 aa 次翻转就能对答案增加 a+1a + 1 的贡献。
举例：
对于 YXXY，原先这一段的答案为 00，翻转中间的 22 个 X，答案变为 33。
对于 YXY，原先这一段的答案为 00，翻转中间的 11 个 X，答案变为 22。
对于 YY，把原先这一段的答案当作 00，翻转中间的 00 个 X，答案变为 11。
可见，对于任意的间隔 aa，全部翻转后都能对答案造成 a+1a + 1 的贡献。
因此，我们需要优先翻转间隔小的一段 X，以获得最多的翻转次数，让答案尽可能大。
扫一遍整个字符串，依次把相邻的两个 Y 之间的 X 数量记录下来，最后再从小到大排序。
记得到的序列为 AA，遍历这个序列，如果当前 Ai≤kA_i \le k，那么消耗 AiA_i 次翻转机会，k−Ai→kk - A_i\to k，并把 AnsAns 增加 Ai+1A_i + 1；如果 Ai>kA_i > k，那么我们无法把一整段 X 翻转完，那么最优的一定是从左到右依次翻转，直到翻转次数用完，而每次对答案的贡献是 11，因此这种情况 AnsAns 直接加 kk。
如果遍历完了这个序列，kk 还有剩余，那么显而易见，答案也是直接加 kk。
代码：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 200005; // 数据范围
int n, k; // n 代表字符串长度，k 代表翻转次数
string s; // s 为输入的字符串
int cntX; // 统计输入的字符串中 X 的个数
int ans; // 记录答案的变量，初值为 0
vector<int> dis; // 两个相邻 Y 之间 X 个数的序列
int main() {
    cin >> n >> k >> s; // 读入 n, k, s
    for(int i = 0; s[i]; i ++) { // 遍历整个字符串
        if(s[i] == 'X') cntX ++; // 统计 X 的个数 
    }
    if(cntX == 0) { // 特判 1
        printf("%d\n", max(n - k - 1, 0)); // 显而易见的答案
        return 0; // 直接退出程序
    }
    if(cntX == n) { // 特判 2
        printf("%d\n", max(k - 1, 0)); // 显而易见的答案
        return 0; // 直接退出程序
    }
    if(cntX < k) { // 翻转整个字符串，n - k to k
        k = n - k; // 翻转次数也要翻转
        for(int i = 0; s[i]; i ++) {
            s[i] = 'X' + 'Y' - s[i]; // 翻转 s[i]
        }
    }
    int lst = -1; // 表示上一个 Y 的位置
    for(int i = 0; s[i]; i ++) {
        if(s[i] == 'Y') {
            if(lst != -1) { // 特判第一个 Y
                dis.push_back(i - lst - 1); // 两个相邻的 Y 之间 X 的数量
            }
            lst = i; // 更新上一个 Y 的位置
        }
    }
    sort(dis.begin(), dis.end()); // 从小到大排序
    for(int i : dis) { // 遍历序列
        if(k >= i) {
            k -= i; // 使用 i 次翻转
            ans += 1 + i; // 对答案造成 i + 1 的贡献
        }
    }
    ans += k; // 使用剩下的 k 次翻转，对答案造成 k 的贡献
    printf("%d\n", ans); // 输出答案
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...