菜鸟一个，写个个人代码题解

下面的部分都是本人的个人理解，如果有错误，请大家斧正。
首先，这道题目可以理解为解决这么一个问题：如果我们想让Rabbit的最终位置在1保持不变，那么此时我们这样思考，我们现在假设Rabbit现在已经到达了最终的目的地同时还是1这个位置，也就是保持不动，那么我们可以到达这个位置的条件是什么呢？实际上就是距离你位置1距离为a[m]的位置是否存在上一次跳转的记录（实际上也就是上一次你在进行第m-1次跳转的之后可能到达位置的记录），我来举个例子，就以题目示例1举例子：

360 3
120 120 120

一开始你的位置就是1，但是为了方便计算，我们实际上可以将这个图变为0~n-1的图像，这个地方应该可以理解到，后面的代码大家就知道为什么需要这样变了。
一开始你在位置0，那么你可以跳到的位置就是（(0 + 120) % 360）和((0 - 120 % 360) + 360) % 360两个位置，那么我们就给这两个位置设置为为1，表示的是我走第一步可以走到的位置,
实际公式： f[(0 + k) % n] = 1,f[((0-k % n) + n) % n] = 1;
那么我们在下一步需要寻找我们可以跳到哪些位置就可以通过枚举0 ~ n - 1的位置，找一下判断一下第1次可以走到的位置，然后将第1次可以走到的位置继续顺时针走一下a[2]，再逆时针走一下a[2]看看可以走到哪些位置，然后将这些位置记录为2,表示这些位置是Rabbit第2次走到的。依次类推，第3次想看看可以跳到哪些位置，就只需要看看第2次我们跳到哪里去了，然后通过第2次跳到的位置找到我们第3次可以跳到的地方，记录=3，下面直接来看下：\

代码一

#include <iostream>
using namespace std;
const int N = 5010;
int f[N][N];
int n, m; 
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    
    // 第1次跳转单独列出来
    int k;
    cin >> k; 
    f[1][k % n] = 1;
    f[1][((-k % n) + n) % n] = 1;
      
    for (int i = 2; i <= m; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < n; j++) { // 枚举一下0 ~ n - 1的所有位置
            if (f[i - 1][j] == i - 1) { // 如果当前是第 i - 1 次跳跃的时候到达的位置就更新一下第 i 次跳跃可以跳跃到的位置
                f[i][(((j + x) % n) + n) % n] = i; // 顺时针跳转
                f[i][(((j - x) % n) + n) % n] = i; // 逆时针跳转
            }
        }
    }
    if (f[m][0] == m) cout << "YES"; // 最后就来看一下跳了第 m 次之后是否可以跳到0这个位置，那么也就是f[m][0]会记录=m的情况;
    else cout << "NO"; // 反之则是到不了咯
       
    return 0;
}

这段代码的内存消耗还是蛮大的，我们现在来尝试一下是否可以优化一下空间，将二维转直接变为一维，对于本人的这种写法本人觉得应该是不可以直接转为一维的，因为如果转为一维这里更新的时候就会变成这个样子：\

if (f[j] == i - 1) { // 如果当前是第 i - 1 次跳跃的时候到达的位置就更新一下第 i 次跳跃可以跳跃到的位置
                f[(((j + x) % n) + n) % n] = i; // 顺时针跳转
                f[(((j - x) % n) + n) % n] = i; // 逆时针跳转
            }

如此你此时就可能会造成它还没有遍历到的第j个位置的位置f[j] = i,这样就会造成第i - 1次跳跃可能达到情况有损失了，所以这里是不允许直接转换为一维的，但是我们可以通过滚动数组的方式来优化一下。\

代码二

#include <iostream>
using namespace std;
const int N = 5010;
int f[2][N];
int n, m;
   
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    int k;
    cin >> k;
    f[0][k % n] = 1;
    f[0][((-k % n) + n) % n] = 1;
       
    for (int i = 2; i <= m; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < n; j++) {
            if (f[i % 2][j] == i - 1) {
                f[(i + 1) % 2][(((j + x) % n) + n) % n] = i;
                f[(i + 1) % 2][(((j - x) % n) + n) % n] = i;
            }
        }
    }
    if (f[(m + 1) % 2][0] == m) cout << "YES";
    else cout << "NO";
       
    return 0;
}

题解 | #我不是大富翁#

菜鸟一个，写个个人代码题解

代码一

代码二