首页 > ACM题库 > HDU-杭电 > HDU 2949-Box Betting[解题报告]HOJ
2014
02-24

HDU 2949-Box Betting[解题报告]HOJ

Box Betting

问题描述 :

Theres a new delivery boy at your company, supposed to drive around delivering a specific number of items to difierent locations. He needs to deliver at least X of an item, while the truck can at most take Y of the item.

If there are more, the truck is will to break down due to the weight. If there are less, that means he hasn’t fulfilled the assignment. At the loading station, there’s a row of boxes he can bring along.

Each box contains a specified number of items. This driver isn’t the sharpest snail on the rock, however. Since he’s also too shy to ask for help, he’s decided to just choose one entirely random starting point in the row of boxes. Then he chooses a random end point among the boxes from the starting point to the end, inclusive.

All the boxes between those points (inclusive) are loaded onto the truck. You and the other employees have started betting on whether or not the truck breaks
down, he brings to few items along or if he should happen to be lucky enough to fulfil the assignment without any problems. This gets you wondering. What is the actual probability for each of these scenarios to occur? Assume for the sake of this problem that the driver will always be able to fit all the boxes into the truck (after all, he had to have SOME skill, seeing as he was hired).

输入:

The input will start with a line containing a single number T, the number of test cases.

Each test case consists of three lines. The first one contains a single number N, the number of boxes. The second line contains a sequence of N characters (A-Z), B1B2…BN (no whitespace), representing the amount of items in each of the boxes in the same order as they’re located on the loading dock. An A represents an empty box, B a box with 1 item, and so on until Z, which represents a box with 25 items in it. The third line contains the two numbers L and U. L is the number of items the driver is supposed to deliver, while U is the maximum number of items the truck can take before it’ll break down.

输出:

The input will start with a line containing a single number T, the number of test cases.

Each test case consists of three lines. The first one contains a single number N, the number of boxes. The second line contains a sequence of N characters (A-Z), B1B2…BN (no whitespace), representing the amount of items in each of the boxes in the same order as they’re located on the loading dock. An A represents an empty box, B a box with 1 item, and so on until Z, which represents a box with 25 items in it. The third line contains the two numbers L and U. L is the number of items the driver is supposed to deliver, while U is the maximum number of items the truck can take before it’ll break down.

样例输入:

2
4
KCHA
2 9
3
BCD
4 5

样例输出:

0.5 0.25 0.25
0.16666667 0.72222222 0.11111111

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#define PB push_back
#define MP make_pair
#define clr(a,b)    (memset(a,b,sizeof(a)))
#define rep(i,a)    for(int i=0; i<(int)a.size(); i++)

const int INF = 0x3f3f3f3f;
const double eps = 1E-8;

int T;
int n,l,r;
char s[200010];
int num[200010];
LL tot = 1ll*n*(n+1)/2;

double fun1(int lim)
{
    double ret = 0;
    int ed = 1,sum = num[1];
    for(int st=1; st<=n; st++)
    {
        while(sum <= lim && ed < n)
        {
            ed ++;
            sum += num[ed];
        }
        if(sum > lim)	ret += 1.0*(n - ed + 1)/(1ll*n*(n-st+1)) ;
        sum -= num[st];
    }
    return ret;
}

double fun2(int lim)
{
    double ret = 0;
    int ed = 1,sum = num[1];
    for(int st=1; st<=n; st++)
    {
        while(sum < lim && ed < n)
        {
            ed ++;
            sum += num[ed];
        }
        if(sum >= lim)
        {
        	if(ed-1 >= st)	ret += 1.0*(ed - st)/(1ll*n*(n-st+1));
        }
        else
        {
        	ret += 1.0*(ed - st + 1)/(1ll*n*(n-st+1));
        }
        sum -= num[st];
    }
    return ret;
}

int main()
{
	//freopen("D:\\in.txt","r",stdin);

    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        scanf("%s",s+1);
        scanf("%d%d",&l,&r);
        num[0] = 0;
        for(int i=1; i<=n; i++)	num[i] = s[i] - 'A';


        double a,b,c;
        c = fun1(r);
        a = fun2(l);
        b = 1 - a - c;
        printf("%lf %lf %lf\n",b,a,c);
    }
    return 0;
}

  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));
    }
    }