2023-09-07：用go语言编写。塔子哥最近在处理一些字符串相关的任务

他喜欢 R 字符，因为在某些任务中，这个字符通常表示“正确”的结果

另一方面，他不喜欢 B 字符，因为在某些任务中，这个字符通常表示“错误”的结果

为了解决他的任务，塔子哥定义了字符串的权值为字符串中 R 字符的出现次数

例如，对于字符串 BBRBRB，它的权值为 2，因为其中有 2 个 R 字符

现在，塔子哥面临一个问题，他有一个长度为 n 的字符串 s，它仅由 R 和 B 组成

他想知道，长度为 n 的仅由 R 和 B组成的字符串中，

字典序不小于 s 的字符串的权值之和是多少？

因此，他需要编写一个程序来解决这个问题

输入第一行为一个整数 n ，表示字符串的长度

输入第二行为一个长度为 n 的字符串 s ，字符串中元素组成仅为 R 和 B

输出一个整数，代表长度为 n 的、字典序不小于 s 的字符串权值之和。

输入样例：

3

RBR

输出：

7

解释：共有 3 个字符串字典序大于等于”RBR”，RBR权值为2，RRB为2，RRR为3。

1 <= n <= 100000，

结果可能很大，对1000000007取模。

来自左程云。

答案2023-09-07：

大体过程如下：

算法一（sum1）：

1.定义函数sum1，它接收一个字符串作为参数，并返回字典序不小于该字符串的所有可能字符串中权值之和。

2.在sum1中，定义了辅助函数process1，它通过递归生成所有可能的字符串，并计算符合条件的字符串的权值之和。

3.在process1中，递归地生成新字符串，每次添加’R’或’B’，直到生成的字符串长度与给定字符串长度相等。

4.如果生成的字符串与给定字符串相等或更大，返回权值之和，其中权值为’R’的个数。

5.如果生成的字符串小于给定字符串，返回0，表示没有符合条件的字符串。

6.在每个递归步骤中，将递归调用的结果相加，计算出所有可能字符串的权值之和。

7.在sum1函数中，调用process1函数并返回最终的权值之和。

算法二（sum3）：

1.定义函数sum3，它接受一个字符串作为参数，并返回字典序不小于该字符串的所有可能字符串的权值之和。

2.在sum3中，首先初始化一些辅助数组和变量。

3.使用动态规划的方法来计算权值之和。

4.创建一个长度为n+1的dp数组，其中dp[i]表示以第i个字符作为起始字符的后缀字符串的权值之和。

5.初始化dp[n]为给定字符串最后一个字符的权值。

6.从右到左遍历字符串，计算dp数组的值。

7.如果当前字符是’R’，根据公式计算p1和p2，然后将p1和p2相加得到dp[i]。

8.如果当前字符是’B’，将dp[i+1]的值赋给dp[i]。

9.最后返回dp[0]作为最终的权值之和。

时间复杂度：

• 算法一（sum1）的时间复杂度为O(2^n)，其中n是给定字符串的长度。因为它通过递归的方式生成所有可能的字符串。

• 算法二（sum3）的时间复杂度为O(n)，其中n是给定字符串的长度。因为它使用动态规划计算权值之和。

额外空间复杂度：

• 算法一（sum1）的额外空间复杂度为O(n)，因为递归调用process1函数可能会使用到O(n)的栈空间。

• 算法二（sum3）的额外空间复杂度为O(n)，因为它使用了dp数组来存储中间结果，数组长度为n+1。

go完整代码如下：

package main

import (
    "fmt"
    "math/rand"
    "strings"
    "time"
)

const MAXN = 100001
const mod = 1000000007

var pow2, f [MAXN]int

func sum1(str string) int {
    return process1("", str)
}

func process1(path, s string) int {
    if len(path) == len(s) {
        if strings.Compare(path, s) >= 0 {
            ans := 0
            for i := 0; i < len(path); i++ {
                if path[i] == 'R' {
                    ans++
                }
            }
            return ans
        } else {
            return 0
        }
    } else {
        return process1(path+"R", s) + process1(path+"B", s)
    }
}

func initialize() {
    pow2[0] = 1
    for i := 1; i < MAXN; i++ {
        pow2[i] = (pow2[i-1] * 2) % mod
    }
    f[1] = 1
    for i := 2; i < MAXN; i++ {
        f[i] = (pow2[i-1] + f[i-1]) % mod
        f[i] = (f[i] + f[i-1]) % mod
    }
}

func sum2(str string) int {
    n := len(str)
    s := []byte(str)
    rnumber := make([]int, n)
    rnumber[0] = map[bool]int{true: 1, false: 0}[s[0] == 'R']
    for i := 1; i < n; i++ {
        rnumber[i] = rnumber[i-1] + map[bool]int{true: 1, false: 0}[s[i] == 'R']
    }
    return process2(s, rnumber, n, 0)
}

func process2(s []byte, rnumber []int, n, i int) int {
    var ans int
    if i == n {
        ans = rnumber[n-1]
    } else {
        if s[i] == 'B' {
            p1 := int(((int64(rnumber[i]+1)*int64(pow2[n-i-1]))%int64(mod) + int64(f[n-i-1])) % int64(mod))
            p2 := process2(s, rnumber, n, i+1)
            ans = (p1 + p2) % mod
        } else {
            ans = process2(s, rnumber, n, i+1)
        }
    }
    return ans
}

