P1057 传球游戏 题解

难度：⭐⭐⭐
知识点：传球法
题目链接

序言：

我看题解中除了各种对于我这个蒟蒻来说稀奇古怪高深莫测的方法之外就只有用二维数组的了，所以我决定来发一篇用初学者们也都熟悉的一维数组也能AC的方法。

1.入手程序

一拿到题，哇！完全没思路哇( ⊙o⊙ )

所以，画个表吧！

由于我们知道小蛮一定在第一位，所以我们可以用一个数组来模拟这个圈：

好了，定义好了数组，就可以开始准备模拟了。我们先画一个表：（样例一）
现在我们看到，第三次传球后小蛮有两种可能性手上有球，分别是1->2->3->1和1->3->2->1，因此我们知道了每次把有球的人的旁边两个人加上这个人的可能次数，就可以得到正确结果。（这其实就是小学奥数传球法）

2.编程思路

上面的一句话有一些难懂，这里用代码解释一下：

    a[j+1]+=a[j];
    a[j-1]+=a[j];

所以，我们的任务就是模拟这个过程。

注意：

1.不应该用数值来判断是否到边界（0或n），而应该用下标来判断

2.a[j]不能直接为零，而是减去上一次传球的可能次数（因为可能不仅他要传给别人，别人也要传给他）

对应解决方案：

1.改为j-1和j+1

2.使用一个b数组来存储上一次的

3.AC代码

#include<bits/stdc++.h>
using namespace std;
const int mm=40;
int n,m;
int a[mm],b[mm];
int main()
{
    //读入
    cin>>n>>m;
    a[1]=b[1]=1;
    //循环m次传球
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            //分不同情况处理，这里开两个数组，类似于差分操作
            if(a[j]>=1)
            {
                if(j-1<1)
                {
                    a[n]+=b[j];
                }
                else
                {
                    a[j-1]+=b[j];
                }
                if(j+1>n)
                {
                    a[1]+=b[j];
                }
                else
                {
                    a[j+1]+=b[j];
                }
                a[j]-=b[j];
            }
        }
        //加起来
        for(int j=1;j<=n;j++)
        {
            b[j]=a[j];
        }
    }
    //输出1号也就是小强的可能传到数量
    cout<<a[1];
    return 0;
}

我是千文杜博，记住我呦~~

The end