妹子刚学CSP求助
查看原帖
妹子刚学CSP求助
28910
览遍千秋七海楼主2019/8/30 20:53

刚学数位DP...

不知道为啥过不了样例...

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
	x=0;char ch=1;int fh;
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-'){
		fh=-1;ch=getchar();
	}
	else fh=1;
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	x*=fh;
}

int a,b;

struct node{
	int a[10];
	node(){
		memset(a,0,sizeof(a));
	}
	node operator + (node aa)const{
		node ret;
		for(int i=0;i<=9;i++) ret.a[i]=a[i]+aa.a[i];
		return ret;
	}
};

node opt[17][30];
bool flag[17][30];
int n[17],wp;
node dfs(int step,int num,bool lim,bool zer){
	if(flag[num][step]) return opt[num][step];
	int tp;node ans;
	if(num!=0||!zer) ans.a[num]=1;
	if(step>=wp) return ans;
	if(lim) tp=n[step+1];else tp=9;
	for(int i=0;i<=tp;i++){
		ans=ans+dfs(step+1,i,lim&&(i==tp),zer||i);
	}
	flag[num][step]=1;
	return opt[num][step]=ans;
}

void chk(int x){
	wp=0;
	while(x){
		n[++wp]=x%10;
		x/=10;
	}
	reverse(n+1,n+wp+1);
}

node solve(int x){
	memset(flag,false,sizeof(flag));
	chk(x);
	node ret;
	for(int i=0;i<=n[1];i++){
		ret=ret+dfs(1,i,(i==n[1]),i==0);
	}
	return ret;
}

signed main(){
	read(a);read(b);
	node aa=solve(a-1),bb=solve(b);
	if(a/10==0){
		for(int i=0;i<10;i++) if(aa.a[i]) aa.a[i]--;
	}
	for(int i=0;i<9;i++) printf("%lld ",bb.a[i]-aa.a[i]);
	printf("%lld\n",bb.a[9]-aa.a[9]);
//	for(int i=0;i<9;i++) printf("%lld ",bb.a[i]);
//	printf("%lld\n",bb.a[9]);
	return 0;
}
2019/8/30 20:53
加载中...