2287 火车站

时间限制: 1 s

空间限制: 32000 KB

题目等级 : 钻石 Diamond

题目描述 Description

火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的人数有一定的规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有N个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。试问从x站开出时车上的人数是多少？若无解输出“No answer.”（所有数据均在longint范围内）

输入描述 Input Description

a，n，m和x

输出描述 Output Description

x站开出时车上的人数

样例输入 Sample Input

1　6　7　3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

无

分类标签 Tags

递推数论

/*

好几个月之前做的一道题了，枚举+递推，超级恶心

*/

#include<iostream>

#include<cstdio>

using namespace std;

int a,n,m,x;

bool b;

struct node{int up,tot;}f[];

int main()

{

    cin>>a>>n>>m>>x;

    f[].up=a;f[].tot=a;

    f[].tot=a;f[n].tot=m;

    f[n].up=;

    for(int k=;k<=m;k++)

    {

        f[].up=k;

        for(int i=;i<n;i++)

        {

            f[i].up=f[i-].up+f[i-].up;

            f[i].tot=f[i-].tot+f[i].up-f[i-].up;

        }

        if(f[n-].tot==m)

        {

            printf("%d",f[x].tot);

            b=true;

            return ;

        }

    }

    if(!b)printf("No answer.\n");

    return ;

}

//第一次做的时候的代码：

#include<iostream>

#include<cstdio>

using namespace std;

int a,n,m,x;

bool b;

struct car

{

    int up;

    int down;

    int tot;

}f[];

int main()

{

    cin>>a>>n>>m>>x;

    f[].up=a;

    f[].tot=a;

    f[].tot=a;

    f[n].tot=m;

    f[n].up=;

    for(int k=;k<=m;k++)

    {

        f[].up=k;

        for(int i=;i<n;i++)

        {

            f[i].up=f[i-].up+f[i-].up;//A

            //f[i].down=f[i-1].up;B

            //f[i].tot=f[i-1].tot+f[i].up-f[i].down;C

            f[i].tot=f[i-].tot+f[i].up-f[i-].up;//D<--C(B)

        }

        if(f[n-].tot==m)

        {

            cout<<f[x].tot;

            b=true;

            return ;

        }

    }

    if(!b)

        cout<<"No answer.";

    return ;

}

巴特西

codevs 2287 火车站

2287 火车站

分类标签 Tags

最新文章

热门文章