26牛客寒假算法训练营1题解
26牛客寒假算法训练营1题解学习总结
学习到了状态压缩，我们直接转换为二进制，再直接把二进制转换为数字就可以了。
用的时候这样用就可以了 x>>j.
对于多种选择方案用状态压缩有时候会解决很多问题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
01110111
也就是119，其他的以此类推。
然后我们可以得到每一个数的概率，因为每一个都要亮的概率，所以我们先把每一个数的概率算出来，用
x>>j&1来得到这个数到底是1还是0最后直接把一个四位数的表示方法写出来，我们直接用取最后一位一直取，如果不够就直接前导零，然后相乘概率。
得到c的话直接枚举a，然后得到b=c-a；
解题代码
#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,b,c,pre;//相当于0的话就中间那个不亮，1110111，以此类推。int segMask = { 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; 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; }else{ x1*=(1+MOD-x); } x1%=MOD; } } //开始拼接，四位数的-》x的概率 auto cacl=[&](int x)->int{ if(x==0)return x1%MOD*x1%MOD*x1%MOD*x1%MOD; int ans=1; int len=0; while(x>0){ ans*=x1%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=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 前排留名，哈哈哈 分享、互助 让互联网精神温暖你我 这个好，看起来很实用 收藏一下 不知道什么时候能用到 谢谢分享，试用一下 前排留名，哈哈哈 前排留名，哈哈哈 谢谢分享，试用一下 感谢分享，下载保存了，貌似很强大 这个有用。 不错，里面软件多更新就更好了
页:
[1]