自动搬运

查看原文

来自洛谷，原作者为

	红黑树 https://rbtr.ee

搬运于2025-08-24 21:45:08，当前版本为作者最后更新于2022-07-12 20:33:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给定 $N$ 个点的图，每个点有两条出边，给定一条长 $M$ 的指令，从 $1$ 出发按照指令移 $K$ 轮，求最终位置。

思路

可以对移动的过程进行模拟，但由于 $K$ 很大，这样做比较低效。

由于每一轮移动的指令都是一样的，所以我们可以将一轮移动看作一个整体。由于一共只有 $N$ 个点，所以最多移动 $N$ 轮以后必然会产生环，环中的移动是重复的，可以利用同余来处理。

因此，我们从 $1$ 出发模拟移动直到找到环，再根据 $K$ 在环上还是环外来求解终点即可。

复杂度

时间

• 模拟找环次数 $\mathcal O(N)$
• 每次移动 $\mathcal O(M)$
• 总共 $\mathcal O(NM)$。

空间

• 记录图 $\mathcal O(N)$
• 记录指令 $\mathcal O(M)$
• 总共 $\mathcal O(N + M)$

Code

#include <icecream>
#include <utility>
#include <vector>

using namespace std;
using tp = long long int;

tp m;
vector<char> d;
vector<pair<tp, tp>> go;

struct Item_t {
  tp p, r;

  Item_t() = default;
  Item_t(tp _p, tp _r) : p(_p), r(_r) {}

  Item_t move() {
    p = (d[r] == 'L' ? go[p].first : go[p].second);
    r = (r + 1) % m;
    return *this;
  }

  bool operator==(const Item_t& comp) const {
    return p == comp.p && r == comp.r;
  }

  bool operator!=(const Item_t& comp) const {
    return !(*this == comp);
  }
};

signed main() {
  tp n, k;
  Item_t _1(1, 0), _2(1, 0);
  scanf("%lld%lld%lld", &n, &m, &k);
  k *= m;
  d = vector<char>(m);
  go = vector<pair<tp, tp>>(n + 1);
  for (tp i = 1; i <= n; ++i) {
    scanf("%lld%lld", &go[i].first, &go[i].second);
  }
  for (auto&& i : d) {
    cin >> i;
  }
  while (k--) {
    _2.move();
    if (_1.move() == _2.move()) {
      break;
    }
  }
  k += !~k;
  if (k) {
    tp cnt = 1;
    while (_1.move() != _2) {
      ++cnt;
    }
    for (k %= cnt; k--; _1.move()) {
    }
  }
  cout << _1.p << '\n';
  return 0;
}