reverse模拟可过的数位DP

秒速五厘米 2023-10-10 10:24 26阅读 0赞

我再也不用模拟去做数位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好不好）

最后附上我亲爱的代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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;
        }
    }

要不是我压行我觉得我打不下去。。。。。。

转载于:https://www.cnblogs.com/three-D/p/11441600.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif