蒟蒻求助，被今天 ARC 的第 2 题，折磨疯了，谁能帮忙看看么？,C\C++交流,技术交流,鱼C论坛

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

鱼C论坛's Archiver

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