暗黑的字符串
题目
解题思路
使用动态规划解决：
- 状态表示：
表示长度为
时，最后三个字符状态为
的字符串数量
- 状态转移：根据新添加的字符更新状态
- 注意：只有不包含ABC的字符串才是暗黑的
题目## 题目## 题目## 题目
解题思路
使用动态规划解决：
- 状态表示：
- 状态转移：根据新添加的字符更新状态
- 注意：只有不包含ABC的字符串才是暗黑的
关键点
- 状态编码
- 状态转移
- 处理边界情况
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long countDarkStrings(int n) {
// 如果长度小于3，直接计算
if (n <= 0) return 0;
if (n == 1) return 3;
if (n == 2) return 9;
// dp[i][state]表示长度为i，最后三个字符状态为state的字符串数量
vector<vector<long long>> dp(n + 1, vector<long long>(27, 0));
// 初始化长度为1的情况
dp[1][0] = 3; // A=0, B=1, C=2
// 初始化长度为2的情况
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
dp[2][i * 3 + j]++;
}
}
// 动态规划
for (int i = 3; i <= n; i++) {
for (int last = 0; last < 27; last++) {
int x = last / 9; // 倒数第三个字符
int y = (last / 3) % 3;// 倒数第二个字符
int z = last % 3; // 倒数第一个字符
for (int next = 0; next < 3; next++) {
// 检查新的三个字符是否包含ABC
if (!containsABC(y, z, next)) {
int newState = (y * 3 + z) * 3 + next;
dp[i][newState] += dp[i-1][last];
}
}
}
}
// 统计所有暗黑字符串
long long result = 0;
for (int state = 0; state < 27; state++) {
result += dp[n][state];
}
return result;
}
private:
// 检查三个字符是否包含ABC
bool containsABC(int a, int b, int c) {
vector<bool> has(3, false);
has[a] = has[b] = has[c] = true;
return has[0] && has[1] && has[2];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while (cin >> n) {
Solution sol;
cout << sol.countDarkStrings(n) << endl;
}
return 0;
}
import java.util.*;
public class Main {
static class Solution {
public long countDarkStrings(int n) {
if (n <= 0) return 0;
if (n == 1) return 3;
if (n == 2) return 9;
long[][] dp = new long[n + 1][27];
// 初始化
dp[1][0] = 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
dp[2][i * 3 + j]++;
}
}
// 动态规划
for (int i = 3; i <= n; i++) {
for (int last = 0; last < 27; last++) {
int x = last / 9;
int y = (last / 3) % 3;
int z = last % 3;
for (int next = 0; next < 3; next++) {
if (!containsABC(y, z, next)) {
int newState = (y * 3 + z) * 3 + next;
dp[i][newState] += dp[i-1][last];
}
}
}
}
long result = 0;
for (int state = 0; state < 27; state++) {
result += dp[n][state];
}
return result;
}
private boolean containsABC(int a, int b, int c) {
boolean[] has = new boolean[3];
has[a] = has[b] = has[c] = true;
return has[0] && has[1] && has[2];
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
Solution sol = new Solution();
System.out.println(sol.countDarkStrings(n));
}
sc.close();
}
}
class Solution:
def count_dark_strings(self, n: int) -> int:
if n <= 0:
return 0
if n == 1:
return 3
if n == 2:
return 9
# dp[i][state]表示长度为i，最后三个字符状态为state的字符串数量
dp = [[0] * 27 for _ in range(n + 1)]
# 初始化
dp[1][0] = 3
for i in range(3):
for j in range(3):
dp[2][i * 3 + j] += 1
# 动态规划
for i in range(3, n + 1):
for last in range(27):
x = last // 9 # 倒数第三个字符
y = (last // 3) % 3 # 倒数第二个字符
z = last % 3 # 倒数第一个字符
for next_char in range(3):
# 检查新的三个字符是否包含ABC
if not self.contains_abc(y, z, next_char):
new_state = (y * 3 + z) * 3 + next_char
dp[i][new_state] += dp[i-1][last]
return sum(dp[n])
def contains_abc(self, a: int, b: int, c: int) -> bool:
has = [False] * 3
has[a] = has[b] = has[c] = True
return all(has)
def main():
while True:
try:
n = int(input())
sol = Solution()
print(sol.count_dark_strings(n))
except EOFError:
break
if __name__ == "__main__":
main()
算法及复杂度
- 算法：动态规划
- 时间复杂度：
- 空间复杂度：
解题思路
使用动态规划解决：
- 状态表示：
- 状态转移：根据新添加的字符更新状态
- 注意：只有不包含ABC的字符串才是暗黑的
关键点
- 状态编码
- 状态转移
- 处理边界情况
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long countDarkStrings(int n) {
// 如果长度小于3，直接计算
if (n <= 0) return 0;
if (n == 1) return 3;
if (n == 2) return 9;
// dp[i][state]表示长度为i，最后三个字符状态为state的字符串数量
vector<vector<long long>> dp(n + 1, vector<long long>(27, 0));
// 初始化长度为1的情况
dp[1][0] = 3; // A=0, B=1, C=2
// 初始化长度为2的情况
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
dp[2][i * 3 + j]++;
}
}
// 动态规划
for (int i = 3; i <= n; i++) {
for (int last = 0; last < 27; last++) {
int x = last / 9; // 倒数第三个字符
int y = (last / 3) % 3;// 倒数第二个字符
int z = last % 3; // 倒数第一个字符
for (int next = 0; next < 3; next++) {
// 检查新的三个字符是否包含ABC
if (!containsABC(y, z, next)) {
int newState = (y * 3 + z) * 3 + next;
dp[i][newState] += dp[i-1][last];
}
}
}
}
// 统计所有暗黑字符串
long long result = 0;
for (int state = 0; state < 27; state++) {
result += dp[n][state];
}
return result;
}
private:
// 检查三个字符是否包含ABC
bool containsABC(int a, int b, int c) {
vector<bool> has(3, false);
has[a] = has[b] = has[c] = true;
return has[0] && has[1] && has[2];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while (cin >> n) {
Solution sol;
cout << sol.countDarkStrings(n) << endl;
}
return 0;
}
import java.util.*;
public class Main {
static class Solution {
public long countDarkStrings(int n) {
if (n <= 0) return 0;
if (n == 1) return 3;
if (n == 2) return 9;
long[][] dp = new long[n + 1][27];
// 初始化
dp[1][0] = 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
dp[2][i * 3 + j]++;
}
}
// 动态规划
for (int i = 3; i <= n; i++) {
for (int last = 0; last < 27; last++) {
int x = last / 9;
int y = (last / 3) % 3;
int z = last % 3;
for (int next = 0; next < 3; next++) {
if (!containsABC(y, z, next)) {
int newState = (y * 3 + z) * 3 + next;
dp[i][newState] += dp[i-1][last];
}
}
}
}
long result = 0;
for (int state = 0; state < 27; state++) {
result += dp[n][state];
}
return result;
}
private boolean containsABC(int a, int b, int c) {
boolean[] has = new boolean[3];
has[a] = has[b] = has[c] = true;
return has[0] && has[1] && has[2];
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
Solution sol = new Solution();
System.out.println(sol.countDarkStrings(n));
}
sc.close();
}
}
class Solution:
def count_dark_strings(self, n: int) -> int:
if n <= 0:
return 0
if n == 1:
return 3
if n == 2:
return 9
# dp[i][state]表示长度为i，最后三个字符状态为state的字符串数量
dp = [[0] * 27 for _ in range(n + 1)]
# 初始化
dp[1][0] = 3
for i in range(3):
for j in range(3):
dp[2][i * 3 + j] += 1
# 动态规划
for i in range(3, n + 1):
for last in range(27):
x = last // 9 # 倒数第三个字符
y = (last // 3) % 3 # 倒数第二个字符
z = last % 3 # 倒数第一个字符
for next_char in range(3):
# 检查新的三个字符是否包含ABC
if not self.contains_abc(y, z, next_char):
new_state = (y * 3 + z) * 3 + next_char
dp[i][new_state] += dp[i-1][last]
return sum(dp[n])
def contains_abc(self, a: int, b: int, c: int) -> bool:
has = [False] * 3
has[a] = has[b] = has[c] = True
return all(has)
def main():
while True:
try:
n = int(input())
sol = Solution()
print(sol.count_dark_strings(n))
except EOFError:
break
if __name__ == "__main__":
main()
算法及复杂度
- 算法：动态规划
- 时间复杂度：
- 空间复杂度：
题目难度：二星 考察点：找规律 简要说明：这是一道找规律的题目，只要我们发现其中的规律，题目也就迎刃而解。
- 分析： 对于这道题来说，我们肯定不能直接从l到r遍历一遍，然后对于每个数判断是否能够被3整除，这样的复杂度太高，因为数据范围是10^9，所以我们考虑找规律，打表如下： 1%3 =====> 1 12%3 =====> 0 123%3 =====> 0 1234%3 =====> 1 12345%3 =====> 0 123456%3 =====> 0 那么我们发现从1开始，每隔3个数就有两个数%3=0，那么从[1,x]区间有多少能被3整除的数呢？答案显然为 f(x)=2*x/3，那么从[1,r]区间中被3整除的个数就等于f(r)-f(l-1)。
- 复杂度： 时间复杂度：O(1) 空间复杂度：O(1)
- 代码：
#include <bits stdc++.h>
using namespace std;
int f(int x) {
return 2*x/3;
}
int main() {
int l, r;
while(cin>>l>>r) {
cout<</bits>
[题目链接](https://www.nowcoder.com/practice/532a3814a4c646f2a063d5745b870fbe?tpId=182&tqId=314235&sourceUrl=/exam/oj&channenl=wcnblog&fromPut=wcnblog)
## 解题思路
1. 题目要求：
- 从 $n$ 个数中选择两个数
- 将一个数写在另一个数前面形成新数
- 计算能被7整除的新数的个数
2. 解题策略：
- 使用动态规划记录每个长度和余数的数字个数
- 对于每个数字，计算其长度和对7的余数
- 对于每对数字，检查拼接后是否能被7整除
---
## 代码
```cpp []
#include <iostream>
#include <vector>
using namespace std;
int main() {
// dp[i][j]: 长度为i的数字中余数为j的个数
vector<vector<int>> dp(10, vector<int>(7, 0));
// cnt[i]: 余数为i的数字总个数
vector<int> cnt(7, 0);
// num[i]: 10的i次方
vector<int> num(10, 10);
// 预处理10的幂
for(int i = 1; i < 10; ++i) {
num[i] = 10 * num[i-1];
}
int n;
cin >> n;
// 处理每个输入的数字
for(int i = 0; i < n; ++i) {
int v;
cin >> v;
// 计算数字长度
int len = 0;
while(v / num[len]) ++len;
// 计算对7的余数
int mod = v % 7;
++cnt[mod];
++dp[len][mod];
}
// 计算结果
long long res = (cnt[0]-1) * cnt[0]; // 处理余数为0的情况
// 处理其他余数的情况
for(int i = 1; i < 7; ++i) {
if(cnt[i] == 0) continue;
for(int x = 0; x < 10; ++x) {
for(int y = 0; y < 7; ++y) {
if(dp[x][y] == 0) continue;
// 检查拼接后是否能被7整除
if((i * num[x]) % 7 == (7 - y) % 7) {
if(i == y) {
res += (cnt[i]-1) * dp[x][y];
} else {
res += cnt[i] * dp[x][y];
}
}
}
}
}
cout << res << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// dp[i][j]: 长度为i的数字中余数为j的个数
int[][] dp = new int[10][7];
// cnt[i]: 余数为i的数字总个数
int[] cnt = new int[7];
// num[i]: 10的i次方
int[] num = new int[10];
num[0] = 10;
// 预处理10的幂
for(int i = 1; i < 10; ++i) {
num[i] = 10 * num[i-1];
}
int n = sc.nextInt();
// 处理每个输入的数字
for(int i = 0; i < n; ++i) {
int v = sc.nextInt();
// 计算数字长度
int len = 0;
while(v / num[len] > 0) ++len;
// 计算对7的余数
int mod = v % 7;
++cnt[mod];
++dp[len][mod];
}
// 计算结果
long res = (long)(cnt[0]-1) * cnt[0]; // 处理余数为0的情况
// 处理其他余数的情况
for(int i = 1; i < 7; ++i) {
if(cnt[i] == 0) continue;
for(int x = 0; x < 10; ++x) {
for(int y = 0; y < 7; ++y) {
if(dp[x][y] == 0) continue;
// 检查拼接后是否能被7整除
if((i * num[x]) % 7 == (7 - y) % 7) {
if(i == y) {
res += (long)(cnt[i]-1) * dp[x][y];
} else {
res += (long)cnt[i] * dp[x][y];
}
}
}
}
}
System.out.println(res);
}
}
def solve():
# dp[i][j]: 长度为i的数字中余数为j的个数
dp = [[0] * 7 for _ in range(10)]
# cnt[i]: 余数为i的数字总个数
cnt = [0] * 7
# num[i]: 10的i次方
num = [10] * 10
# 预处理10的幂
for i in range(1, 10):
num[i] = 10 * num[i-1]
n = int(input())
nums = list(map(int, input().split()))
# 处理每个输入的数字
for v in nums:
# 计算数字长度
length = 0
while v // num[length] > 0:
length += 1
# 计算对7的余数
mod = v % 7
cnt[mod] += 1
dp[length][mod] += 1
# 计算结果
res = (cnt[0]-1) * cnt[0] # 处理余数为0的情况
# 处理其他余数的情况
for i in range(1, 7):
if cnt[i] == 0:
continue
for x in range(10):
for y in range(7):
if dp[x][y] == 0:
continue
# 检查拼接后是否能被7整除
if (i * num[x]) % 7 == (7 - y) % 7:
if i == y:
res += (cnt[i]-1) * dp[x][y]
else:
res += cnt[i] * dp[x][y]
print(res)
solve()
算法及复杂度
- 算法：动态规划 + 数学
- 时间复杂度：
，其中
是常数(70)，表示余数和长度的组合数
- 空间复杂度：
，使用固定大小的数组
关键点
- 状态编码
- 状态转移
- 处理边界情况
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long countDarkStrings(int n) {
// 如果长度小于3，直接计算
if (n <= 0) return 0;
if (n == 1) return 3;
if (n == 2) return 9;
// dp[i][state]表示长度为i，最后三个字符状态为state的字符串数量
vector<vector<long long>> dp(n + 1, vector<long long>(27, 0));
// 初始化长度为1的情况
dp[1][0] = 3; // A=0, B=1, C=2
// 初始化长度为2的情况
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
dp[2][i * 3 + j]++;
}
}
// 动态规划
for (int i = 3; i <= n; i++) {
for (int last = 0; last < 27; last++) {
int x = last / 9; // 倒数第三个字符
int y = (last / 3) % 3;// 倒数第二个字符
int z = last % 3; // 倒数第一个字符
for (int next = 0; next < 3; next++) {
// 检查新的三个字符是否包含ABC
if (!containsABC(y, z, next)) {
int newState = (y * 3 + z) * 3 + next;
dp[i][newState] += dp[i-1][last];
}
}
}
}
// 统计所有暗黑字符串
long long result = 0;
for (int state = 0; state < 27; state++) {
result += dp[n][state];
}
return result;
}
private:
// 检查三个字符是否包含ABC
bool containsABC(int a, int b, int c) {
vector<bool> has(3, false);
has[a] = has[b] = has[c] = true;
return has[0] && has[1] && has[2];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while (cin >> n) {
Solution sol;
cout << sol.countDarkStrings(n) << endl;
}
return 0;
}
import java.util.*;
public class Main {
static class Solution {
public long countDarkStrings(int n) {
if (n <= 0) return 0;
if (n == 1) return 3;
if (n == 2) return 9;
long[][] dp = new long[n + 1][27];
// 初始化
dp[1][0] = 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
dp[2][i * 3 + j]++;
}
}
// 动态规划
for (int i = 3; i <= n; i++) {
for (int last = 0; last < 27; last++) {
int x = last / 9;
int y = (last / 3) % 3;
int z = last % 3;
for (int next = 0; next < 3; next++) {
if (!containsABC(y, z, next)) {
int newState = (y * 3 + z) * 3 + next;
dp[i][newState] += dp[i-1][last];
}
}
}
}
long result = 0;
for (int state = 0; state < 27; state++) {
result += dp[n][state];
}
return result;
}
private boolean containsABC(int a, int b, int c) {
boolean[] has = new boolean[3];
has[a] = has[b] = has[c] = true;
return has[0] && has[1] && has[2];
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
Solution sol = new Solution();
System.out.println(sol.countDarkStrings(n));
}
sc.close();
}
}
class Solution:
def count_dark_strings(self, n: int) -> int:
if n <= 0:
return 0
if n == 1:
return 3
if n == 2:
return 9
# dp[i][state]表示长度为i，最后三个字符状态为state的字符串数量
dp = [[0] * 27 for _ in range(n + 1)]
# 初始化
dp[1][0] = 3
for i in range(3):
for j in range(3):
dp[2][i * 3 + j] += 1
# 动态规划
for i in range(3, n + 1):
for last in range(27):
x = last // 9 # 倒数第三个字符
y = (last // 3) % 3 # 倒数第二个字符
z = last % 3 # 倒数第一个字符
for next_char in range(3):
# 检查新的三个字符是否包含ABC
if not self.contains_abc(y, z, next_char):
new_state = (y * 3 + z) * 3 + next_char
dp[i][new_state] += dp[i-1][last]
return sum(dp[n])
def contains_abc(self, a: int, b: int, c: int) -> bool:
has = [False] * 3
has[a] = has[b] = has[c] = True
return all(has)
def main():
while True:
try:
n = int(input())
sol = Solution()
print(sol.count_dark_strings(n))
except EOFError:
break
if __name__ == "__main__":
main()
算法及复杂度
- 算法：动态规划
- 时间复杂度：
- 空间复杂度：
查看12道真题和解析
，这工资还不如去摇奶茶