https://www.luogu.com.cn/problem/P1980
题目描述
试计算在区间 1 到 n 的所有整数中，数字x(0 ≤ x ≤ 9) 共出现了多少次？例如，在 1到11中，即在 1,2,3,4,5,6,7,8,9,10,11 中，数字 1 出现了 4 次。
输入格式
2个整数 n,x 之间用一个空格隔开。
输出格式
1 个整数，表示 x 出现的次数。
输入输出样例
输入 #1复制
11 1
输出 #1复制
4
三个状态：pre 表示前面已有多少个 X 出现。prex 表示前一个数 ，flag 表示前面是否全为 0 。 prex ,flag 专门统计 0 而设 orz… 因为不能统计前导 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[20];
int dp[20][10][10][2];
int n,x;
ll dfs(int pos,int pre,int prex,bool flag,bool limit)
{
if(!flag && x==0 && prex==0 &&pos==-1) return 0;
if(pos==-1) return pre;
if(!limit && dp[pos][pre][prex][flag]!=-1) return dp[pos][pre][prex][flag];
int up=limit ? a[pos] : 9;
ll tmp=0;
for(int i=0;i<=up;i++){
if(i==x) tmp+=dfs(pos-1,(flag&&x==0)||x!=0? pre+1 :pre,i,flag,limit && i==a[pos]);
else tmp+=dfs(pos-1,pre,x>0?true:false,i,limit && i==a[pos]);
}
if(!limit) dp[pos][pre][prex][flag]=tmp;
return tmp;
}
int solve(int x)
{
int pos=0;
while(x) {
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1,0,0,false,true);
}
int main(){
cin>>n>>x;
memset(dp,-1,sizeof dp);
cout<<solve(n)<<endl;
return 0;
}
|