GYM 103371 B - Cilantro

香菜面条！

prob.: 给两个01串S和T，S有一个辅助栈，问以T的形式取出之后，第一个取出的字符在原串S中的可能下标的和

ideas：

很奇妙的一个题

因为是01串，当两个串中0和1的数目都相等的时候总能构造一种方案在栈的辅助下使得S变成T

如果S以T的形式取出之后第一个取出的字符在原串中的下标可能值包含mx，则所有在mx之前的相同字符都为可能的解

只要使得T中第一个与尽量后面的字符匹配就行，二分这个位置好像说会T

考虑贪心

尽量使得S中第一个字符匹配后面的T中的靠后的字符，然后匹配第二个字符，匹配到最后只剩下T中第一个能匹配，这时候就是T能匹配的S的最大的下标，指针指一下

参考了下一些佬的代码，佬们写的真好看

code：

#include 

using namespace std;

const int N = 5000000 + 10;

char s[N], t[N];
int pres[N][2], pret[N][2];

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

    int n;
    cin >> n;
    cin >> (s + 1) >> (t + 1);

    for (int i = 1; i <= n; ++i) {
        pres[i][0] = pres[i - 1][0];
        pres[i][1] = pres[i - 1][1];
        if (s[i] == 'N') pres[i][0]++;
        else pres[i][1]++;
        pret[i][0] = pret[i - 1][0];
        pret[i][1] = pret[i - 1][1];
        if (t[i] == 'N') pret[i][0]++;
        else pret[i][1]++;
    }

    if (pres[n][1] != pret[n][1]) {
        cout << 0;
        return 0;
    }

    int cur = 1, ps = n, pt = n;
    while (pt > 1) {
        if (s[cur] == t[pt]) {
            ++cur;
            --pt;
            continue;
        }
        int lstps = ps, lstpt = pt;
//        while(ps && pt && pres[lstps][1] - pres[ps][1] != pret[lstpt][1] - pret[pt][1]) {
//            ps--, pt--;
//        }
//        ps--, pt--;
        while (1) {
            ps--, pt--;
            if (ps && pt && pres[lstps][1] - pres[ps][1] == pret[lstpt][1] - pret[pt][1]) break;
        }
    }

    long long ans = 0;
    for (int i = 1; i <= cur; ++i) {
        if (s[i] == t[1]) ans += i;
    }
    cout << ans << 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