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

zhangjinxuan

题目：

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

本人代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, k;
   
5. char s[200011];
   
6. int ypos[500011], tot, dtot;
   
7. struct D {
   
8.         int l, r, va;
   
9. } d[500011];
   
10. bool fd[500011];
    
11. 
    
12. bool cmp(const D &a, const D &b) {
    
13.         if (b.l == 0 || b.r == n + 1) return 1;
    
14.         if (a.l == 0 || a.r == n + 1) return 0;
    
15.         return a.va < b.va;
    
16. }
    
17. 
    
18. int main() {
    
19.         scanf("%d%d%s", &n, &k, s + 1);
    
20.         //printf("\n%d", cmp({0, 2, 1}, {4, 7, 2}));
    
21.         //exit(0);
    
22.         if (k == 0) {
    
23.                 for (int i = 1; i < n; ++i) {
    
24.                         if (s[i] == s[i + 1] && s[i] == 'Y') ++tot;
    
25.                 }
    
26.                 printf("%d", tot);
    
27.                 return 0;
    
28.         }
    
29.         for (int i = 1; i <= n; ++i) {
    
30.                 if (s[i] == 'Y') {
    
31.                         ypos[++tot] = i;
    
32.                 }
    
33.         }
    
34.         if (tot == 0) {
    
35.                 printf("%d", k - 1);
    
36.                 return 0;
    
37.         }
    
38.         for (int i = 1; i < tot; ++i) {
    
39.                 if (ypos[i + 1] - ypos[i] - 1 == 0) continue;
    
40.         ++dtot;
    
41.                 d[dtot].l = ypos[i];
    
42.                 d[dtot].r = ypos[i + 1];
    
43.                 d[dtot].va = ypos[i + 1] - ypos[i] - 1;
    
44.         }
    
45.         if (ypos[1] != 0) {
    
46.                 ++dtot;
    
47.                 d[dtot].l = 0;
    
48.                 d[dtot].r = ypos[1];
    
49.                 d[dtot].va = ypos[1] - 1;
    
50.         }
    
51.         if (ypos[tot] != n) {
    
52.                 ++dtot;
    
53.                 d[dtot].l = ypos[tot];
    
54.                 d[dtot].r = n + 1;
    
55.                 d[dtot].va = n + 1 - ypos[tot] - 1;
    
56.         }
    
57.         sort(d + 1, d + dtot + 1, cmp);
    
58.         //for (int i = 1; i <= dtot; ++i) {
    
59.         //        printf("%d %d %d\n", d[i].l, d[i].r, d[i].va);
    
60.         //}
    
61.         for (int i = 1; i <= dtot && k; ++i) {
    
62.                 for (int j = d[i].l + 1; j < d[i].r && k; ++j) {
    
63.                         //assert(s[j] == 'X');
    
64.                         s[j] = 'Y';
    
65.             assert(fd[j] == 0);
    
66.                         fd[j] = 1;
    
67.                         --k;
    
68.                 }
    
69.         }
    
70.         int res = 0;
    
71.         for (int i = 1; i < n; ++i) {
    
72.                 if (s[i] == s[i + 1] && s[i] == 'Y') {
    
73.                         ++res;
    
74.                 }
    
75.         }
    
76.         //        puts(s + 1);
    
77.         if (k == 0) {
    
78.                 printf("%d", res);
    
79.                 return 0;
    
80.         }
    
81.         if (fd[1] == 0) {
    
82.                 --res;
    
83.                 --k;
    
84.         }
    
85.         if (fd[n] == 0 && k) {
    
86.                 --res;
    
87.                 --k;
    
88.         }
    
89.         for (int i = 2; i < n && k; ++i) {
    
90.                 if (!fd[i]) {
    
91.                        fd[i] = 1;
    
92.                         res -= 2;
    
93.                         --k;
    
94.                 }
    
95.         }
    
96.         printf("%d", res);
    
97.         return 0;
    
98. }/*
    
99. 10 5
    
100. XYXYXXYYYX*/

复制代码

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

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

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

jhq999

1. 10 10
   
2. YYYYYYYYYY

复制代码

zhangjinxuan

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, k;
   
5. char s[200011];
   
6. int ypos[200011], tot, dtot;
   
7. struct D {
   
8.         int l, r, va;
   
9.         bool first;
   
10. } d[200011];
    
11. bool fd[200011];
    
12. 
    
