WA 0分求调

感觉我的代码太猎奇了还是讲一下思路吧

设

f_{i,a}

为

i

位数结尾为

a

的方案数（允许前导零）：

f_{i,a}=f_{i-1,a}\times10+10^{i-1}

然后为了避免前导零被算入记录0时的答案：

f_{i,0} \leftarrow f_{i,0}-\sum_{j=0}^{i-1}10^j

如果思路错了，可以指出问题吗qwq

感谢乐于助人的大佬。

CPP

#include<iostream>
#define int long long
using namespace std;
int a,b,f[15][15],digit[15],top;
int pow_10(int x){
	int ans=1;
	for(int i=1;i<=x;i++) ans*=10;
	return ans;
}
void init(){
	for(int i=0;i<=9;i++) f[1][i]=1;
	for(int i=2;i<=13;i++){
		for(int j=0;j<=9;j++){
			f[i][j]=f[i-1][j]*10+pow_10(i-1);
		}
	}
    for(int i=2;i<=13;i++){
        for(int j=0;j<=i-1;j++){
            f[i][0]-=pow_10(j);
        }
    }
}
int solve(int x,int d){
	top=0;
	while(x){
		digit[++top]=x%10;
		x/=10;
	}
	int ans=0;
	for(int i=top;i>=1;i--){
		for(int j=0;j<(digit[i]+(i==1));j++){
            ans+=f[i-1][d];
            if(j==d&&j) ans+=pow_10(i-1);
            if(i+1<=top&&digit[i+1]==d) ans+=pow_10(i-1);
        }
	}
    return ans;
}
signed main(){
	init();
	cin>>a>>b;
	for(int i=0;i<=9;i++) cout<<(solve(b,i)-solve(a-1,i))<<" ";
}

讨论操作

回复

相关推荐

WA 0分求调