子2023(DP)

时间：2024-11-16 07:34:27

问题描述
小蓝在黑板上连续写下从 1到 2023 之间所有的整数，得到了一个数字序列:S =12345678910111213...20222023。小蓝想知道 S 中有多少种子序列恰好等于 2023?
以下是 3 种满足条件的子序列(用中括号标识出的数字是子序列包含的数字)1[2]345678910111[21314151617181920212223...1[2]34567891[0111[2131415161718192021222[3...1[2]345678910|111213141516171819[21021222[3....注意以下是不满足条件的子序列，虽然包含了 2、0、2、3 四个数字，但是顺序不对:1[2]345678910111[2131415161718192[0]21222[3....


答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#include <iostream>
#include <string>
using namespace std;

int main() {
    string S = "";
    for (int i = 1; i <= 2023; ++i) {
        S += to_string(i);
    }

    long long count_2 = 0, count_20 = 0, count_202 = 0, count_2023 = 0;

    for (char c : S) {
        if (c == '2') {
            count_2++;
            count_202 += count_20;
        } else if (c == '0') {
            count_20 += count_2;
        } else if (c == '3') {
            count_2023 += count_202;
        }
    }

    cout << count_2023 << endl;

    return 0;
}

将从 1 到 2023 的所有整数用 to_string() 转换成字符串并拼接到 S 中。   #include <string>

使用 long long 是为了防止整数溢出。

count_2 用来记录子序列中出现 2 的次数。

count_20 用来记录子序列中出现 20 的次数。

count_202 用来记录子序列中出现 202 的次数。

count_2023 用来记录子序列中出现 2023 的次数。

对于字符串 S 中的每个字符，依次进行判断：

  • 如果遇到 2，这意味着我们可以开始一个新的子序列 2，因此 count_2 增加。遇到第二个 2 时，可以与前面的 20 形成 202，因此 count_202 增加 count_20。
  • 如果遇到 0，则表示我们可以与前面的 2 形成 20，因此 count_20 增加 count_2。
  • 如果遇到 3，则表示我们可以与前面的 202 形成 2023，因此 count_2023 增加 count_202。

实例

  • S = "220203"
  • 状态变量：
    • count_2 = 0
    • count_20 = 0
    • count_202 = 0
    • count_2023 = 0

遍历字符串 S

Step 1: c = '2'
  • count_2 自增：count_2 = 1
  • 其他状态变量不变。
  • 当前状态：
    • count_2 = 1
    • count_20 = 0
    • count_202 = 0
    • count_2023 = 0
Step 2: c = '2'
  • count_2 自增：count_2 = 2（有两个位置的“2”可以作为起点）
  • 其他状态变量不变。
  • 当前状态：
    • count_2 = 2
    • count_20 = 0
    • count_202 = 0
    • count_2023 = 0
Step 3: c = '0'
  • count_20 增加 count_2 的值：count_20 = 2（两种“2”可以与“0”形成“20”）
  • 其他状态变量不变。
  • 当前状态：
    • count_2 = 2
    • count_20 = 2
    • count_202 = 0
    • count_2023 = 0
Step 4: c = '2'
  • count_2 自增：count_2 = 3
  • count_202 增加 count_20 的值：count_202 = 2（两种“20”可以与“2”形成“202”）
  • 当前状态：
    • count_2 = 3
    • count_20 = 2
    • count_202 = 2
    • count_2023 = 0
Step 5: c = '0'
  • count_20 增加 count_2 的值：count_20 = 5（三种“2”可以与“0”形成新的“20”）
  • 其他状态变量不变。
  • 当前状态：
    • count_2 = 3
    • count_20 = 5
    • count_202 = 2
    • count_2023 = 0
Step 6: c = '3'
  • count_2023 增加 count_202 的值：count_2023 = 2（两种“202”可以与“3”形成“2023”）
  • 其他状态变量不变。
  • 当前状态：
    • count_2 = 3
    • count_20 = 5
    • count_202 = 2
    • count_2023 = 2

最终结果

  • count_2023 = 2
  • 输出 2

相关文章