首页 > 代码库 > BZOJ1833 数位DP
BZOJ1833 数位DP
数位DP随便搞搞.
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<string> #include<iomanip> #include<algorithm> #include<map> using namespace std; #define LL long long #define FILE "dealing" #define up(i,j,n) for(LL i=j;i<=n;++i) #define db double #define ull unsigned long long #define eps 1e-10 #define pii pair<LL,LL> LL read(){ LL x=0,f=1,ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();} return f*x; } const LL maxn=102,maxm=20000,mod=10000007,inf=(LL)(2e9); template<class T>bool cmax(T& a,T b){return a<b?a=b,true:false;} template<class T>bool cmin(T& a,T b){return a>b?a=b,true:false;} template<class T>T min(T& a,T& b){return a<b?a:b;} template<class T>T max(T& a,T& b){return a>b?a:b;} LL a,b,w[20],r[20],cnt[maxn],f[20][20],p,mi[maxn],g[maxn][maxn],sum[maxn]; LL s[20]; void dfs(LL pos,bool flag){ if(pos==-1)return; if(!flag){ for(LL i=1;i<=9;i++)cnt[i]+=p*(f[pos][i]+mi[pos]*s[i]); cnt[0]+=p*(f[pos][0]+s[0]*mi[pos]); return; } for(LL i=0;i<=w[pos];i++){ bool flg=0; for(LL j=1;j<10;j++)if(s[j]){flg=1;break;} if(flg||i)s[i]++; dfs(pos-1,w[pos]==i); if(flg||i)s[i]--; } } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); a=read(),b=read()+1; mi[0]=1;for(LL i=1;i<=14;i++)mi[i]=mi[i-1]*10; for(LL i=1;i<=14;i++){ for(LL j=0;j<=9;j++){ f[i][j]=f[i-1][j]*10+mi[i-1]; } } w[0]=0; while(b){ w[++w[0]]=b%10; b/=10; } memset(s,0,sizeof(s)); p=1;dfs(w[0],1); up(i,1,w[0]-1)cnt[0]-=mi[i-1]; LL Max=w[0]; memset(w,0,sizeof(w)); while(a){ w[++w[0]]=a%10; a/=10; } memset(s,0,sizeof(s)); up(i,1,w[0]-1)cnt[0]+=mi[i-1]; w[0]=Max; p=-1;dfs(Max,1); up(i,0,8)printf("%lld ",cnt[i]);printf("%lld\n",cnt[9]); return 0; }
BZOJ1833 数位DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。