我再也不用模拟去做数位dp了！！！
这是噩梦这是噩梦这是噩梦！！！
这nm比大模拟恶心n倍。。。。
利用各种闲暇时间做了大概1周？？？
我nm.........真的恶心。。。思路考试的时候就有且对
但实现起来..........
细节多到爆炸。。。
考虑大过r的和小过l的分别考虑其每一位计入答案注意左右边界还不能超出
然后考虑当前这一位的翻转位能不能选还要考虑unsigned long long 不能爆的问题
所以大的还是比较好打（这只是相对于小的来说）
小的话....你会认为只是把大的翻过了一样的思想
抱歉我开始也是这么想的
然后兴奋的走上一条不归路。。。
一个细节就是一节课来调 我看见自己写的那份代码就恶心。。。。
noooooooooooooooooooooo我的时光我的青春！！！
还要考虑0？？？
所以分成了最恶心情况得有3部分统计答案。。。
第一部分从l->999999...
第二部分从100000...->l
第三部分从10000000...->r -> 这有点不好搞所以统一把多于l位数的位卡掉
这三种情况下还是考虑每一位以及边界问题，以及算重？？？？？？
对就是这么恶心。。。还会有算重的情况所以要减去（说起来简单做起来想哭）
哦对了
是不是最后一个（翻过来对应第一位）还得单独考虑。。。。。。。。。。。。
nw bw rw 用来搞会不会爆范围。。。。。还得考虑如果l位数小于r位数得变100000...各种都得变
如果r大于l位数还得变999999。。。各种都得变
而且因为有三部分最后还得变回来当然还有什么nw rw bw 爆掉unsigned long long 的东西？？？
然后发现并用不到最大的那个所以快速幂什么的按位取什么的-- ++ × 将近20个if啦什么的都是小事小事。。。。。。。。。。
所以我打了3.9k没有复制粘贴每处都不一样（我光那道题才1.几k好不好）
最后附上我亲爱的代码
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define ull unsigned long long ull l,r,tl,tr,num,ansb,anss; ull w1[100],w2[100],nw[100],bw[100],rw[100],tp; ull a,b,fir[100],sec[100],tf[100],ts[100],numf,nums; inline ull qpow(ull a,int b){ ull ans=1; while(b){ if(b&1) ans=ans*a; b>>=1,a*=a; } return ans; } inline ull read() { ull t=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') t=(t<<3)+(t<<1)+(ch^48),ch=getchar(); return t; } inline void bigger(){ for(register int i=2;i<=nums;++i) tr=tr*10+ts[i]; tp=qpow(10,nums-1); for(register int i=1;i<=nums;++i) w1[i]=w1[i-1]*10+fir[i],w2[i]=w2[i-1]*10+sec[i]; for(register int i=2;i<=nums;++i) nw[i]=tr%tp,bw[i]=r%tp,rw[i]=l%tp,tp/=10;//cout<<nw[i]<<' '<<bw[i]<<"#"<<endl; nw[nums+1]=0,bw[nums+1]=0,rw[nums+1]=0; if(numf<nums){ w1[1]=1,fir[1]=1; for(register int i=2;i<=nums;++i) fir[i]=0,w1[i]=w1[i-1]*10; } for(register int i=nums;i;--i){ num=w2[i]/10-w1[i]/10+1; ansb+=num*(9-sec[nums-i+1])-(9-max(sec[nums-i+1],sec[i])); if(fir[i]>sec[nums-i+1]) ansb-=fir[i]-sec[nums-i+1]-1; if(nw[i+1]>bw[i+1]&&sec[i]>sec[nums-i+1]) --ansb; //cout<<nw[i+1]<<' '<<rw[i+1]<<"#"<<endl; if(numf==nums&&nw[i+1]<rw[i+1]&&fir[i]>sec[nums-i+1]) --ansb; } } inline void smaller() { for(register int i=1;i<=numf;++i) fir[i]=tf[numf-i+1]; for(register int i=2;i<=numf;++i) tl=tl*10+tf[i]; tp=qpow(10,numf-1); for(register int i=1;i<=numf;++i) w1[i]=w1[i-1]*10+fir[i],w2[i]=w2[i-1]*10+sec[i]; for(register int i=2;i<=numf;++i) nw[i]=tl%tp,bw[i]=l%tp,rw[i]=r%tp,tp/=10; nw[numf+1]=0,bw[numf+1]=0,rw[numf+1]=0; if(nums>numf){ w2[1]=9,sec[1]=9; for(register int i=1;i<=numf;++i) sec[i]=9,w2[i]=w2[i-1]*10+9; } long long anst=0; for(register int i=numf;i;--i){ num=w2[i]/10-w1[i]/10+1; anss+=num*fir[numf-i+1]-min(fir[i],fir[numf-i+1]); if(i^1){ anst+=(w1[i]/10-qpow(10,i-2)+1)*fir[numf-i+1];//min(fir[i],fir[numf-i+1]); if(fir[i]<fir[numf-i+1]) anst-=fir[numf-i+1]-fir[i]-1; if(i!=numf&&fir[i]<fir[numf-i+1]&&nw[i+1]>=bw[i+1]) --anst; } else{ if(fir[numf-i+1]) --anst; anst+=fir[numf-i+1]; if(fir[i]<fir[numf-i+1]) anst-=fir[numf-i+1]-fir[i]-1; if(fir[i]<fir[numf-i+1]&&nw[i+1]>=bw[i+1]) --anst; if(fir[i]>fir[numf-i+1]||(fir[i]==fir[numf-i+1]&&nw[i+1]<bw[i+1])) --anst; } if(sec[i]<fir[numf-i+1]) anss-=fir[numf-i+1]-sec[i]-1; if(nw[i+1]<bw[i+1]&&fir[i]<fir[numf-i+1]) --anss; if(nw[i+1]>rw[i+1]&&sec[i]<fir[numf-i+1]) --anss; } //cout<<anss<<' '<<anst<<"#"<<endl; if(nums-numf>0){ anss+=anss*(nums-numf-1)+anst*(nums-numf-1); long long kp=anss; for(register int i=1;i<=nums;++i) sec[i]=ts[nums-i+1]; tr=0,tp=10; for(register int i=1;i<=numf;++i) tr=tr*10+sec[i],w2[i]=w2[i-1]*10+sec[i]; for(register int i=1;i<=numf;++i) rw[numf-i+1]=tr%tp,tp*=10; for(register int i=numf;i;--i){ if(i^1){ anss+=(w2[i]/10-qpow(10,i-2)+1)*fir[numf-i+1]; if(sec[i]<fir[numf-i+1]) anss-=fir[numf-i+1]-sec[i]-1; if(i!=numf&&sec[i]<fir[numf-i+1]&&nw[i+1]>rw[i+1]) --anss; } else{ if(fir[numf-i+1]) --anss; anss+=fir[numf-i+1]; if(sec[i]<fir[numf-i+1]) anss-=fir[numf-i+1]-sec[i]-1; if(sec[i]<fir[numf-i+1]&&nw[i+1]>rw[i+1]) --anss; //if(sec[i]>fir[numf-i+1]||(sec[i]==fir[numf-i+1]&&nw[i+1]<rw[i+1])) --anss; } } } } int main() { //freopen("reverse6.in","r",stdin); //freopen("c.out","w",stdout); int t=read(); a=read(),b=read(); while(t--){ l=read(),r=read(); tl=l,tr=r; memset(fir,0,sizeof(fir)); ansb=0,anss=0,numf=0,nums=0,w1[0]=0,w2[0]=0; while(tl) tf[++numf]=tl%10,tl/=10; while(tr) ts[++nums]=tr%10,tr/=10; for(register int i=1;i<=numf;++i) fir[i]=tf[numf-i+1]; for(register int i=1;i<=nums;++i) sec[i]=ts[nums-i+1]; bigger(); smaller(); //cout<<ansb<<' '<<anss<<"#"<<endl; cout<<r-l+1-ansb-anss<<endl; } }
要不是我压行我觉得我打不下去。。。。。。