英文题干

Red stands at the coordinate (0,0) of the Cartesian coordinate system. She has a string of instructions: up, down, left, right (where 'right' increases the x-coordinate by 1, and 'up' increases the y-coordinate by 1).

Now Red wants to select a continuous substring of instructions and execute them. Red hopes that the final execution of the instructions can pass through the coordinate (x,y). She wants to know how many selection options there are.

Input:

The first line contains three integers 𝑛, 𝑥, and 𝑦 (, ) — the length of the instruction string and the coordinates Red hopes to pass through.

The second line contains a string of length 𝑛 n, consisting of the characters ′𝑊′, ′𝑆′, ′𝐴′, and ′𝐷′ — the four directions: up, down, left, and right, respectively.

Output:

Output one integer representing the number of selection options for the continuous substring.

中文题干

Red站在笛卡尔坐标系的原点(0,0)处。她手上有一串指令包含：上(W)、下(S)、左(A)、右(D)（其中“右”会使x坐标增加1，“上”会使y坐标增加1）。

现在，Red想选择一段连续的指令并执行。她希望最终执行这些指令后能通过坐标(x,y)。她想知道有多少种选择选项。

思路

  1. 首先考虑最简单的情况：

    (0,0)就是目标点。这种情况下显然任意连续的组合都满足条件，直接对1到n求和即可。

  2. 接下来考虑一般情况。

    我们考虑遍历纵坐标，找到纵坐标差值为y且对应的横坐标差值为x的连续段。此时后面从段尾出发到n的组合都是可行的（因为题目只要求路径经过目标点)。这里为方便处理数组负数索引的情况，将纵坐标分为正和负两部分存储，分别进行计算。

AC代码

时间复杂度：O()(最坏的情况)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;

ll n, x, y, ans;

struct
{
    vector<int> arr;
} pos[maxn], nag[maxn]; // 正、负的纵坐标(p1)下的指令索引

int a[maxn]; // 存储横坐标

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // 1.输入和初始化
    cin >> n >> x >> y;
    if (x == 0 && y == 0) // 若目标坐标是(0,0)，那么任意长度的子串都是有效的
    {
        cout << n * (n + 1) / 2;
        return 0;
    }

    // 2.读取指令并计算位置变化
    pos[0].arr.push_back(0);
    int p1 = 0, p2 = 0; // 纵坐标(p1), 横坐标(p2)
    int mx = 0, mn = 0; // 纵坐标的最大值(mx)、最小值(mn)
    cin.ignore();

    for (int i = 1; i <= n; i++)
    {
        char s = cin.get();
        if (s == 'W')
            p1++;
        if (s == 'S')
            p1--;
        if (s == 'D')
            p2++;
        if (s == 'A')
            p2--;

        if (p1 >= 0) // 纵坐标更新后为正
            pos[p1].arr.push_back(i);
        else // 纵坐标更新后为负
            nag[-p1].arr.push_back(i);

        a[i] = p2;
        mx = max(p1, mx);
        mn = min(p1, mn);
    }

    // 3.查找满足条件的连续指令段
    for (int i = mn; i < 0; i++) // PART1: 处理负纵坐标区间
    {
        vector<int> arr1 = nag[-i].arr; // 纵坐标在i的所有指令索引
        vector<int> arr2;               // 纵坐标 i+y 处的所有指令索引
        // 通过判断 i+y 的正负来决定从 nag 还是 pos 中获取索引。
        if (i + y < 0)
            arr2 = nag[-i - y].arr;
        else
            arr2 = pos[i + y].arr;

        // for (int i : arr2)
        // {
        //     cout << i << endl;
        // }

        for (int i = 0; i < arr1.size(); i++)
        {
            for (int j = 0; j < arr2.size(); j++)
            {
                // 确保指令段连续且索引 arr2[j] 在 arr1[i] 之后
                // 同时确保指令段之间，横坐标变化量恰好是x
                if (arr2[j] > arr1[i] && a[arr2[j]] - a[arr1[i]] == x)
                {
                    // 满足上述条件情况下, arr2[j] 到 n 的所有指令段都能满足
                    ans += n - arr2[j] + 1;
                    break;
                }
            }
        }
    }

    for (int i = 0; i <= mx - y; i++) // PART2: 处理正纵坐标区间，逻辑同理
    {
        vector<int> arr1 = pos[i].arr;
        vector<int> arr2;
        if (i + y < 0)
        {
            arr2 = nag[-i - y].arr;
        }
        else
            arr2 = pos[i + y].arr;
        for (int i = 0; i < arr1.size(); i++)
        {
            for (int j = 0; j < arr2.size(); j++)
            {
                if (arr2[j] > arr1[i] && a[arr2[j]] - a[arr1[i]] == x)
                {
                    ans += n - arr2[j] + 1;
                    break;
                }
            }
        }
    }

    // 4.输出结果
    cout << ans;
    return 0;
}
// Inspired by LJY