算法
(思维、模拟) $O(N\log N)$
你知道 领地 吗?我知道。
我们要求的问题其实就是机器人通过执行 $K$ 次指令集 $S$ 得到的点群的并集。
记执行一次指令集 $S$ 到达的终点坐标是 $(a, b)$,将指令 $S_1 \sim S_N$ 到达的横纵坐标分别除以 $a$ 和 $b$,然后以余数与商的差值进行分类。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::set;
using std::map;
using std::min;
using std::swap;
using std::vector;
using std::string;
using ll = long long;
using P = std::pair<ll, ll>;
int main() {
string s;
ll k;
cin >> s >> k;
int n = s.size();
set<P> st;
int x = 0, y = 0;
for (char c : s) {
st.emplace(x, y);
if (c == 'L') --x;
if (c == 'R') ++x;
if (c == 'U') --y;
if (c == 'D') ++y;
}
st.emplace(x, y);
if (x == 0 and y == 0) {
cout << st.size() << '\n';
return 0;
}
vector<P> ps;
for (P p : st) ps.push_back(p);
if (x == 0) {
swap(x, y);
for (P& p : ps) swap(p.first, p.second);
}
if (x < 0) {
x *= -1;
for (P& p : ps) p.first *= -1;
}
if (y < 0) {
y *= -1;
for (P& p : ps) p.second *= -1;
}
assert(x > 0);
assert(y >= 0);
map<P, vector<P>> mp;
for (P& p : ps) {
auto [nx, ny] = p;
if (nx > 0) {
ll i = nx / x;
nx -= x * i; ny -= y * i;
}
else {
ll i = (-nx + x - 1) / x;
nx += x * i; ny += y * i;
}
mp[P(nx, ny)].push_back(p);
}
ll ans = 0;
for (auto& np : mp) {
vector<ll> d;
for (P p : np.second) {
d.push_back((p.first + n) / x);
}
sort(d.begin(), d.end());
rep(i, d.size()) {
ll w = k;
if (i + 1 < d.size()) w = min(w, d[i + 1] - d[i]);
ans += w;
}
}
cout << ans << '\n';
return 0;
}