首页 > ACM题库 > HDU-杭电 > HDU 4066-Random Sequence[解题报告]HOJ
2015
04-16

HDU 4066-Random Sequence[解题报告]HOJ

Random Sequence

问题描述 :

There is a random sequence L whose element are all random numbers either -1 or 1 with the same possibility. Now we define MAVS, the abbreviate of Maximum Absolute Value Subsequence, to be any (if more than one) subsequences of L whose absolute value is maximum among all subsequences. Given the length of L, your task is to find the expectation of the absolute value of MAVS.

输入:

There is only one input file. The first line is the number of test cases T. T positive integers follow, each of which contains one positive number not greater than 1500 denoted the length of L.

输出:

There is only one input file. The first line is the number of test cases T. T positive integers follow, each of which contains one positive number not greater than 1500 denoted the length of L.

样例输入:

3
1
5
10

样例输出:

Case 1: 1.000000
Case 2: 2.750000
Case 3: 4.167969

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define swap(t,x,y) (t=x,x=y,y=t)
#define distance(x1,x2,y1,y2,z1,z2) (sqrt(pow(x2-x1,2)+pow(y2-y1,2)+pow(z2-z1,2)))
#define myabs(x) (x<0?-x:x)
#define sgn(x) (x<0?-1:(x>0?1:0))
#define clr(list) memset(list,0,sizeof(list))

using namespace std;

double ans[1540];

int main()
{
    double x=1.0;
    ans[1]=1.0;
    for (int i=2;i<=1500;i++)
    {
        if (i%2==0)
            x=x*(i-1.0)/(i*1.0);
        ans[i]=ans[i-1]+x;
    }
    int t;
    int cas=0;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        printf("Case %d: %.6lf\n",++cas,ans[n]);
    }
	return 0;
}

  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;