13. bool cmp(const D &a, const D &b) {
    
14.         if (b.l == 0 || b.r == n + 1) return 1;
    
15.         if (a.l == 0 || a.r == n + 1) return 0;
    
16.         return a.va < b.va;
    
17. }
    
18. 
    
19. int main() {
    
20.         scanf("%d%d%s", &n, &k, s + 1);
    
21.         //printf("\n%d", cmp({0, 2, 1}, {4, 7, 2}));
    
22.         //exit(0);
    
23.         if (k == 0) {
    
24.                 for (int i = 1; i < n; ++i) {
    
25.                         if (s[i] == s[i + 1] && s[i] == 'Y') ++tot;
    
26.                 }
    
27.                 printf("%d", tot);
    
28.                 return 0;
    
29.         }
    
30.         for (int i = 1; i <= n; ++i) {
    
31.                 if (s[i] == 'Y') {
    
32.                         ypos[++tot] = i;
    
33.                 }
    
34.         }
    
35.         if (tot == 0) {
    
36.                 printf("%d", k - 1);
    
37.                 return 0;
    
38.         }
    
39.         for (int i = 1; i < tot; ++i) {
    
40.                 if (ypos[i + 1] - ypos[i] - 1 == 0) continue;
    
41.                 ++dtot;
    
42.                 d[dtot].l = ypos[i];
    
43.                 d[dtot].r = ypos[i + 1];
    
44.                 d[dtot].va = ypos[i + 1] - ypos[i] - 1;
    
45.                 d[dtot].first = 1;
    
46.         }
    
47.         sort(d + 1, d + dtot + 1, cmp);
    
48. 
    
49.         if (ypos[1] - 1) {
    
50.                 ++dtot;
    
51.                 d[dtot].l = 0;
    
52.                 d[dtot].r = ypos[1];
    
53.                 d[dtot].va = ypos[1] - 1;
    
54.                 d[dtot].first = 0;
    
55.         }
    
56.         if (ypos[tot] != n) {
    
57.                 ++dtot;
    
58.                 d[dtot].l = ypos[tot];
    
59.                 d[dtot].r = n + 1;
    
60.                 d[dtot].va = n + 1 - ypos[tot] - 1;
    
61.                 d[dtot].first = 0;
    
62.         }
    
63.         //for (int i = 1; i <= dtot; ++i) {
    
64.         //        printf("%d %d %d\n", d[i].l, d[i].r, d[i].va);
    
65.         //}
    
66.         for (int i = 1; i <= dtot && k; ++i) {
    
67.                 for (int j = d[i].l + 1; j < d[i].r && k; ++j) {
    
68.                         //assert(s[j] == 'X');
    
69.                         s[j] = 'Y';
    
70.                         fd[j] = 1;
    
71.                         --k;
    
72.                 }
    
73.         }
    
74.         int res = 0;
    
75.         for (int i = 1; i < n; ++i) {
    
76.                 if (s[i] == s[i + 1] && s[i] == 'Y') {
    
77.                         ++res;
    
78.                 }
    
79.         }
    
80.         //        puts(s + 1);
    
81.         if (k == 0) {
    
82.                 printf("%d", res);
    
83.                 return 0;
    
84.         }
    
85.         if (fd[1] == 0) {
    
86.                 s[1] = 'X';
    
87.                 --res;
    
88.                 --k;
    
89.         }
    
90.         if (fd[n] == 0 && k) {
    
91.                 s[n] = 'X';
    
92.                 --res;
    
93.                 --k;
    
94.         }
    
95.         for (int i = 2; i < n && k; ++i) {
    
96.                 if (!fd[i]) {
    
97.                         s[i] = 'X';
    
98.                         --k;
    
99.                         if (s[i - 1] == 'Y') --res;
    
100.                         if (s[i + 1] == 'Y') --res;
     
101.                 }
     
102.         }
     
103.         printf("%d", res);
     
104.         return 0;
     
105. }/*
     
106. 10 5
     
107. XYXYXXYYYX*/

复制代码

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

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

jhq999

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

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

1. 10 9
   
2. XYYXXYXXYY
   
3. 
   
4. 
   
5. XYYXXYXXYY
   
6. YYYYYYYYYY
   
7. YXXYYYYYXX

复制代码

zhangjinxuan

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

?

jhq999

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

1. 10 9
   
2. XYYXXYXXYY
   
3. 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. 1 <= n <= 2e5
   
2. 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？