清北学堂 18 金秋模拟题 1

总结

  • 最后 5 分钟,检查文件 IO,数组大小,关闭多余的调试信息。

题面

A.game

概率 DP, 表示打 场赢 场的概率。最后统计期望即可

#include<cstdio>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
const int N=1004;// 惨死
int n;
double f[N][N],ans=0;
double p[N][N];
int main(){//freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    scanf("%d",&n);
    FOR(i,1,n)FOR(j,0,i-1)scanf("%lf",&p[i][j]);
    f[0][0]=1;
    FOR(i,1,n){f[i][0]=f[i-1][0]*(1-p[i][0]);
    FOR(j,1,i-1)f[i][j]=f[i-1][j]*(1-p[i][j])+f[i-1][j-1]*p[i][j-1];    
    f[i][i]=f[i-1][i-1]*p[i][i-1];
    }
    FOR(i,0,n)ans+=f[n][i]*i;// 统计期望
    printf("%.2lf",ans);
    return 0;
}

B.cake

折半搜索,然后 凑 x 即可。

.

#include<cstdio>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
const int N=42,X=10004;
int n,x,v,ans;
int a[N],p1[1<<20],p2[1<<20],l1,l2;
int main(){//freopen("cake.in","r",stdin);
    //freopen("cake.out","w",stdout);
    scanf("%d%d",&n,&x);
    FOR(i,1,n)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int d1=n/2,mxi=1<<d1;
    FOR(i,0,mxi-1){// 对前后两半做二进制枚举,把所有可能产生的值记录
        long long sum=0;
        FOR(j,1,d1)if((i>>(j-1))&1)sum+=a[j];
        if(sum<=x)p1[++l1]=sum;
    }
    mxi=1<<(n-d1);
    FOR(i,0,mxi-1){
        long long sum=0;
        FOR(j,1,n-d1)if((i>>(j-1))&1)sum+=a[j+d1];
        if(sum<=x)p2[++l2]=sum;
    }
    sort(p1+1,p1+l1+1);
    sort(p2+1,p2+l2+1);
    int j=l2;
    FOR(i,1,l1){// 用 p1,p2 凑 x
        while(p1[i]+p2[j]>x)j--;
        ans=max(ans,p1[i]+p2[j]);
    }
    printf("%d",x-ans);
    return 0;
}

C.


 上一篇
[NOIP2005] 过河 [NOIP2005] 过河
考虑 因此对于两相邻点之间的距离可以对 取模离散化 然后正常 DP 即可 f[i]=\
2018.11.07
下一篇 
搬瓦工快照提取文件 搬瓦工快照提取文件
搬瓦工的快照文件是一个 tar.gz 的压缩包,如何提取里面的文件? 方法是将里面 raw 格式镜像(disk 文件)通过 kpartx 挂载在 linux 文件夹下 建议先开启 root 权限: sudo su 解压(必须用 linux
2018.11.02
  目录