论如何用两枚硬币代替骰子

感谢伟大的Cai提供的思路!

首先,我们先制造一枚正反面概率均为$\frac{1}{2}$的硬币,然后构造一棵比较大的完全二叉树,假设这棵二叉树有k个叶子节点,那么每个节点被选到的概率就是$\frac{1}{k}$

然后将这k个叶子分为n组,其中,前n-1组的叶子数相等且不为0,最后一组的叶子数小于等于前n-1组每组的叶子数,可以为0。假设前n-1组每组有$k_0$个叶子,最后一组有$k_1$个叶子。

如果$k_0=k_1$,就可以直接按照这种分组输出答案了。

否则前n-1组每组的概率为$\frac{k_0}{k}$,这个概率是大于$\frac{1}{n}$的,那么要从这个概率里”分“一点给最后一组。所以从每组中取一片叶子,给它添加两个儿子,抛第二枚硬币,让新的两个叶子,一个分给当前组,一个分给第n组,使得当前组的概率减少一点,恰好变成$\frac{1}{n}$。

可知第二枚硬币的正面概率应为$(\frac{1}{n}-\frac{k_0-1}{k})*k$

显然此时最后一组的概率也为$\frac{1}{n}$

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int LIM=100000;
int n,tot,SZ,p1,q1;
int s[LIM+5][2],num[LIM+5],yb[LIM+5];
void build(int nowjs) {//建二叉树
    for(RI i=1;i<nowjs;++i)
        ++SZ,s[i][0]=i<<1,s[i][1]=(i<<1)|1,yb[i]=0;
}
void print() {
    puts("YES");
    printf("1 2 %d %d\n",p1,q1);
    printf("%d\n",SZ);
    for(RI i=1;i<=SZ;++i)
        if(num[i]) printf("E %d\n",num[i]-1);
        else printf("C %d %d %d\n",yb[i],s[i][0]-1,s[i][1]-1);
    exit(0);
}
int gcd(int x,int y) {
    int r=x%y;
    while(r) x=y,y=r,r=x%y;
    return y;
}
int main()
{
    scanf("%d",&n);
    for(RI nowjs=1;nowjs*2<=LIM;nowjs<<=1) {
        if(nowjs%n==0) {
            build(nowjs),p1=1,q1=2;
            for(RI j=1;j<=n;++j) ++SZ,num[SZ]=j;
            print();
        }
        else if(nowjs/(n-1)>0) {
            int k0=nowjs/(n-1),k1=nowjs-k0*(n-1);
            if(k1>=k0) continue;
            build(nowjs);
            p1=nowjs-(k0-1)*n,q1=n;int d=gcd(p1,q1);
            p1/=d,q1/=d;
            int kSZ=nowjs*2-1;
            for(RI j=1;j<=nowjs;++j) {
                int knum=(j-1)/k0+1,x=++SZ;
                if((j-1)%k0==0) {
                    s[x][0]=++kSZ,s[x][1]=++kSZ,yb[x]=1;
                    num[s[x][0]]=knum,num[s[x][1]]=n;
                }
                else num[x]=knum;
            }
            SZ=kSZ;print();
        }
    }
    puts("NO");
    return 0;
}

如何检查你的代码

因为太菜而WA了一次的litble,又因为太菜不会写spj,所以让原来那个代码把n也输出来了,然后不输出”YES”或”NO”,写了一个程序检验是否正确:

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int N=100005;
int n,SZ;
int vis[N];
struct fs{int a,b;}u[N],ans[N],g0,g1;
int gcd(int x,int y) {
    int r=x%y;
    while(r) x=y,y=r,r=x%y;
    return y;
}
fs operator - (fs x1,fs x2) {
    fs re;int d=1;
    re.b=x1.b*x2.b,re.a=x1.a*x2.b-x2.a*x1.b;
    d=gcd(re.a,re.b),re.a/=d,re.b/=d;return re;
}
fs operator + (fs x1,fs x2) {
    fs re;int d;
    re.b=x1.b*x2.b,re.a=x1.a*x2.b+x2.a*x1.b;
    d=gcd(re.a,re.b),re.a/=d,re.b/=d;return re;
}
fs operator * (fs x1,fs x2) {
    fs re;int d;
    re.b=x1.b*x2.b,re.a=x1.a*x2.a;
    d=gcd(re.a,re.b),re.a/=d,re.b/=d;return re;
}
int main()
{
    freopen("lx.out","r",stdin);
    char ch[10];int p,x,y;
    fs e=(fs){1,1};
    scanf("%d",&n);
    if(n==-1) {puts("WA");return 0;}
    scanf("%d%d%d%d",&g0.a,&g0.b,&g1.a,&g1.b);
    scanf("%d",&SZ);
    u[1].a=u[1].b=1;
    for(RI i=1;i<=n;++i) ans[i].b=1;
    for(RI i=1;i<=SZ;++i) {
        scanf("%s",ch);
        if(ch[0]=='E') {
            scanf("%d",&x);
            if(x>=n||x<0) {puts("WA");return 0;}
            ans[x+1]=ans[x+1]+u[i];
        }
        else {
            scanf("%d%d%d",&p,&x,&y);
            ++x,++y;
            if(x>SZ||y>SZ||x<=i||y<=i) {puts("WA");return 0;}
            if(p==0) u[x]=u[i]*g0,u[y]=u[i]*(e-g0);
            else u[x]=u[i]*g1,u[y]=u[i]*(e-g1);
        }
    }
    for(RI i=1;i<=n;++i) if(ans[i].a!=1||ans[i].b!=n) {puts("WA");return 0;}
    puts("AC");
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *