P3083 题解

红黑树 · 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;
}