专栏文章

题解：P14074 [GESP202509 五级] 有趣的数字和

封封禁用户

2025/10/01 14:44P14074题解参与者 1已保存评论 0

文章操作

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

当前评论: 0 条
当前快照: 1 份
快照标识符: @minqmf5f
此快照首次捕获于: 2025/12/02 06:45
此快照最后确认于: 2025/12/02 06:45

传送门

题解

枚举

开始时，我想的是枚举，不过数据范围

1≤l≤r≤10^9

1≤l≤r≤10 ^9

，直接遍历区间并检查每个数会超时，于是我想到了数位DP

数位DP

定义

：

$count(n)$ 为从 $1$ 到 $n$ 的有趣数的个数
$sum(n)$ 为从 $1$ 到 $n$ 的有趣数的和

那么答案为

sum(r) - sum(l-1)

状态转移方程

设

dp[a][b][c]

表示：

当前处理到二进制第 $a$ 位（从高位到低位）
$b$ = 当前已选 $1$ 的个数的奇偶性（ $0$ 表示偶数， $1$ 表示奇数）
$c$ = 是否紧贴上界 $n$ $（1=是，0=否）$

同时我们需要两个

DP

数组：

dp1[pos][cnt][tight]：

满足条件的数的个数

dp2[pos][cnt][tight]：

满足条件的数的和

方程式

自己推吧 ~~，其实我也不会hhh~~

结

最后

~~求通过QWQ~~

评论

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

正在加载评论...