蒟蒻求助，被今天 ARC 的第 2 题，折磨疯了，谁能帮忙看看么？

zhangjinxuan

题目：

给出由X，Y构成的长度N的字符串S。选择S中位于不同位置的K字符，如果选择的字符是X，则改成Y，如果是Y，则改成X。
请问修改K次后的字符串中Y彼此相邻的地方最大为多少，也就是有多少 i, 满足 1 <= i < n 并且 Si = Si+1 以及 Si == 'Y'

本人代码：

#include <bits/stdc++.h>
using namespace std;

int n, k;
char s[200011];
int ypos[500011], tot, dtot;
struct D {
        int l, r, va;
} d[500011];
bool fd[500011];

bool cmp(const D &a, const D &b) {
        if (b.l == 0 || b.r == n + 1) return 1;
        if (a.l == 0 || a.r == n + 1) return 0;
        return a.va < b.va;
}

int main() {
        scanf("%d%d%s", &n, &k, s + 1);
        //printf("\n%d", cmp({0, 2, 1}, {4, 7, 2}));
        //exit(0);
        if (k == 0) {
                for (int i = 1; i < n; ++i) {
                        if (s[i] == s[i + 1] && s[i] == 'Y') ++tot;
                }
                printf("%d", tot);
                return 0;
        }
        for (int i = 1; i <= n; ++i) {
                if (s[i] == 'Y') {
                        ypos[++tot] = i;
                }
        }
        if (tot == 0) {
                printf("%d", k - 1);
                return 0;
        }
        for (int i = 1; i < tot; ++i) {
                if (ypos[i + 1] - ypos[i] - 1 == 0) continue;
        ++dtot;
                d[dtot].l = ypos[i];
                d[dtot].r = ypos[i + 1];
                d[dtot].va = ypos[i + 1] - ypos[i] - 1;
        }
        if (ypos[1] != 0) {
                ++dtot;
                d[dtot].l = 0;
                d[dtot].r = ypos[1];
                d[dtot].va = ypos[1] - 1;
        }
        if (ypos[tot] != n) {
                ++dtot;
                d[dtot].l = ypos[tot];
                d[dtot].r = n + 1;
                d[dtot].va = n + 1 - ypos[tot] - 1;
        }
        sort(d + 1, d + dtot + 1, cmp);
        //for (int i = 1; i <= dtot; ++i) {
        //        printf("%d %d %d\n", d[i].l, d[i].r, d[i].va);
        //}
        for (int i = 1; i <= dtot && k; ++i) {
                for (int j = d[i].l + 1; j < d[i].r && k; ++j) {
                        //assert(s[j] == 'X');
                        s[j] = 'Y';
            assert(fd[j] == 0);
                        fd[j] = 1;
                        --k;
                }
        }
        int res = 0;
        for (int i = 1; i < n; ++i) {
                if (s[i] == s[i + 1] && s[i] == 'Y') {
                        ++res;
                }
        }
        //        puts(s + 1);
        if (k == 0) {
                printf("%d", res);
                return 0;
        }
        if (fd[1] == 0) {
                --res;
                --k;
        }
        if (fd[n] == 0 && k) {
                --res;
                --k;
        }
        for (int i = 2; i < n && k; ++i) {
                if (!fd[i]) {
                       fd[i] = 1;
                        res -= 2;
                        --k;
                }
        }
        printf("%d", res);
        return 0;
}/*
10 5
XYXYXXYYYX*/

题目链接：https://atcoder.jp/contests/arc157/tasks/arc157_b
测评链接：https://atcoder.jp/contests/arc157/submissions/39197616

求助，我调了 70 分钟都没想出来，思路就是类似贪心，能最短的把一串 'Y' 连起来，就优先考虑，如果后面还有多余的 K，还是贪心尽量少减少答案

是不是那个细节没注意啊，求助各位，或者给一个 Hack 数据也可以，谢谢

jhq999

10 10
YYYYYYYYYY

zhangjinxuan

jhq999 发表于 2023-2-25 23:12

#include <bits/stdc++.h>
using namespace std;

int n, k;
char s[200011];
int ypos[200011], tot, dtot;
struct D {
        int l, r, va;
        bool first;
} d[200011];
bool fd[200011];

bool cmp(const D &a, const D &b) {
        if (b.l == 0 || b.r == n + 1) return 1;
        if (a.l == 0 || a.r == n + 1) return 0;
        return a.va < b.va;
}

