专栏文章

P2602 [ZJOI2010] 数字计数

GGUO120822
P2602题解参与者 34已保存评论 37

文章操作

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

当前评论
36 条
当前快照
1 份
快照标识符
@miq8q4np
此快照首次捕获于
2025/12/04 00:47
3 个月前
此快照最后确认于
2025/12/04 00:47
3 个月前
查看原文
非常好懂又简洁的题解，不压行只有 9 行！
思路来源：leomaster
数据范围很大，考虑数位dp小学奥数。
题目要求计算 00 到 99 的答案，直接枚举，对于每一个数计算。
下文记 f(n,x)f(n,x) 表示 nn 以内，xx 的答案。
由于是求 ll 到 rr 的答案，我们容斥一下，用 rr 的答案减去 ll 的答案。
对于每一位造成贡献，于是我们枚举 ii。
ii 为 11，个位。
ii 为 1010，十位。
一直枚举到 nn 的最后一位。
来考虑每一位。
分两种情况讨论：
  1. 前面填更小的，一共 n/i/10n/i/10 种可能，乘上后面随便填，这一位就是 n/i/10∗in/i/10*i。
  2. 前面填相同的，若这一位相同，那么后面只能填更小的 00 到 nn 取余 ii 一共 nn 取余 ii 再加 11 种可能。
  3. 这一位更小，后面随便填，一共 ii 种可能。
CPP
#include<stdio.h>
typedef long long ll;ll a,b,i;
inline ll f(ll n,ll x){
	ll cnt=0,i;for (i=1;n/i;i*=10){ 
		cnt+=n/i/10*i-(x==0)*i;
		if (x<n%(i*10)/i) cnt+=i;
		else if (x==n%(i*10)/i) cnt+=n%i+1;
	}return cnt;
}int main(){scanf("%lld%lld",&a,&b);for (i=0;i<=9;i++) printf("%lld ",f(b,i)-f(a-1,i));}

评论

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

正在加载评论...