先用前缀和预处理从第一个操作做到当前操作后到达的位置,倒序考虑,维护记录相对位置的桶子即可(桶子里面记录有关最近一个到达那个相对位置的操作序号之类的信息)。
具体方法这题看代码更好理解:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, a, b, ans;
char c;
pair<int, int> m[1000005];
map<pair<int, int>, int> t;
signed main()
{
cin >> n >> a >> b;
if (a == 0 && b == 0) {
cout << n * (n + 1) / 2;
return 0;
}
for (int i = 1; i <= n; i++) {
cin >> c;
if (c == 'A') m[i] = {m[i - 1].first - 1, m[i - 1].second + 0};
if (c == 'S') m[i] = {m[i - 1].first + 0, m[i - 1].second - 1};
if (c == 'W') m[i] = {m[i - 1].first + 0, m[i - 1].second + 1};
if (c == 'D') m[i] = {m[i - 1].first + 1, m[i - 1].second + 0};
}
for (int i = n; i > 0; i--) {
t[{m[i].first - a, m[i].second - b}] = n - i + 1;
ans += t[{m[i - 1].first, m[i - 1].second}];
}
cout << ans;
return 0;
}