func sum3(str string) int {
    n := len(str)
    s := []byte(str)
    rnumber := make([]int, n)
    rnumber[0] = map[bool]int{true: 1, false: 0}[s[0] == 'R']
    for i := 1; i < n; i++ {
        rnumber[i] = rnumber[i-1] + map[bool]int{true: 1, false: 0}[s[i] == 'R']
    }
    dp := make([]int, n+1)
    dp[n] = rnumber[n-1]
    for i := n - 1; i >= 0; i-- {
        if s[i] == 'B' {
            p1 := int(((int64(rnumber[i]+1)*int64(pow2[n-i-1]))%int64(mod) + int64(f[n-i-1])) % int64(mod))
            p2 := dp[i+1]
            dp[i] = (p1 + p2) % mod
        } else {
            dp[i] = dp[i+1]
        }
    }
    return dp[0]
}

func randomString(n int) string {
    s := make([]byte, n)
    for i := 0; i < n; i++ {
        if rand.Float32() < 0.5 {
            s[i] = 'B'
        } else {
            s[i] = 'R'
        }
    }
    return string(s)
}

func main() {
    rand.Seed(time.Now().UnixMilli())
    N := 15
    testTimes := 10000
    fmt.Println("测试开始")
    initialize()
    for i := 0; i < testTimes; i++ {
        n := rand.Intn(N) + 1
        s := randomString(n)
        ans1 := sum1(s)
        ans3 := sum3(s)
        if ans1 != ans3 {
            fmt.Println("出错了!")
        }
    }
    fmt.Println("测试结束")
}

c++完整代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <random>

constexpr int MAXN = 100001;
constexpr int mod = 1000000007;

std::vector<int> pow2(MAXN);
std::vector<int> f(MAXN);

int process1(const std::string& path, const std::string& s);

int sum1(const std::string& str) {
    return process1("", str);
}

int process1(const std::string& path, const std::string& s) {
    if (path.length() == s.length()) {
        if (path.compare(s) >= 0) {
            int ans = 0;
            for (int i = 0; i < path.length(); i++) {
                if (path[i] == 'R') {
                    ans++;
                }
            }
            return ans;
        }
        else {
            return 0;
        }
    }
    else {
        return process1(path + "R", s) + process1(path + "B", s);
    }
}

void initialize() {
    pow2[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        pow2[i] = (pow2[i - 1] * 2) % mod;
    }
    f[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        f[i] = (pow2[i - 1] + f[i - 1]) % mod;
        f[i] = (f[i] + f[i - 1]) % mod;
    }
}

int process2(const std::vector<char>& s, const std::vector<int>& rnumber, int n, int i);

int sum2(const std::string& str) {
    int n = str.length();
    std::vector<char> s(str.begin(), str.end());
    std::vector<int> rnumber(n);
    rnumber[0] = (s[0] == 'R') ? 1 : 0;
    for (int i = 1; i < n; i++) {
        rnumber[i] = rnumber[i - 1] + ((s[i] == 'R') ? 1 : 0);
    }
    return process2(s, rnumber, n, 0);
}

int process2(const std::vector<char>& s, const std::vector<int>& rnumber, int n, int i) {
    int ans;
    if (i == n) {
        ans = rnumber[n - 1];
    }
    else {
        if (s[i] == 'B') {
            int p1 = (((int64_t)(rnumber[i] + 1) * (int64_t)pow2[n - i - 1]) % (int64_t)mod + (int64_t)f[n - i - 1]) % (int64_t)mod;
            int p2 = process2(s, rnumber, n, i + 1);
            ans = (p1 + p2) % mod;
        }
        else {
            ans = process2(s, rnumber, n, i + 1);
        }
    }
    return ans;
}

int sum3(const std::string& str) {
    int n = str.length();
    std::vector<char> s(str.begin(), str.end());
    std::vector<int> rnumber(n);
    rnumber[0] = (s[0] == 'R') ? 1 : 0;
    for (int i = 1; i < n; i++) {
        rnumber[i] = rnumber[i - 1] + ((s[i] == 'R') ? 1 : 0);
    }
    std::vector<int> dp(n + 1);
    dp[n] = rnumber[n - 1];
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == 'B') {
            int p1 = (((int64_t)(rnumber[i] + 1) * (int64_t)pow2[n - i - 1]) % (int64_t)mod + (int64_t)f[n - i - 1]) % (int64_t)mod;
            int p2 = dp[i + 1];
            dp[i] = (p1 + p2) % mod;
        }
        else {
            dp[i] = dp[i + 1];
        }
    }
    return dp[0];
}

std::string randomString(int n) {
    std::string s(n, ' ');
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, 1);
    for (int i = 0; i < n; i++) {
        if (dis(gen) < 0.5) {
            s[i] = 'B';
        }
        else {
            s[i] = 'R';
        }
    }
    return s;
}

int main() {
    std::random_device rd;
    std::mt19937 gen(rd());
    int N = 15;
    int testTimes = 100;
    std::cout << "测试开始" << std::endl;
    initialize();
    for (int i = 0; i < testTimes; i++) {
        int n = gen() % N + 1;
        std::string s = randomString(n);
        int ans1 = sum1(s);
        int ans3 = sum3(s);
        if (ans1 != ans3) {
            std::cout << "出错了!" << std::endl;
        }
    }
    std::cout << "测试结束" << std::endl;
    return 0;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接