2023-09-07：用go語言編寫。塔子哥最近在處理一些字符串相關(guān)的任務(wù) 他喜歡 R 字符，因
2023-09-07：用go語言編寫。塔子哥最近在處理一些字符串相關(guān)的任務(wù)
他喜歡 R 字符，因?yàn)樵谀承┤蝿?wù)中，這個(gè)字符通常表示“正確”的結(jié)果
另一方面，他不喜歡 B 字符，因?yàn)樵谀承┤蝿?wù)中，這個(gè)字符通常表示“錯(cuò)誤”的結(jié)果
為了解決他的任務(wù)，塔子哥定義了字符串的權(quán)值為字符串中 R 字符的出現(xiàn)次數(shù)
例如，對于字符串 BBRBRB，它的權(quán)值為 2，因?yàn)槠渲杏?2 個(gè) R 字符
現(xiàn)在，塔子哥面臨一個(gè)問題，他有一個(gè)長度為 n 的字符串 s，它僅由 R 和 B 組成
他想知道，長度為 n 的僅由 R 和 B組成的字符串中，
字典序不小于 s 的字符串的權(quán)值之和是多少？
因此，他需要編寫一個(gè)程序來解決這個(gè)問題
輸入第一行為一個(gè)整數(shù) n ，表示字符串的長度
輸入第二行為一個(gè)長度為 n 的字符串 s ，字符串中元素組成僅為 R 和 B
輸出一個(gè)整數(shù)，代表長度為 n 的、字典序不小于 s 的字符串權(quán)值之和。
輸入樣例：
3
RBR
輸出：
7
解釋：共有 3 個(gè)字符串字典序大于等于"RBR"，RBR權(quán)值為2，RRB為2，RRR為3。
1 <= n <= 100000，
結(jié)果可能很大，對1000000007取模。
來自[左程云](https://b23.tv/Zho7gh0)。
答案2023-09-07：
# 大體過程如下：
算法一（sum1）：
1.定義函數(shù)sum1，它接收一個(gè)字符串作為參數(shù)，并返回字典序不小于該字符串的所有可能字符串中權(quán)值之和。
2.在sum1中，定義了輔助函數(shù)process1，它通過遞歸生成所有可能的字符串，并計(jì)算符合條件的字符串的權(quán)值之和。
3.在process1中，遞歸地生成新字符串，每次添加'R'或'B'，直到生成的字符串長度與給定字符串長度相等。
4.如果生成的字符串與給定字符串相等或更大，返回權(quán)值之和，其中權(quán)值為'R'的個(gè)數(shù)。
5.如果生成的字符串小于給定字符串，返回0，表示沒有符合條件的字符串。
6.在每個(gè)遞歸步驟中，將遞歸調(diào)用的結(jié)果相加，計(jì)算出所有可能字符串的權(quán)值之和。
7.在sum1函數(shù)中，調(diào)用process1函數(shù)并返回最終的權(quán)值之和。
算法二（sum3）：
1.定義函數(shù)sum3，它接受一個(gè)字符串作為參數(shù)，并返回字典序不小于該字符串的所有可能字符串的權(quán)值之和。
2.在sum3中，首先初始化一些輔助數(shù)組和變量。
3.使用動態(tài)規(guī)劃的方法來計(jì)算權(quán)值之和。
4.創(chuàng)建一個(gè)長度為n+1的dp數(shù)組，其中dp[i]表示以第i個(gè)字符作為起始字符的后綴字符串的權(quán)值之和。
5.初始化dp[n]為給定字符串最后一個(gè)字符的權(quán)值。
6.從右到左遍歷字符串，計(jì)算dp數(shù)組的值。
7.如果當(dāng)前字符是'R'，根據(jù)公式計(jì)算p1和p2，然后將p1和p2相加得到dp[i]。
8.如果當(dāng)前字符是'B'，將dp[i+1]的值賦給dp[i]。
9.最后返回dp[0]作為最終的權(quán)值之和。
時(shí)間復(fù)雜度：
- 算法一（sum1）的時(shí)間復(fù)雜度為O(2^n)，其中n是給定字符串的長度。因?yàn)樗ㄟ^遞歸的方式生成所有可能的字符串。
- 算法二（sum3）的時(shí)間復(fù)雜度為O(n)，其中n是給定字符串的長度。因?yàn)樗褂脛討B(tài)規(guī)劃計(jì)算權(quán)值之和。
額外空間復(fù)雜度：
- 算法一（sum1）的額外空間復(fù)雜度為O(n)，因?yàn)檫f歸調(diào)用process1函數(shù)可能會使用到O(n)的?？臻g。
- 算法二（sum3）的額外空間復(fù)雜度為O(n)，因?yàn)樗褂昧薲p數(shù)組來存儲中間結(jié)果，數(shù)組長度為n+1。
# go完整代碼如下：
```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("出錯(cuò)了!")
}
}
fmt.Println("測試結(jié)束")
}
```
# c++完整代碼如下：
```cpp
#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 << "出錯(cuò)了!" << std::endl;
? ? ? ? }
? ? }
? ? std::cout << "測試結(jié)束" << std::endl;
? ? return 0;
}
```
