背景
蒟蒻最近学了学数位DP,数位dp例题,但是蒟蒻太菜了,只能抄题解bushi,可是却发现,连抄都抄不对!
这是蒟蒻的代码,借鉴于@niolle 大佬的题解
#include<cstdio>
#include<string.h>
#define Long long long
#define For(a,b) for(int i=a;i<=b;++i)
struct Node{
Long s[10], sum=0; bool r;
Node (bool r=0):r(r){ memset(s,0,sizeof s); };
Node operator+(Node x){ For(0,9) x.s[i]+=s[i]; x.sum+=sum; return x; }
Node operator-(Node x){ For(0,9) x.s[i]=s[i]-x.s[i]; return x; }
void operator+=(Node x){*this=*this+x; }
//void operator-=(Node x){*this=*this-x; }
} dp[13][2]; int _[13];
Node DFS(int t,bool b,bool z){
Node ans(1); if(t==-1){ ans.sum=1; return ans; }
if(dp[t][z].r&&!b) return dp[t][z];
int en=b?_[t]:9; For(0,en){
Node res=DFS(t-1,b&&i==en,z&&!i);
ans+=res; if(!z||i) ans.s[i]+=res.sum;
} if(!b) dp[t][z]=ans; return ans;
}
Node work(Long a){
int len=0;
while(a) _[len++]=a%10,a/=10;
return DFS(len-1,1,1);
}
main(){
Long a,b; scanf("%ld%ld",&a,&b);
Node res=work(b)-work(a-1);
For(0,9) printf("%ld ",res.s[i]);
}
事实上这份代码提交后就AC了。
蒟蒻的系统是win10,编译器是g++,我发现用这份代码在Windows端按照样例"1 99"输入,输出的竟然是很多很大的负数!蒟蒻中途还尝试直接引用Node DFS(...,Long*_),而_的定义在work函数中,这样竟然必须用Long才能得到相对正确的结果(9 19 20 20 20...). 否则会输出很大的负数。我感到匪夷所思。拆分整数用int还不够吗?这太奇怪了!而且竟然还不是正确答案。operator-的部分,只有改为res1=work...,res2=work...,print res1.x[i]-res2.x[i]才能得到正确的结果。我真的希望能有个正常些的编译环境,因为实在受不了了。