题解 | #我不是大富翁#

题目链接

题目描述

在一张有 $n$ 个地块的环形大富翁地图上，地块从 $0$ 到 $n-1$ 顺时针编号。游戏开始时，玩家位于 $0$ 号地块。

游戏共进行 $k$ 个回合。在一个长度为 $k$ 的行动力序列 $a$ 中，第 $i$ 回合的行动力为 $a_i$ 。在每个回合，玩家可以自由选择移动方向（顺时针或逆时针），并移动 $a_i$ 个地块。问题是：是否存在一种移动方式，使得在 $k$ 个回合结束后，玩家能恰好回到 $0$ 号地块。

解题思路

本题的核心是判断经过一系列操作后，能否到达一个特定的状态。这是一个经典的可达性问题，非常适合使用动态规划来解决。

问题的关键在于，在第 $i$ 回合，如果我们当前的位置是 $p$ ，行动力是 $a_i$ ，我们可以移动到 $(p + a_i) \pmod n$ 或者 $(p - a_i) \pmod n$ 。我们不需要记录每一步的具体路径，只需要知道在每个回合结束后，我们可能处于哪些位置。

1. 状态定义

我们可以定义一个状态数组，用于记录在每个回合结束后所有可能到达的位置。设 $S_i$ 是一个集合，表示在第 $i$ 回合结束后，玩家所有可能到达的位置（地块编号）。

2. 状态转移

初始状态：在游戏开始前（第 0 回合），玩家唯一可能的位置就是起点 $0$ 。所以， $S_0 = \{0\}$ 。
转移过程：假设我们已经知道了第 $i-1$ 回合后所有可能的位置集合 $S_{i-1}$ 。现在是第 $i$ 回合，行动力为 $a_i$ 。对于 $S_{i-1}$ 中的每一个可能位置 $p$ ，我们都可以选择顺时针或逆时針移动 $a_i$ 步。
- 顺时针移动：到达新位置 $(p + a_i) \pmod n$ 。
- 逆时针移动：到达新位置 $(p - a_i) \pmod n$ 。
因此，第 $i$ 回合结束后所有可能的位置集合 $S_i$ 就是由所有 $S_{i-1}$ 中的位置经过这两种移动方式得到的新位置的并集。

$S_i = \bigcup_{p \in S_{i-1}} \{ (p + a_i) \pmod n, (p - a_i) \pmod n \}$

3. 实现方式与空间优化

我们可以用一个布尔数组 $dp$ 来表示集合 $S$ ， $dp[j] = \text{true}$ 表示位置 $j$ 是可能到达的。

由于计算第 $i$ 回合的状态只依赖于第 $i-1$ 回合的状态，我们可以使用滚动数组的思想进行空间优化，只需要两个大小为 $n$ 的布尔数组交替使用，或者一个布尔数组和一个临时集合/数组来更新状态。这样可以将空间复杂度从 $\mathcal{O}(k \cdot n)$ 优化到 $\mathcal{O}(n)$ 。

算法流程如下：

初始化一个大小为 $n$ 的布尔数组 $dp$ ，dp[0] = true，其余为 false，表示初始位置在 $0$ 。
对 $k$ 个行动力 $a_i$ 进行遍历：

a. 创建一个临时的布尔数组 $next\_dp$ ，全部初始化为 false。

b. 遍历所有地块 $j$ 从 $0$ 到 $n-1$ 。

c. 如果 $dp[j]$ 为 true（表示位置 $j$ 在上一回合是可达的），则计算出从 $j$ 出发本回合能到达的两个新位置，并在 $next\_dp$ 中将它们标记为 true。

d. 用 $next\_dp$ 更新 $dp$ 。
所有回合结束后，检查 $dp[0]$ 的值。如果为 true，则说明可以回到起点，输出 "YES"；否则输出 "NO"。

注意：在计算逆时针移动时，为避免负数取模的问题，可以使用 (p - a_i % n + n) % n 的方式来确保结果为正。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<bool> dp(n, false);
    dp[0] = true;

    for (int i = 0; i < k; ++i) {
        int move;
        cin >> move;
        move %= n;

        if (move == 0) continue;

        vector<bool> next_dp(n, false);
        for (int j = 0; j < n; ++j) {
            if (dp[j]) {
                next_dp[(j + move) % n] = true;
                next_dp[(j - move + n) % n] = true;
            }
        }
        dp = next_dp;
    }

    if (dp[0]) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        boolean[] dp = new boolean[n];
        dp[0] = true;

        for (int i = 0; i < k; i++) {
            int move = sc.nextInt();
            move %= n;
            
            if (move == 0) continue;

            boolean[] next_dp = new boolean[n];
            for (int j = 0; j < n; j++) {
                if (dp[j]) {
                    next_dp[(j + move) % n] = true;
                    next_dp[(j - move + n) % n] = true;
                }
            }
            dp = next_dp;
        }

        if (dp[0]) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

n, k = map(int, input().split())
moves = list(map(int, input().split()))

# dp[i] 表示是否能到达位置 i
dp = [False] * n
dp[0] = True

for move in moves:
    move %= n
    if move == 0:
        continue
    
    next_dp = [False] * n
    for i in range(n):
        if dp[i]:
            # 顺时针
            next_dp[(i + move) % n] = True
            # 逆时针
            next_dp[(i - move) % n] = True
    dp = next_dp

if dp[0]:
    print("YES")
else:
    print("NO")

算法及复杂度

算法：动态规划
时间复杂度： $\mathcal{O}(k \cdot n)$ 。外层循环遍历 $k$ 个回合，内层循环遍历 $n$ 个地块来更新可达状态。
空间复杂度： $\mathcal{O}(n)$ 。我们使用了一个大小为 $n$ 的滚动数组来存储每个回合的可达性状态。