投稿
  1. 高性能架构探索首页
  2. C/C++

完美数字

admin • • C/C++ • 阅读 131

题解 完美数字

前言

fr大佬的原创题，菜鸡受教了

题面

给出两个数字集合S和T，其中元素均为0到9之间的整数。

定义“完美数字”为数位中包含S中所有的数且不包含T中任意一个数的数字。

例如S={1,3,4}，T={7,8}，则1345、341166、4133129都是完美数字。

而13、8431、34171都不是完美数字（因为13数位中不包含44，8431和34171中虽然包含了1、3、4这三个数但又包含88和77）。

求[l,r]中所有完美数字的和。

对于100%的数据，t<=2000，1<=l<=r<(10^{9})，保证S和T中的元素均为[0,9]中的整数且互不相同。

题解

这道题，数位dp可以一眼就看出来，状压也能在思考过程中顺势带出来

规定如下:

(state)存状态，(1<<i)表示数字(i)存在于该状态下

(move(k))表示(1<<k)

(g[state][k])表示状态为state的k位数的个数，且零可以任意摆放

(hg[state][k])表示状态为state的k位数的和，且零可以任意摆放

(hf[state][k])表示状态为state的k位数的和，且零符合通则

由于求解hf的过程的时候需要利用到g和hg，因此我们顺序求出来

接下来会出现大量的"state中1的位置"与"state中1的个数"，提前解释一下。前者根据state的定义方法可知，((1<<k))存的是(数字k)存在；后者指的是该状态的数字由几种数字构成(如134，由1、3、4构成)

求解 (g[state][k])

由于dp求解，因此在求(g[state][k])的时候(g[][k-1])一定已经求解出来了。因此可以理解为在(k-1)位数的基础上再添加一个数字。

假设新添加的数字在(k-1)位数中出现过，那么(state)中每一个数字都可以带来(g[state][k-1])种可能，因此

[g[state][k]+=sum (state中1的个数)times g[state][k-1]
]

假设新添加的数字在(k-1)位数中没有出现过，那么每一个数字带来(state-move())种可能，因此

[g[state][k]+=sum g[state-move(state中1的位置)][k-1]
]

求解 (hg[state][k])

同样道理分类讨论

假设新添加的数字在(k-1)位数中出现过，那么(state)中每一个数字都可以带来(g[state][k-1])种可能,因此

新添加的数字：

[hg[state][k]+=sum (state中1的位置)times 10^{k-1} times g[state][k-1]
]

原来的(k-1)位数字：

[hg[state][k]+=sum (state中1的个数)times hg[state][k-1]
]

假设新添加的数字在(k-1)位数中没有出现过，那么每一个数字带来(state-move())种可能，因此:

新添加的数字：

[hg[state][k]+=sum (state中1的位置)times 10^{k-1} times g[state-move(state中1的位置)][k-1]
]

原来的(k-1)位数字：

[hg[state][k]+=sum hg[state-move(state中1的位置)][k-1]
]

求解 (hf[state][k])

还是分类讨论~~其实与(hg[state][k])大同小异，只是由于零不能前置，由略微地更改。为了严谨还是完整叙述一遍

假设新添加的数字在(k-1)位数中出现过，那么(state)中每一个数字都可以带来(g[state][k-1])种可能,因此

新添加的数字：

[hg[state][k]+=sum (state中1的位置[去零])times 10^{k-1} times g[state][k-1]
]

原来的(k-1)位数字：

[hg[state][k]+=sum (state中1的个数[去零])times hg[state][k-1]
]

假设新添加的数字在(k-1)位数中没有出现过，那么每一个数字带来(state-move())种可能，因此:

新添加的数字：

[hg[state][k]+=sum (state中1的位置[去零])times 10^{k-1} times g[state-move(state中1的位置)][k-1]
]

原来的(k-1)位数字：

[hg[state][k]+=sum hg[state-move(state中1的位置[去零])][k-1]
]

呼，dp推完了~~

(f[state][k])是在思路不清地时候瞎推的

手写版：

VsKkLQ.md.jpg

代码版：

code:

