zhangjinxuan 发表于 2023-2-25 21:59:21

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

题目:
给出由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;
int ypos, tot, dtot;
struct D {
        int l, r, va;
} d;
bool fd;

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 == s && s == 'Y') ++tot;
                }
                printf("%d", tot);
                return 0;
        }
        for (int i = 1; i <= n; ++i) {
                if (s == 'Y') {
                        ypos[++tot] = i;
                }
        }
        if (tot == 0) {
                printf("%d", k - 1);
                return 0;
        }
        for (int i = 1; i < tot; ++i) {
                if (ypos - ypos - 1 == 0) continue;
      ++dtot;
                d.l = ypos;
                d.r = ypos;
                d.va = ypos - ypos - 1;
        }
        if (ypos != 0) {
                ++dtot;
                d.l = 0;
                d.r = ypos;
                d.va = ypos - 1;
        }
        if (ypos != n) {
                ++dtot;
                d.l = ypos;
                d.r = n + 1;
                d.va = n + 1 - ypos - 1;
        }
        sort(d + 1, d + dtot + 1, cmp);
        //for (int i = 1; i <= dtot; ++i) {
        //        printf("%d %d %d\n", d.l, d.r, d.va);
        //}
        for (int i = 1; i <= dtot && k; ++i) {
                for (int j = d.l + 1; j < d.r && k; ++j) {
                        //assert(s == 'X');
                        s = 'Y';
            assert(fd == 0);
                        fd = 1;
                        --k;
                }
        }
        int res = 0;
        for (int i = 1; i < n; ++i) {
                if (s == s && s == 'Y') {
                        ++res;
                }
        }
        //        puts(s + 1);
        if (k == 0) {
                printf("%d", res);
                return 0;
        }
        if (fd == 0) {
                --res;
                --k;
        }
        if (fd == 0 && k) {
                --res;
                --k;
        }
        for (int i = 2; i < n && k; ++i) {
                if (!fd) {
                     fd = 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 发表于 2023-2-25 23:12:40

10 10
YYYYYYYYYY

zhangjinxuan 发表于 2023-2-26 08:06:13

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


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

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

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 == s && s == 'Y') ++tot;
                }
                printf("%d", tot);
                return 0;
        }
        for (int i = 1; i <= n; ++i) {
                if (s == 'Y') {
                        ypos[++tot] = i;
                }
        }
        if (tot == 0) {
                printf("%d", k - 1);
                return 0;
        }
        for (int i = 1; i < tot; ++i) {
                if (ypos - ypos - 1 == 0) continue;
                ++dtot;
                d.l = ypos;
                d.r = ypos;
                d.va = ypos - ypos - 1;
                d.first = 1;
        }
        sort(d + 1, d + dtot + 1, cmp);

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

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

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

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

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

10 9
XYYXXYXXYY


XYYXXYXXYY
YYYYYYYYYY
YXXYYYYYXX

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

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


?

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

本帖最后由 jhq999 于 2023-2-26 10:00 编辑

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


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

zhangjinxuan 发表于 2023-2-26 10:13:43

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


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

有dp那味了

陈尚涵 发表于 2023-2-26 10:43:18

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

zhangjinxuan 发表于 2023-2-26 10:45:02

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

或许这道题真的就是noip难度{:10_257:}
但不太现实{:10_269:}

陈尚涵 发表于 2023-2-26 10:45:09

而且没有注释,看的头大

zhangjinxuan 发表于 2023-2-26 10:45:55

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

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

陈尚涵 发表于 2023-2-26 10:47:29

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

懒得看英文,头大{:10_257:}
可以简单解释下题意吗

zhangjinxuan 发表于 2023-2-26 10:48:24

陈尚涵 发表于 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

陈尚涵 发表于 2023-2-26 10:49:20

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

最后的最后,本题的灵魂:

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

陈尚涵 发表于 2023-2-26 10:49:36

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

最后的最后,本题的灵魂:

机翻会吞掉不少东西

陈尚涵 发表于 2023-2-26 10:51:32

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

最后的最后,本题的灵魂:

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

陈尚涵 发表于 2023-2-26 10:53:57

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

陈尚涵 发表于 2023-2-26 10:55:29

加好友了

陈尚涵 发表于 2023-2-26 10:56:58

?人呢

sfqxx 发表于 2023-2-26 11:51:04

我想问一下为什么CE还能AC?
页: [1] 2
查看完整版本: 蒟蒻求助,被今天 ARC 的第 2 题,折磨疯了,谁能帮忙看看么?