首页 > ACM题库 > HDU-杭电 > HDU 2995-Another Panda’s Birthday Present-分治-[解题报告]HOJ
2014
02-24

HDU 2995-Another Panda’s Birthday Present-分治-[解题报告]HOJ

Another Panda’s Birthday Present

问题描述 :

On Panda’s Birthday party, he received a strange present from Jason. The present is a black box with 9 dices in it which is used to play a game. The dice in the box is unusual. Instead of the digits, only red or blue is painted on each side of the dice. Before the first round of the game, the box can repaint every side of every dice red or blue with equal probability. Then for each round of the game, the box will roll the 9 dices and tell the player the number of red side facing up, which is the point the player get. Now, Panda has play it for k(0<=k<=3) rounds and he tell you the point he has got for each round. Can you tell him the expected point he can get for next round.

输入:

The first line of the input is number of test case. Each test case contains k+1 integers, k which is the number of rounds and a1…ak, which are the points Panda has got for the first k rounds.(0≤ai≤9,0<=k<=3)

输出:

The first line of the input is number of test case. Each test case contains k+1 integers, k which is the number of rounds and a1…ak, which are the points Panda has got for the first k rounds.(0≤ai≤9,0<=k<=3)

样例输入:

2
2 2 2 
2 4 4

样例输出:

2.000
2.571

题目:http://acm.hit.edu.cn/hoj/problem/view?id=2995

本题主要是理解题意和理解二分法的思路。

具体还需要学会求简单的定积分。

关于x ≥ 1, y ≥ 1, x * y ≤ C。

 代码:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
using namespace std;

//计算x ≥ 1, y ≥ 1, x * y ≤ c时S内有多少个整数点
int count(int c)
{
    int ans = 0;
    for(int i=1;i<=c;i++)
    {
        ans += c/i;
    }
    return ans;
}
//二分法求lower_bound
int calc(int n)
{
    int low = 1;
    int high = n;
    int pos = 1;
    while(low < high)
    {
        int mid = (low + high)/2;
        if(count(mid)<n)
        {
            low = mid + 1;
            pos = low;
        }
        else
        {
            high = mid;
            pos = mid;
        }
    }
    return pos;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int t;
    int n;
    int c;
    scanf(" %d",&t);
    for(int i=0;i<t;i++)
    {
        scanf(" %d",&n);
        if(n == 0)
        {
            printf("0.0000\n");
            continue;
        }

        c = calc(n);
        printf("%.4lf\n",c*log(c) - (c - 1));
    }

    return 0;
}

解题参考:http://blog.csdn.net/niuox/article/details/8635453


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!