void init(){
    for(register int i=0;i<=9;++i) g[move(i)][1]=1;
    for(register int p=2;p<=9;++p){
        for(register int i=1;i<=move(10)-1;++i){
            int sum=0;
            for(register int j=0;j<=9;++j) if(i&move(j)) sum++;
            g[i][p]=sum*g[i][p-1];
            for(register int j=0;j<=9;++j){
                if(i&move(j)){
                    g[i][p]+=g[i-move(j)][p-1];
                }
            }
        }
    }

    for(register int i=1;i<=9;++i) f[move(i)][1]=1;
    for(register int p=2;p<=9;++p){
        for(register int i=1;i<=move(10)-1;++i){

            int sum=0;
            for(register int j=1;j<=9;++j) if(i&move(j)) sum++;
            f[i][p]+=sum*g[i][p-1];

            for(register int j=1;j<=9;++j){
                if(i&move(j)){
                    f[i][p]+=g[i-move(j)][p-1];
                }
            }
        }
    }

    for(register int i=0;i<=9;++i) hg[move(i)][1]=i;
    for(register int p=2;p<=9;++p){
        for(register int i=1;i<=move(10)-1;++i){
            int sum=0,cnt=0;
            for(int k=0;k<=9;++k){
                if(i&move(k)){
                    sum+=k; cnt++;
                }
            }
            hg[i][p]+=sum*tim[p-1]*g[i][p-1];
            hg[i][p]+=cnt*hg[i][p-1];

            for(register int k=0;k<=9;++k){
                if(i&move(k)){
                    hg[i][p]+=k*tim[p-1]*g[i-move(k)][p-1];
                    hg[i][p]+=hg[i-move(k)][p-1];
                }
            }
        }
    }

    for(register int i=1;i<=9;++i) hf[move(i)][1]=i;
    for(register int p=2;p<=9;++p){
        for(register int i=1;i<=move(10)-1;++i){
            int sum=0,cnt=0;
            for(register int k=1;k<=9;++k){
                if(i&move(k)){
                    cnt++; sum+=k;
                }
            }
            hf[i][p]+=sum*tim[p-1]*g[i][p-1];
            hf[i][p]+=cnt*hg[i][p-1];

            for(register int k=1;k<=9;++k){
                if(i&move(k)){
                    hf[i][p]+=k*tim[p-1]*g[i-move(k)][p-1];
                    hf[i][p]+=hg[i-move(k)][p-1];
                }
            }
        }
    }
}

然后有了dp，数位dp小心点处理就ok(。・∀・)ノ

代码

code:

#include <ctime>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int INF=0x3f3f3f3f;

int T;
int l,r;
int s[15],t[15];
ll tim[11]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000ll,10000000000ll};
ll f[1024][15],g[1024][15],hg[1024][15],hf[1024][15];
int ty[1024];
clock_t st,ed;

void work();
inline int read();
inline int move(int);
void init();
ll calculate(int);
bool check(int);

int main(){
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    #endif

    init();
    T=read();
    while(T--) work();

    return 0;
}

void work(){
    l=read(); r=read();
    s[0]=read(); for(int i=1;i<=s[0];++i) s[i]=read();
    t[0]=read(); for(int i=1;i<=t[0];++i) t[i]=read();

    s[s[0]+1]=0; for(int i=1;i<=s[0];++i) s[s[0]+1]|=move(s[i]);
    t[t[0]+1]=0; for(int i=1;i<=t[0];++i) t[t[0]+1]|=move(t[i]);

    ty[0]=0;
    for(int i=1;i<=move(10)-1;++i) if(check(i)) ty[++ty[0]]=i;

    cout<<calculate(r)-calculate(l-1)<<endl;
}

inline int read(){
    char tmp=getchar(); int sum=0; bool flag=false;
    while(tmp<'0'||tmp>'9'){
        if(tmp=='-') flag=true;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9'){
        sum=(sum<<1)+(sum<<3)+tmp-'0';
        tmp=getchar();
    }
    return flag?-sum:sum;

}

inline int move(int k){
    int tmp=1;
    return tmp<<k;
}

