2016 Hdu 多校赛第七场

Hdu 5810 Balls and Boxes

链接

题意

有n个球，m个盒子，每个球扔进每个盒子是等概率的，
$V=\frac{\sum_{i=1}^{m}(X_{i}-\bar X)^{2}}{m}$
求V的期望值，其中Xi是第i个盒子的球数

分析

数学公式推导，answer=n*(m-1)/(m*m)

参考代码

#include<stdio.h>
typedef long long LL;
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    LL n,m;
    while(scanf("%lld%lld",&n,&m)!=EOF){
        if(n==0&&m==0)
            break;
        LL x=n*(m-1);
        LL y=m*m;
        LL g=gcd(x,y);
        printf("%lld/%lld\n",x/g,y/g);
    }
    return 0;
}

Hdu Elegant Construction

链接

Elegant Construction

题意

有n个城镇，给定每个城镇能到达的城镇数(可直接或间接到达)，
问是否能建一些没有环路的单向路，满足上述条件

分析

将顶点按能到达的点数从小到大排序，排好序之后每个点只能往前面的点连边.
因而如果存在一个排在第i位的点，要求到达的点数大于i-1，则不可行；
否则就可以按照上述方法构造出图. 复杂度O(N^2).

参考代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=1010;
struct stu{
    int id;
    int val;
}a[N];
bool cmp(stu x,stu y)
{
    return x.val>y.val;
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        printf("Case #%d: ",k);
        int n,sum=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i].val);
            a[i].id=i;
            sum+=a[i].val;
        }
        sort(a+1,a+1+n,cmp);
        bool flag=true;
        for(int i=n;i>=1;i--){
            if(a[i].val>n-i){
                flag=false;
                break;
            }
        }
        if(!flag){
            printf("No\n");
            continue;
        }
        printf("Yes\n%d\n",sum);
        for(int i=n;i>=1;i--){
            for(int j=n;j>n-a[i].val;j--)
                printf("%d %d\n",a[i].id,a[j].id);
        }
    }
    return 0;
}

Hdu 5816 Hearthstone

链接

Hearthstone

题意

有n张奥术智慧(抽两张牌)，m张火球术(造成x点伤害)，
给定每张火球术会造成的伤害数以及对手的HP数，
求这回合杀死对手的概率是多少。

分析

设dp[i][j][k]表示有i张火球术，用j张火球打出伤害为k的方案数，可以先DP求出。
转移方程为：dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i]]
其中x[i]是第i张火球的伤害，相当于恰好装满的01背包。可以优化为二维空间。
设s[i]表示有m张火球术，用i张火球打出伤害大于等于P(敌方血量)的总方案数。
则用i张火球打出杀死对手的概率pi=s[i]/com[m][i]（com是组合数)
再用位运算求出枚举牌库的状态(m+n位，其中有m个1)，状态总数为cnt,
对于每中状态可计算出能抽到的火球牌数i，计算概率总和，answer=sum(pi)/cnt

参考代码

#include<stdio.h>
#include<string.h>
typedef long long LL;
const int N=22;
const int M=20010;
int dp[N][M],s[N];
int x[N],com[N][N];
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
LL lcm(LL a,LL b)
{
    return a/gcd(a,b)*b;
}
void init()
{
    com[0][0]=1;
    for(int i=1;i<N;i++){
        com[i][0]=1;
        for(int j=1;j<=i;j++){
            com[i][j]=com[i-1][j]+com[i-1][j-1];
        }
    }
}
void solve(int m,int sum,int p)
{
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=m;i++){
        for(int j=m;j>=0;j--){
            for(int k=sum;k>=0;k--){
                dp[j][k]=dp[j][k];
                if(j>=1&&k>=x[i])
                    dp[j][k]+=dp[j-1][k-x[i]];
            }
        }
    }
    memset(s,0,sizeof(s));
    for(int i=0;i<=m;i++){
        for(int j=p;j<=sum;j++){
            s[i]+=dp[i][j];
        }
    }
}
int main()
{
    int T;
    init();
    scanf("%d",&T);
    while(T--){
        int p,n,m;
        scanf("%d%d%d",&p,&n,&m);
        int sum=0;
        for(int i=1;i<=m;i++){
            scanf("%d",&x[i]);
            sum+=x[i];
        }
        solve(m,sum,p);
        int comb=(1<<m)-1;
        LL up=0,down=1,cnt=0;
        while(comb<(1<<(n+m))){
            cnt++;
            int fire=0,num=1,now=comb;
            while(now&&num){
                num--;
                if(now&1)
                    fire++;
                else
                    num+=2;
                now>>=1;
            }
            LL lm=lcm(down,com[m][fire]);
            up=up*lm/down+s[fire]*lm/com[m][fire];
            down=lm;
            int x=comb&-comb,y=comb+x;
            comb=((comb&~y)/x>>1)|y;
        }
        down*=cnt;
        LL g=gcd(up,down);
        printf("%lld/%lld\n",up/g,down/g);
    }
    return 0;
}

Hdu 5818 Joint Stacks

链接

Joint Stacks

题意

有两个栈A,B(初始时为空)，有三种操作：
push(插入一个数)、pop(删除栈顶元素)、merge.
其中merge是按照A,B中元素进栈的相对顺序来重排的.
pop操作时，输出删除的元素值。

分析

比较简单巧妙的一个做法是引入一个新的栈C，每次合并的时候就把A和B合并到C上，然后把A和B都清空. push还是按正常做，pop注意当遇到要pop的栈为空时，因为题目保证不会对空栈进行pop操作，所以这时应直接改为对C栈进行pop操作. 这样做因为保证每个元素最多只在一次合并中被处理到，pop和push操作当然也是每个元素只做一次，所以总复杂度是O(N)的.

参考代码

#include<stdio.h>
const int N=100010;
struct stu{
    int val;
    int id;
}st[3][N];
int main()
{
    int n,cas=1;
    while(scanf("%d",&n)&&n){
        printf("Case #%d:\n",cas++);
        int cnt=0,tpa=0,tpb=0,tpc=0;
        while(n--){
            char ope[8],s[5];
            scanf("%s%s",ope,s);
            if(ope[1]=='u'){
                int x;
                scanf("%d",&x);
                if(s[0]=='A'){
                    st[0][tpa].val=x;
                    st[0][tpa++].id=cnt++;
                }
                else if(s[0]=='B'){
                    st[1][tpb].val=x;
                    st[1][tpb++].id=cnt++;
                }
            }
            else if(ope[1]=='o'){
                if(s[0]=='A'){
                    if(tpa==0)
                        printf("%d\n",st[2][--tpc].val);
                    else
                        printf("%d\n",st[0][--tpa].val);
                }
                else if(s[0]=='B'){
                    if(tpb==0)
                        printf("%d\n",st[2][--tpc].val);
                    else
                        printf("%d\n",st[1][--tpb].val);
                }
            }
            else if(ope[1]=='e'){
                char t[5];
                scanf("%s",t);
                int i=0,j=0;
                while(i<tpa&&j<tpb){
                    if(st[0][i].id<st[1][j].id)
                        st[2][tpc]=st[0][i++];
                    else
                        st[2][tpc]=st[1][j++];
                    tpc++;
                }
                while(i<tpa)
                    st[2][tpc++]=st[0][i++];
                while(j<tpb)
                    st[2][tpc++]=st[1][j++];
                tpa=tpb=0;
            }
        }
    }
    return 0;
}