2022牛客多校加赛场_G

G - Good red-string

非常难得做到这种一看一眼，然后wa的死去活来的题，mark一下

一些水blog+想法记录

prob:

给一个只含有r、e、d、？的字符串，问能否通过将？补成red中的一个使得最后的串能被分成若干red子序列

ideas：

真的各种乱贪，又觉得需要一起考虑的东西太多了，能被自己造的并不长的样例随便卡死的程度

一些赛中想法

刚开始想的纯暴力从前往后能r就r，能e就e，会被r??r??卡掉，从后往前直接贪d也是同理会被??d??d卡

中间有一发是记录当前的每个字符的数目，然后类似如果rd比较多就用一个？去填e，但忽略了这个？必须在r后面

对于每个r，最后如果剩下来没处理的话需要两个？对它进行抵消，d往前同理，关于怎么样处理？或者怎么匹配rd比较优，这样想非常乱

从rd考虑太复杂，看看对于每个e，从前面从后面补r或d的条件，

考虑怎么先填e

一度觉得这题是不是不可能是贪心

---

后来已经脑子糊到对队友的想法就是一些：好写吗，你写出来，能把我造的所有样例过了就算你对（？

一些赛中的样例：

erd??d
r??r??
??d??d
??d??dr??r??
erd??d
redr??
?e?
?ee???
red??e
?rr?ee?dd
?rd
re?r?d
??ee?
?e?r?d??d
?re?e?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

中间队友有个想法就是将r看做在格子上往右走一步，e看做往左上走一步，d看做往下走一步，题目变成从原点出发回到原点，每一步都是以上三种走法，不出第一象限 的走的方案

但本来就不太会走格子，指方的格都不太会走

---

看了题解经典觉得好像不难

把所有的条件先列出来
对整个串： c n t r = c n t e = c n t d 对所有前缀： c n t r ≥ c n t e ≥ c n t d 对所有后缀： c n t r ≤ c n t e ≤ c n t d

对整个串：cntr对所有前缀：cntr对所有后缀：cntr​=cnte=cntd≥cnte≥cntd≤cnte≤cntd​​
从rd考虑情况会很复杂，关注e，把与e相关的条件拎出来

其中 对于前缀$cntd\le cnte$，对于后缀$cntr\le cnte$ 能涵盖所有前后缀限制

对于前缀$cntd\le cnte$，可以贪，一但$cntd>cnte$， 将前面最近的？改成e

对于后缀$cntr\le cnte$，一但$cntr>cnte$ ，将后面最近的？改成e

最最后按red顺序填？，然后判串是否合法

参考题解写出来的code：

#include 

using namespace std;

const int N = 5e5 + 10;
int nxt[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int _;
    cin >> _;
    while (_--) {
        string s;
        cin >> s;
        int n = s.size();

        if(n % 3 != 0) {
            cout << "No" << endl;
            continue;
        }
        int cnte = 0, cntd = 0;
        int p = -1;
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'e') cnte++;
            else if (s[i] == 'd') cntd++;
            else if (s[i] == '?') {
                nxt[i] = p;
                p = i;
            }
            if (cntd > cnte) {
                if (p == -1) {
                    flag = false;
                } else {
                    s[p] = 'e';
                    p = nxt[p];
                }
                cnte++;
            }
        }

//        cerr << s <

        cnte = 0, p = -1;
        int cntr = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == 'e') cnte++;
            else if (s[i] == 'r') cntr++;
            else if (s[i] == '?') {
                nxt[i] = p;
                p = i;
            }
            if (cntr > cnte) {
                if (p == -1) {
                    flag = false;
                } else {
                    s[p] = 'e';
                    p = nxt[p];
                }
                cnte++;
            }
        }

        cntr = 0, cnte = 0, cntd = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'r') cntr++;
            else if (s[i] == 'e') cnte++;
            else if (s[i] == 'd') cntd++;
        }

        int k = n / 3;
        cntr = k - cntr, cnte = k - cnte, cntd = k - cntd;

        if (cntr < 0 || cnte < 0 || cntd < 0) flag = 0;

//        cerr << s <

        if (!flag) {
            cout << "No" << endl;
            continue;
        }

        for (int i = 0; i < n; ++i) {
            if (s[i] == '?') {
                if (cntr) {
                    s[i] = 'r';
                    cntr--;
                } else if (cnte) {
                    s[i] = 'e';
                    cnte--;
                } else if (cntd) {
                    s[i] = 'd';
                    cntd--;
                }
            }
        }

//        cerr << s <
//        cerr << flag << endl;

        cntr = 0, cnte = 0, cntd = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'r') cntr++;
            else if (s[i] == 'e') cnte++;
            else if (s[i] == 'd') cntd++;
            if (cntd > cnte) flag = 0;
            if (cnte > cntr) flag = 0;
        }

        cntr = 0, cnte = 0, cntd = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == 'r') cntr++;
            else if (s[i] == 'e') cnte++;
            else if (s[i] == 'd') cntd++;
            if (cntr > cnte) flag = 0;
            if (cnte > cntd) flag = 0;
        }

        if (flag) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127