26牛客寒假算法训练营1题解

26牛客寒假算法训练营1题解

学习总结

1. 学习到了状态压缩，我们直接转换为二进制，再直接把二进制转换为数字就可以了。
2. 用的时候这样用就可以了 x>>j.
3. 对于多种选择方案用状态压缩有时候会解决很多问题

复制代码

A.A+B Problem

题目描述

有八个独立的数位显示器，每个显示器的每个二极管被点亮的概率为 ，管与管之间互相独立，显示器
之间也相互独立，求分别显示出两个四位合法数字，且数字之和等于输入的常数 的概率。

• 每个显示器至少亮 1 根（不能全灭）
  
• 每个显示器显示的是合法数字 0..9 0..90..9
  
• 上排 4 个拼成四位数 A AA，下排 4 个拼成四位数 B BB，满足 A + B = C A+B=CA+B=C（允许前导 0）
  

解题
我们可以去先算显示当个数d的概率，七段码，每一个对应两种状态，0，1
那我们完全可以用状态压缩来得到这个所以的情况。
例如 显示0

1. 01110111

复制代码

也就是119，其他的以此类推。
然后我们可以得到每一个数的概率，因为每一个都要亮的概率，所以我们先把每一个数的概率算出来，用

1. x>>j&1来得到这个数到底是1还是0

复制代码

最后直接把一个四位数的表示方法写出来，我们直接用取最后一位一直取，如果不够就直接前导零，然后相乘概率。
得到c的话直接枚举a，然后得到b=c-a；
解题代码

[code]#include#define int long long#define lll __uint128_t#define PII pair#define endl '\n'using namespace std;#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印#define YN(ans) printf("%s\n", (ans)?"YES":"NO");#define REP(i, e) for (int i = 0; i < (e); ++i)#define REP1(i, s, e) for (int i = (s); i > t; while (t--)#define TESTconst int N=2e5+10,M=1e3+10,mod=1e9+7,MOD=998244353;int a[N],b[N],c[N],pre[N];//相当于0的话就中间那个不亮，1110111，以此类推。int segMask[10] = {        119, 36, 93, 109, 46, 107, 123, 37, 127, 111};int ksm(int p,int q,int mod){    int result=1;    p%=mod;    while(q){        if(q&1)result=result*p%mod;        p=p*p%mod;        q>>=1;    }    return result%mod;}signed main(){        std::ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    int inv100=ksm(100,MOD-2,MOD);    int x[7];    int C;    cin>>C;    //先得到这个，x = p_i / 100 (mod MOD)    for(int i=0;i>p;        x=(1ll*p%mod*inv100)%mod;    }    vectorx1(10,1);//统计出0-9这些数在一个的时候的概率。    for(int i=0;ij&1){                x1*=x[j];            }else{                x1*=(1+MOD-x[j]);            }            x1%=MOD;        }    }    //开始拼接，四位数的-》x的概率    auto cacl=[&](int x)->int{        if(x==0)return x1[0]%MOD*x1[0]%MOD*x1[0]%MOD*x1[0]%MOD;        int ans=1;        int len=0;        while(x>0){            ans*=x1[x%10]%MOD;//取最后一位            ans%=MOD;            x/=10;            len++;        }        for(int i=0;in;    int x=0,y=0,mi=1e8;    vectora(n);    for(int i=0;i>a;    }    for(int i=0;i>m;        mi=min(mi,m);    }    for(int i=0;i=mi){            x++;        }else{            y++;        }    }    int ans=0;    for(int i=1;i>k;    vectorv(n+1);    v[n]=k;    for(int i=1;i>v;    }    int ma=-2e7;    for(int i=0;is2;    int l= stoll(s1);    int r=stoll(s2);    int n=s2.size();    string t="1";    //先让其变成10000000，    for(int i=0;i

前排留名，哈哈哈

分享、互助 让互联网精神温暖你我

这个好，看起来很实用

收藏一下   不知道什么时候能用到

谢谢分享，试用一下

前排留名，哈哈哈