void init(){
    for(register int i=0;i<=9;++i) g[move(i)][1]=1;
    for(register int p=2;p<=9;++p){
        for(register int i=1;i<=move(10)-1;++i){
            int sum=0;
            for(register int j=0;j<=9;++j) if(i&move(j)) sum++;
            g[i][p]=sum*g[i][p-1];
            for(register int j=0;j<=9;++j){
                if(i&move(j)){
                    g[i][p]+=g[i-move(j)][p-1];
                }
            }
        }
    }

    for(register int i=1;i<=9;++i) f[move(i)][1]=1;
    for(register int p=2;p<=9;++p){
        for(register int i=1;i<=move(10)-1;++i){

            int sum=0;
            for(register int j=1;j<=9;++j) if(i&move(j)) sum++;
            f[i][p]+=sum*g[i][p-1];

            for(register int j=1;j<=9;++j){
                if(i&move(j)){
                    f[i][p]+=g[i-move(j)][p-1];
                }
            }
        }
    }

    for(register int i=0;i<=9;++i) hg[move(i)][1]=i;
    for(register int p=2;p<=9;++p){
        for(register int i=1;i<=move(10)-1;++i){
            int sum=0,cnt=0;
            for(int k=0;k<=9;++k){
                if(i&move(k)){
                    sum+=k; cnt++;
                }
            }
            hg[i][p]+=sum*tim[p-1]*g[i][p-1];
            hg[i][p]+=cnt*hg[i][p-1];

            for(register int k=0;k<=9;++k){
                if(i&move(k)){
                    hg[i][p]+=k*tim[p-1]*g[i-move(k)][p-1];
                    hg[i][p]+=hg[i-move(k)][p-1];
                }
            }
        }
    }

    for(register int i=1;i<=9;++i) hf[move(i)][1]=i;
    for(register int p=2;p<=9;++p){
        for(register int i=1;i<=move(10)-1;++i){
            int sum=0,cnt=0;
            for(register int k=1;k<=9;++k){
                if(i&move(k)){
                    cnt++; sum+=k;
                }
            }
            hf[i][p]+=sum*tim[p-1]*g[i][p-1];
            hf[i][p]+=cnt*hg[i][p-1];

            for(register int k=1;k<=9;++k){
                if(i&move(k)){
                    hf[i][p]+=k*tim[p-1]*g[i-move(k)][p-1];
                    hf[i][p]+=hg[i-move(k)][p-1];
                }
            }
        }
    }
}

ll calculate(int k){
    ll ans=0;

    if(k<10){
        for(register int i=1;i<=k;++i){
            if(!check(move(i))) continue;
            ans+=i;
        }
        return ans;
    }

    int line[15]; line[0]=0;
    int tmp=k;
    while(tmp){
        line[++line[0]]=tmp%10;
        tmp/=10;
    }

    for(register int p=1;p<line[0];++p){
        for(register int i=ty[1],tmpi=1;tmpi<=ty[0];++tmpi,i=ty[tmpi]){
            if(!check(i)) continue;
            ans+=hf[i][p];
        }
    }

    int rec=0; ll sum=0;
    for(register int p=1;p<line[line[0]];++p){
        rec+=move(p);
        sum+=p;
        for(register int i=1;i<=move(10)-1;++i){
            if(!check(rec|i)) continue;
            ans+=hg[i][line[0]-1];
            ans+=sum*tim[line[0]-1]*g[i][line[0]-1];
        }
        rec-=move(p);
        sum-=p;
    }
    for(register int i=1;i<=t[0];++i) if(line[line[0]]==t[i]) return ans;
    rec+=move(line[line[0]]); sum=line[line[0]]*10;

    for(register int p=line[0]-1;p>=2;--p){
        for(register int i=0;i<line[p];++i){
            bool flag=false;
            if(rec&move(i)) flag=true;
            else rec+=move(i);
            sum+=i;
            for(register int j=1;j<=move(10)-1;++j){
                if(!check(rec|j)) continue;
                ans+=hg[j][p-1];
                ans+=sum*tim[p-1]*g[j][p-1];
            }
            if(!flag) rec-=move(i);
            sum-=i;
        }
        for(register int i=1;i<=t[0];++i) if(t[i]==line[p]) return ans;
        rec|=move(line[p]);
        sum+=line[p]; sum*=10;
    }

    for(register int p=0;p<=line[1];++p){
        int tmprec=rec|move(p);
        ll tmpsum=sum+p;
        if(!check(tmprec)) continue;
        ans+=tmpsum;
    }

    return ans;
}

bool check(int k){
    if((k&s[s[0]+1])!=s[s[0]+1]) return false;
    if(k&t[t[0]+1]) return false;
    return true;
}

原文链接: https://www.cnblogs.com/ticmis/p/13210982.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    完美数字

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/360656

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午1:24
下一篇 2023年3月2日 下午1:24

相关推荐