玖的数学&算法录
0%

AtCoder Beginner Contest

发表于 更新于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

仅补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$$

题解：模拟

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}