HDU 4972 Bisharp and Charizard 想法题

Bisharp and Charizard

Time Limit: 1 Sec  Memory Limit: 256 MB

 

Description

Dragon is watching NBA. He loves James and Miami Heat. 

Here's an introduction of basketball game:http://en.wikipedia.org/wiki/Basketball. However the game in Dragon's version is much easier: 

"There's two teams fight for the winner. The only way to gain scores is to throw the basketball into the basket. Each time after throwing into the basket, the score gained by the team is 1, 2 or 3. However due to the uncertain factors in the game, it’s hard to predict which team will get the next goal". 

Dragon is a crazy fan of Miami Heat so that after each throw, he will write down the difference between two team's score regardless of which team keeping ahead. For example, if Heat's score is 15 and the opposite team's score is 20, Dragon will write down 5. On the contrary, if Heat has 20 points and the opposite team has 15 points, Dragon will still write down 5. 

Several days after the game, Dragon finds out the paper with his record, but he forgets the result of the game. It's also fun to look though the differences without knowing who lead the game, for there are so many uncertain! Dragon loves uncertain, and he wants to know how many results could the game has gone? 

input

The first line of input contains only one integer T, the number of test cases. Following T blocks, each block describe one test case. 

For each test case, the first line contains only one integer N(N<=100000), which means the number of records on the paper. Then there comes a line with N integers (a ₁, a ₂, a ₃, ... , a _n). a _i means the number of i-th record.

 

ouput

Each output should occupy one line. Each line should start with "Case #i: ", with i implying the case number. Then for each case just puts an integer, implying the number of result could the game has gone.

 

 

Sample Input

2 2 2 3 4 1 3 5 7

Sample Output

Case #1: 2 Case #2: 2

题意  

：篮球比赛有1、2、3分球  现给出两队的分差序列（5：3 分差2  3：5分差也是2）  问有多少种可能的比分

题解：

比较简单的想法题  可以类一张表“从分差x到分差y一共有几种情况”  很容易发现只有1->2和2->1的时候会多一种情况  其他均是一种  所以只需要统计这种特殊分差即可  注意一下最后结果要不要乘2  如果最后分差是0就不用因为x:x只有一种  但是最后分差不是0就要乘  因为x:y和y:x算两种  还有本题有坑！！ 那个SB记分员会把分数记错  所以一旦记错种类数就为0了

代码：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
#include <stack>
typedef long long ll;
#define inf 0x7fffffff
using namespace std;
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
//**************************************************************************************


int main()
{

    int T=read();
    int oo=1;
    while(T--)
    {

        int n,a[100005];
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        a[0]=0;
        int flag=0;
        int ans=1;
        for(int i=1;i<=n;i++)
            {
                if(abs(a[i]-a[i-1])>3||(a[i]!=1&&a[i]==a[i-1]))
                {
                    flag=1;
                    break;
                }
                if((a[i]==2&&a[i-1]==1)||(a[i]==1&&a[i-1]==2))ans++;
            }
            printf("Case #%d: ",oo++);
            if(flag){
                printf("0
");
            }
            else {
                if(a[n]==0){
                    printf("%d
",ans);
                }
                else printf("%d
",ans*2);
            }
    }
    return 0;
}