专栏文章

喵

AAmaoFox
P12884题解参与者 9已保存评论 10

文章操作

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

当前评论
10 条
当前快照
1 份
快照标识符
@mip22zyo
此快照首次捕获于
2025/12/03 04:54
3 个月前
此快照最后确认于
2025/12/03 04:54
3 个月前
查看原文
喵呜。本喵就大发慈悲地讲解一下这道整齐的数的题解喵。(≧ω≦)

大意

给定一个上界数 nn 和阈值 mm，统计 [0,n][0, n] 范围内所有整齐的数的个数喵。一个数是整齐的，当且仅当它所有相邻数位差的绝对值之和不超过 mm 喵。比如数 123123 的和是 ∣1−2∣+∣2−3∣=2|1-2|+|2-3|=2 喵。

思路

喵哼哼。这种数字统计问题当然要用数位 DP 解决喵。本喵会用一个记忆化搜索来优雅地处理喵。(ฅ´ω`ฅ)

状态设计

本喵设计的状态是：dp[pos][last][sum][tight]喵～解释一下：
  • pos：当前处理到第几位；（从高到低喵）
  • last：上一位的数字；（如果前面都是 00，用 1010 表示喵）
  • sum：当前相邻数位差的绝对值之和；
  • tight：是否紧贴上界。（前面选的数都和 nn 一样喵）

状态转移

分两种情况处理喵：
  • 前导零状态（last == 10）
    • 选 00：保持前导零状态喵。
    • 选非 00：结束前导零，更新 last 但 sum 仍然是 00。（因为是第一位喵）
  • 正常状态
    • 计算当前位与上一位的差 `diff = abs(last - d)。
    • 如果 sum + diff > m 就跳过。否则更新 sum += diff。
当处理完所有位数时（pos == len），就返回 11 喵。

代码

CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 20, M = 205;

int dp[N][11][M][2];
string s;
int m;
int len;

int dfs(int pos, int last, int sum, bool tight) {
  if (pos == len) {
    return (sum <= m) ? 1 : 0;
  }
  if (dp[pos][last][sum][tight] != -1) {
    return dp[pos][last][sum][tight];
  }
  int up = tight ? (s[pos] - '0') : 9;
  int res = 0;
  for (int d = 0; d <= up; d++) {
    if (last == 10) {
      int new_last = (d == 0) ? 10 : d;
      int new_sum = sum;
      bool new_tight = tight && (d == up);
      res += dfs(pos + 1, new_last, new_sum, new_tight);
    } else {
      int diff = abs(last - d);
      int new_sum = sum + diff;
      if (new_sum > m) {
        continue;
      }
      bool new_tight = tight && (d == up);
      res += dfs(pos + 1, d, new_sum, new_tight);
    }
  }
  return dp[pos][last][sum][tight] = res;
}

signed main() {
  int n;
  cin >> n >> m;
  s = to_string(n);
  len = s.size();
  memset(dp, -1, sizeof(dp));
  cout << dfs(0, 10, 0, 1);
}
喵呜。说实话本喵为了题解写了一些比较“规范”的变量名，看着觉得完全是 AI 写的喵。
由于记忆化的存在，时间复杂度显然和空间复杂度是一样的喵，因为每个状态只计算一次，之后就直接调用了喵。
很重要的建议喵！表示当前处于前导 00 的状态，把 last 设置成 10\bold{10} 是最方便的做法了喵。真不要和本喵早年一样单开一维然后把自己累死了喵。
哼。本喵的讲解就到这里喵。要好好理解状态设计的意义喵，这才是数位 DP 的精髓喵。(๑•̀ㅂ•́)و✧
唉我怎么又写了一篇莫名其妙的东西。

评论

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

正在加载评论...