首页 > 试题广场 >

我不是大富翁

[编程题]我不是大富翁
  • 热度指数：189 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,提到大富翁游戏！就想到环！！就想到经典的约瑟夫问题！！！作为经典问题，其出彩的展示了数学思维在实际问题中的应用，启发了一代又一代的算竞人。
\,\,\,\,\,\,\,\,\,\,好了，不要再约瑟夫了，都是经典问题害的你，没法正常的玩大富翁游戏。现在，让我们来愉快的玩大富翁吧！
\,\,\,\,\,\,\,\,\,\,
\,\,\,\,\,\,\,\,\,\,\rm\mathcal Rabbit 拿到了一张环形的大富翁地图，地图被平均划分为了 n 个地块，地块的编号以 1 为起点，顺时针进行排布。即 1 号地块的顺时针方向依次为 2, 3, \dots 号地块；1 号地块的逆时针方向依次为 n, n-1, \dots 号地块（由于是环形的，所以 1 号地块与 n 号地块相邻，如下图所示）。
\,\,\,\,\,\,\,\,\,\,游戏过程如下：系统会给定一个长度为 m 的行动力序列 a_1,a_2,\dots,a_m ，在第 i (1\leqq i \leqq m) 回合，\mathcal Rabbit 都需要移动 a_i 个地块，但是他可以自由选择移动的方向（换句话说，可以自由选择是向逆时针还是顺时针方向移动 a_i 个地块）。
\,\,\,\,\,\,\,\,\,\,在游戏的开始时，\rm \mathcal Rabbit 位于 1 号地块，他想知道是否存在这样一种移动方式，使得 m 个回合后他依旧在 1 号地块。

输入描述:
\,\,\,\,\,\,\,\,\,\,每个测试文件仅有一组测试数据。
\,\,\,\,\,\,\,\,\,\,第一行输入两个整数 n 和 m (1 \leqq n, m \leqq 5000) 表示地块数量和行动回合数。
\,\,\,\,\,\,\,\,\,\,第二行输入 m 个整数 a_1,a_2,\dots,a_m (0\leqq a_i\leqq 2 \cdot 10^5) 表示行动力序列。


输出描述:
\,\,\,\,\,\,\,\,\,\,如果 m 个回合后 \rm \mathcal Rabbit 依旧在 1 号地块，则输出 \rm YES ；否则，请输出 \rm NO 。您可以以任何大小写形式输出答案，例如，\rm yEs 、\rm yes 和 \rm YeS 都将被视为肯定的回答。
示例1

输入

360 3
120 120 120

输出

YES
示例2

输入

50 5
30 0 10 10 10

输出

yES
示例3

输入

114 5
14 1 9 1 9

输出

no

备注:
\,\,\,\,\,\,\,\,\,\,如果您需要使用 \rm{Python} 解题，我们建议您在提交时选择 \rm{pypy2} 或 \rm pypy3 。
算法知识视频讲解
添加回答
银河护胃队头像 银河护胃队
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;

int n,m;
int a[N];
bool dp[N][N]; //dp[i][j] 表示第i次跳跃能否到达位置j 能到达则标记为true，否则标记为false

void solve(){
   
    //将1-n转化为0-n-1
    //第一次跳跃  能跳跃到的位置标记为true
    dp[1][(0+a[1])%n]=true;//顺时针走
    dp[1][((0-a[1])%n+n)%n]=true;//逆时针走
   
    //后续m-1次跳跃
    for(int i=2;i<=m;i++){//i代表第i次跳跃
        for(int j=0;j<n;j++){//枚举0-n-1 即枚举所有位置
            //第i-1次跳跃能跳到的位置  （也就是上次跳跃能跳跃到的位置）
            if(dp[i-1][j]){
                dp[i][(j+a[i])%n]=true; //顺时针走
                dp[i][((j-a[i])%n+n)%n]=true; //逆时针走
            }
        }
    }
     
    if(dp[m][0]){//第m次跳跃能到达位置0
        cout<<"YES"<<endl;
    }else{//第m次跳跃不能到达位置0
        cout<<"NO"<<endl;
    }
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
   
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i];
    }
   
    solve();

    return 0;
}

发表于 2026-03-06 19:37:01 回复(0)
提交观点

问题信息

难度：
1条回答 24浏览

热门推荐

相关试题

我不是大富翁

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号