AtCoder Beginner Contest

仅补D~F的题（部分C、G会考虑补充）

AtCoder Beginner Contest 456

C.Not Adjacent

给定一个只含有a,b,c的字符串S，求S的非空子串中，没有两个相邻字符相同的字符数，取模为998244353。

数据范围

$$1\leq s.length() \leq 3\times 10^5$$

题解：模拟

扫一遍字符串，如果当前的数和前面的数相同，则不能成为一种方案数，反之不同则可以是一种方案数，每次得到的方案数可以与前面所积累的方案数组成新的方案。

代码

void JiuCherish() {
    std::string s;
    std::cin >> s;
    int n = s.length();
    int sum = 1;
    int ans = 1;
    for(int i=1;i<n;i++) {
        if(s[i] == s[i - 1]) sum = 1;
        else sum += 1;
        ans = (ans + sum) % mod;
    }
    std::cout << ans << endl;
}

D.Not Adjacent 2

给定一个只含有a,b,c的字符串S，求S的非空序列中，没有两个相邻字符相同的字符数，取模为998244353。

数据范围

$$1\leq s.length() \leq 3\times 10^5$$

题解：dp

定义dp[i] [x]是以S的前i个字符中以x结尾的子序列的个数。

那么就会有如果当前字符串不以x结尾的话，不能使用该字符，因此有dp[i] [x] = dp[i - 1] [x]

如果当前字符以 x结尾的话，只有dp[i - 1] [x]不能使用该字符，而其他情况可以使用，即加dp[i - 1] [x2] + dp[i - 1] [x3] + 1

void JiuCherish() {
    std::string s;
    std::cin >> s;
    int n = s.length();
    int ans = 0;
    int dp[3] = {0};
    for(int i=0;i<n;i++) {
        int x = s[i] - 'a';
        int cur = 1;
        for(int j=0;j<3;j++) {
            if(j != x) cur = (cur + dp[j]) % mod;
        }
        dp[x] = (dp[x] + cur) % mod;
    }
    std::cout << (dp[0] + dp[1] + dp[2]) % mod << endl;
}

AtCoder Beginner Contest 455

D - Card Pile Query

有n张扑克牌和n堆扑克牌，

纸牌和牌堆的编号都是1，2…，N，最初，牌堆i中只有纸牌i。

现在有Q次操作：

将纸牌Ci以及所以在纸牌Ci上的牌保持顺序放到Pi上面，同时保证执行操作之前，纸牌Ci和Pi在不同的牌堆中，而纸牌Pi在某一牌堆的顶端。

求Q次操作后每堆牌的数量。

数据范围

$$1 \leq N , Q \leq 3 \times 10^5$$

$$1 \leq C_i,P_i \leq N$$

题解：模拟

根据题意模拟即可

void JiuCherish() {
    int n,q;
    std::cin >> n >> q;
    std::vector<int> nxt(n + 1,0);
    std::vector<int> rev(n + 1,0);
    while(q--) {
        int x,y;
        std::cin >> x >> y;
        if(nxt[x] != 0) rev[nxt[x]] = 0;
        nxt[x] = y;
        rev[y] = x;
    }
    std::vector<bool> vis(n + 1,false);
    std::vector<int> ans(n + 1,0);
    for(int i=1;i<=n;i++) {
        if(nxt[i] == 0 and !vis[i]) {
            int cnt = 0;
            int cur = i;
            while(cur != 0 and !vis[cur]) {
                vis[cur] = 1;
                ++cnt;
                cur = rev[cur];
            }
            ans[i] = cnt;
        }
    }
    for(int i=1;i<=n;i++) std::cout << ans[i] << ' ';
}

E - Unbalanced ABC Substrings

给你一个只有”A”,”B”,”C”组成的字符串S，长度为n。

在S中有N（N+1）/2个非空子串，求其中有多少个满足以下条件：A,B和C出现的次数都互不相同。

数据范围

$$1 \leq N \leq 2 \times 10^5$$

$$|S| = N$$

题解：容斥

设A、B、C分别表示子串中出现a,b,c的次数

约定f（x)为满足条件x的子串的个数。

根据容斥原理，答案就是n(n+ 1)/2 - f(A = B) - f（A=C）-f(B=C)+3f(A=B=C)-f(A=B=C) = n(n+ 1)/2 - f(A = B) - f（A=C）- f(B=C) + 2f(A = B = C)

问题在于如何求f(A=B=C)

首先Ai、Bi和Ci分别是S的前i个字符内出现的A,B,C的个数。那么查询区间内字符数就是Ar-Al,Br-Bl,Cr-Cl,又Ar-Al＝Br-Bl＝Cr-Cl等价于（Al - Bl，Al - Cl） = （Ar-Br,Ar-Cr)，因此可以对每个i找到（Ai-Bi，Ai-Ci)，计算出这对字符产生相同的(l,r)个数。

也就是说如果过某一对出现了c次，那么就有c(c-1)/2种方法可以选择l和r，将他们相加，通过O（N）和O（NlogN）找到f(A=B=C)。

不失一般性f(A=B)、f(A = C)和f(B=C)也可以求出

void JiuCherish() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    int ans = n * (n + 1) / 2;
    std::map<int,int> cntab,cntac,cntbc;
    std::map<std::pair<int,int>,int> cntabc;
    int a = 0,b = 0,c = 0;
    cntab[0] += 1;
    cntac[0] += 1;
    cntbc[0] += 1;
    cntabc[{0,0}] += 1;
    for(auto x : s) {
        if(x == 'A') a += 1;
        else if(x == 'B') b += 1;
        else c += 1;
        int diffab = a - b;
        int diffac = a - c;
        int diffbc = b - c;
        cntab[diffab] += 1;
        cntac[diffac] += 1;
        cntbc[diffbc] += 1;
        cntabc[{diffab,diffac}] += 1;
    }
    auto calc = [](auto &mp) -> int {
        int res = 0;
        for(auto& [u,v] : mp) res += v * (v - 1) / 2;
        return res;
    };
    int fab = calc(cntab);
    int fac = calc(cntac);
    int fbc = calc(cntbc);
    int fabc = calc(cntabc);
    std::cout << ans - fab - fac - fbc + 2 * fabc << endl;
}