专栏文章

题解：P13890 [蓝桥杯 2023 省 Python A] 奇怪的数

OOberon_Qwl
P13890题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minkpvrb
此快照首次捕获于
2025/12/02 04:00
3 个月前
此快照最后确认于
2025/12/02 04:00
3 个月前
查看原文

P13890 [蓝桥杯 2023 省 Python A] 奇怪的数 【题解】

一道不错的练手动规

题目简述

要求输出满足以下条件的长度为 nn 的数的个数：
  • 奇数数位上是奇数 （1,3,5,7,9）
  • 偶数数位上是偶数 （0,2,4,6,8）
  • 任意 55 个连续数位的和 ≤m\le m 显然 nn 最大 2×1052×10^5，暴力肯定超，所以依旧动态规划。

思路

核心观察要点
  1. 每个数位的取值范围固定：奇数位有 55 种选择，偶数位有 55 种选择
  2. 约束条件只涉及连续 55 个数位，因此可以用最近 44 个数位的状态来推导新的状态
动规部分
代码实现很简单；
首先定义一个四维 dp 表示最后四个数位的索引为 a,b,c,da,b,c,d 时的合法数的数量。这里的索引对应预设的取值数组：
CPP
// v[0]存奇数位，v[1]存偶数位
int v[2][5]={{1,3,5,7,9},{0,2,4,6,8}};
其次，列状态转移方程：当新增第 55 个数位 ee 时，需要检查这 55 个数位的和是否 ≤m\le m。若合法，则状态从 (a,b,c,d)(a,b,c,d) 转移到 (b,c,d,e)(b,c,d,e),具体的：
CPP
// 计算5个连续数位的和
int sum=v[aa][a]+v[ab][b]+v[ac][c]+v[ad][d]+v[ae][e];
if (sum<=m)
{
    // 状态转移：(a,b,c,d)->(b,c,d,e)
    nd[b][c][d][e]=(nd[b][c][d][e]+cnt)%mod;
}
再是初始化：对于长度为 44 的数，所有符合奇偶位要求的组合都合法（因为不需要检查 55 个连续数位）
最后滚动数组优化空间
具体迭代过程:
CPP
for (int l = 4; l < n; ++l)
{
       int nd[5][5][5][5] = {0};//新状态存储数组,作临时存储新状态和状态转移的载体以及滚动更新作用
       int res = l + 1; //新增数位的位置
       int ae = 1 - (res % 2); //新增数位的取值类型
       
     
       for (int a = 0; a < 5; ++a) {
           for (int b = 0; b < 5; ++b) {
               for (int c = 0; c < 5; ++c) {
                   for (int d = 0; d < 5; ++d) {
                       int cnt = dp[a][b][c][d];
                       if (cnt == 0) continue;
                       int resa = l - 3, aa = 1 - (resa % 2);
                       int resb = l - 2, ab = 1 - (resb % 2);
                       int resc = l - 1, ac = 1 - (resc % 2);
                       int resd = l, ad = 1 - (resd % 2);
                   
                       for (int e = 0; e < 5; ++e) {
                           int sum = v[aa][a] + v[ab][b] + v[ac][c] + v[ad][d] + v[ae][e];
                           if (sum > m) continue;
                           nd[b][c][d][e] = (nd[b][c][d][e] + cnt) % mod;
                       }
                   }
               }
           }
       }
       memcpy(dp, nd, sizeof(dp));
   }
其他包括四维 dp 的初始化及输出便不展示了。

总结

没文笔不想写了。
EndEnd

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...