int main() {
        scanf("%d%d%s", &n, &k, s + 1);
        //printf("\n%d", cmp({0, 2, 1}, {4, 7, 2}));
        //exit(0);
        if (k == 0) {
                for (int i = 1; i < n; ++i) {
                        if (s[i] == s[i + 1] && s[i] == 'Y') ++tot;
                }
                printf("%d", tot);
                return 0;
        }
        for (int i = 1; i <= n; ++i) {
                if (s[i] == 'Y') {
                        ypos[++tot] = i;
                }
        }
        if (tot == 0) {
                printf("%d", k - 1);
                return 0;
        }
        for (int i = 1; i < tot; ++i) {
                if (ypos[i + 1] - ypos[i] - 1 == 0) continue;
                ++dtot;
                d[dtot].l = ypos[i];
                d[dtot].r = ypos[i + 1];
                d[dtot].va = ypos[i + 1] - ypos[i] - 1;
                d[dtot].first = 1;
        }
        sort(d + 1, d + dtot + 1, cmp);

        if (ypos[1] - 1) {
                ++dtot;
                d[dtot].l = 0;
                d[dtot].r = ypos[1];
                d[dtot].va = ypos[1] - 1;
                d[dtot].first = 0;
        }
        if (ypos[tot] != n) {
                ++dtot;
                d[dtot].l = ypos[tot];
                d[dtot].r = n + 1;
                d[dtot].va = n + 1 - ypos[tot] - 1;
                d[dtot].first = 0;
        }
        //for (int i = 1; i <= dtot; ++i) {
        //        printf("%d %d %d\n", d[i].l, d[i].r, d[i].va);
        //}
        for (int i = 1; i <= dtot && k; ++i) {
                for (int j = d[i].l + 1; j < d[i].r && k; ++j) {
                        //assert(s[j] == 'X');
                        s[j] = 'Y';
                        fd[j] = 1;
                        --k;
                }
        }
        int res = 0;
        for (int i = 1; i < n; ++i) {
                if (s[i] == s[i + 1] && s[i] == 'Y') {
                        ++res;
                }
        }
        //        puts(s + 1);
        if (k == 0) {
                printf("%d", res);
                return 0;
        }
        if (fd[1] == 0) {
                s[1] = 'X';
                --res;
                --k;
        }
        if (fd[n] == 0 && k) {
                s[n] = 'X';
                --res;
                --k;
        }
        for (int i = 2; i < n && k; ++i) {
                if (!fd[i]) {
                        s[i] = 'X';
                        --k;
                        if (s[i - 1] == 'Y') --res;
                        if (s[i + 1] == 'Y') --res;
                }
        }
        printf("%d", res);
        return 0;
}/*
10 5
XYXYXXYYYX*/

https://atcoder.jp/contests/arc157/submissions/39207198

会不会就是最后那一段代码的问题？

jhq999

zhangjinxuan 发表于 2023-2-26 08:06
https://atcoder.jp/contests/arc157/submissions/39207198

会不会就是最后那一段代码的问题？

10 9
XYYXXYXXYY


XYYXXYXXYY
YYYYYYYYYY
YXXYYYYYXX

zhangjinxuan

jhq999 发表于 2023-2-26 09:14

?

jhq999

zhangjinxuan 发表于 2023-2-26 09:24
?

10 9
XYYXXYXXYY
3

你的结果是3
正确应该是4
我发现一个规律，不知道是不是普遍性的不知道
如果K>Xlen,先把所有X变成Y，再从两边把Y变成X，
因为在一个连续的Y中，尽可能的在两边变成X，不要在中间变

zhangjinxuan

jhq999 发表于 2023-2-26 09:53
你的结果是3
正确应该是4
我发现一个规律，不知道是不是普遍性的不知道

我试过，也是从两边来变，但是只进步了一点，还是WA

有dp那味了

陈尚涵

大哥，这个世界上除了省选noip那样的难度，代码超过百行怎么可能

zhangjinxuan

陈尚涵 发表于 2023-2-26 10:43
大哥，这个世界上除了省选noip那样的难度，代码超过百行怎么可能

或许这道题真的就是noip难度
但不太现实

陈尚涵

而且没有注释，看的头大

zhangjinxuan

陈尚涵 发表于 2023-2-26 10:45
而且没有注释，看的头大

我也要疯了啊，到后来自己都看不懂了，只能说一说思路了，算了，这道题我还是看题解把

陈尚涵

zhangjinxuan 发表于 2023-2-26 10:45
或许这道题真的就是noip难度
但不太现实

懒得看英文，头大
可以简单解释下题意吗

zhangjinxuan

陈尚涵 发表于 2023-2-26 10:47
懒得看英文，头大
可以简单解释下题意吗

给出由X，Y构成的长度N的字符串S。选择S中位于不同位置的K字符，如果选择的字符是X，则改成Y，如果是Y，则改成X。
请问修改K次后的字符串中Y彼此相邻的地方最大为多少，也就是有多少 i, 满足 1 <= i < n 并且 Si = Si+1 以及 Si == 'Y'

百度翻+人翻，希望能看得懂……

最后的最后，本题的灵魂：

1 <= n <= 2e5
0 <= k <= n

陈尚涵

zhangjinxuan 发表于 2023-2-26 10:48
百度翻+人翻，希望能看得懂……

最后的最后，本题的灵魂：

这种编程题不能用机翻的，大哥

陈尚涵

zhangjinxuan 发表于 2023-2-26 10:48
百度翻+人翻，希望能看得懂……

最后的最后，本题的灵魂：

机翻会吞掉不少东西

陈尚涵

zhangjinxuan 发表于 2023-2-26 10:48
百度翻+人翻，希望能看得懂……

最后的最后，本题的灵魂：

什么是Y彼此相邻
我尽量看懂题给你讲思路

陈尚涵

为什么我一直显示你发的贴子撤销置顶了

陈尚涵

加好友了

陈尚涵

？人呢

sfqxx

我想问一下为什么CE还能AC？