首页 > ACM题库 > HDU-杭电 > hdu 4420-alice and bob-模拟-[解题报告]hoj
2015
07-16

hdu 4420-alice and bob-模拟-[解题报告]hoj

Alice and Bob

问题描述 :

These days, Alice came up with a new game. In this game, there are some balls placed in a line which are numbered from L to R from left to right. It is known that N of the balls are white, while others are black. Alice will select aCount consecutive balls, after that, Bob will remove bCount balls from the balls that Alice has selected. Bob could remove those bCount balls one by one, for each ball he removes, he can choose whether to select the left most one or right most one.
The goal of Alice is to maximize the number of white balls after Bob’s operation, and Bob’s goal is to minimize this number.
So, what is the maximum number of white balls after Bob’s operation?

输入:

There are multiple test cases, for each case:
The first line is an integer N. (1 <= N <= 100,000)
The second line contains two integers L, R. (0 <= L <= R <= 263 – 1)
The third line contains two integers aCount, bCount.
The fourth line contains N integers p[0], p[1], …, p[N - 1], denoting the positions of the white balls.
It is guaranteed that p[i - 1] < p[i] (1 <= i <= N – 1), L <= p[0], p[N - 1] <= R, 0 <= aCount <= R – L + 1, 0<=bCount <= aCount.

输出:

There are multiple test cases, for each case:
The first line is an integer N. (1 <= N <= 100,000)
The second line contains two integers L, R. (0 <= L <= R <= 263 – 1)
The third line contains two integers aCount, bCount.
The fourth line contains N integers p[0], p[1], …, p[N - 1], denoting the positions of the white balls.
It is guaranteed that p[i - 1] < p[i] (1 <= i <= N – 1), L <= p[0], p[N - 1] <= R, 0 <= aCount <= R – L + 1, 0<=bCount <= aCount.

样例输入:

2
5 9
3 1
5 8
3
6 10
5 0
6 8 10

样例输出:

1
3


对于一个英语四级还没过的渣渣来说,这道题我看了好久都没看懂。。。。
下面贴出别人的题意。。。

两个人打台球,初始状态为n个编号不同的球和一个母球(编号为0),每个球的分数即它的编号,每次操作时,当前的目标球为台面上球的最小值,操作犯规的话会给对手加上若干分,犯规的情况有:
1 母球没有打到任何球,对手+目标球的分数

2 母球没有落袋,但是母球第一次撞击没有撞到目标球,或者是第一次撞击同时撞击了1个以上的球,对手+第一次同时撞击到的球中编号最大的分数

3 母球落袋并且撞击到了至少一个球,对手+第一次同时撞击到的球中编号最大的分数

在没有犯规的情况下,若目标球落袋,则我方的分数加上本轮落袋的球的分数和,并且下一轮依然是我方操作。如果我方犯规,或者是有球落袋但是目标球没有落袋,则对方再加上落袋的球的分数和。所有操作结束后,求A:B的分数。

很考验细心的一道模拟,注意到,我方得分的情况只有首先只撞到了一个球,并且这个球是目标球,并且母球没有落袋,目标球落袋,这种情况下我方加分,并继续行动,否则一定是对方加分并且换手,其中对方加分的情况中有一点要考虑到,如果我方犯规了,对方会加上罚分,并且如果这次操作有球落袋了,对手会再加上落袋求的分数和。考虑到这些,写的时候细心点这题也就没什么大问题了…

翻译出处:http://blog.csdn.net/night_raven/article/details/20320575

翻译这么详细,真是一位大神了。。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int s[10000],hash[200000];
int hit[10000],in[10000];
int a[2],i,j,pot,l_hit,l_in,n,m,flag,flag_pot;

void set()
{
    for(int k=0; k<l_in; k++)
        hash[in[k]]=1;
    while(hash[s[pot]])
        pot++;
    flag=1-flag;
}

void solve()
{
    int sum=0;
    for(int k=0; k<l_in; k++)
        sum+=in[k];
    if(l_hit==0) //没击中球
    {
        a[1-flag]+=s[pot];
    }
    else if(in[0]==0&&l_in!=0) //先判断是否有球入袋
    {
        a[1-flag]+=hit[l_hit-1];
    }
    else if(l_hit>1||(l_hit==1&&hit[0]!=s[pot])) //过多或不是目标球
    {
        a[1-flag]+=hit[l_hit-1];
    }
    else //无犯规
    {
        if(flag_pot) //目标球进了
        {
            a[flag]+=sum;
            flag=1-flag;
            return;
        }
    }
    if(in==0) return;
    a[1-flag]+=sum;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        a[1] = a[0] = 0;
        for(i = 1; i<=n; i++)
            scanf("%d",&s[i]);
        sort(s+1,s+n+1);
        memset(hash,0,sizeof(hash));
        flag = 0;
        pot = 1;
        for(i = 0; i<m; i++)
        {
            flag_pot = 0;
            scanf("%d",&l_hit);
            for(j = 0; j<l_hit; j++)
                scanf("%d",&hit[j]);
            scanf("%d",&l_in);
            for(j = 0; j<l_in; j++)
            {
                scanf("%d",&in[j]);
                if(in[j] == s[pot])
                flag_pot = 1;
            }
            sort(hit,hit+l_hit);
            sort(in,in+l_in);
            solve();
            set();
        }
        printf("%d : %d\n",a[0],a[1]);
    }

    return 0;
}

 

参考:http://blog.csdn.net/libin56842/article/details/20486039