Command Sequence

\Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 792 Accepted Submission(s): 279
**

Problem Description

There is a robot that can move by receiving a sequence of commands.

There are four types of command in the command sequence:

• U: robot moves one unit up.
• D: robot moves one unit down.
• L: robot moves one unit left.
• R: robot moves one unit right.

Now, given a command sequence of length n. You need to find out how many substrings of the command sequence satisfy that if the robot execute the substring command, it can return to the starting position.

A substring is a contiguous sequence of characters within a string. For instance, “the best of” is a substring of “It was the best of times”. For example, “Itwastimes” is a subsequence of “It was the best of times”, but not a substring.

Input

This problem contains multiple test cases.

The first line contains an integer t (1≤t≤20) indicating the number of test cases.

For each test case, the first line contains one integer n (2≤n≤105).

The second line contains a UDLR string of length n.

Output

For each test case, output one line one integer indicating the answer.

Sample Input

1
6
URLLDR

Sample Output

2

Source

2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛

Recommend

IceyWang | We have carefully selected several similar problems for you: 7112 7111 7110 7109 7108

解题思路

如果以当前位置为起点，如果可以再次到达当前的位置那么就可以认为从当前位置可以回到当前的位置。

只需要记录从当前的位置到下次当前位置的数量即可知道子数组的数量。

//
// Created by Vector on 2021/8/31.
//

#include <iostream>
#include <map>
# include <string>
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PAIR;

int main() {
    ll t;
    cin >> t;
    while (t--) {
        map<PAIR, ll> mp;
        mp[{0, 0}]++; // 起点(0, 0)也要记录
        ll n;
        string s;
        cin >> n >> s;

        ll res = 0, x = 0, y = 0; // 初始化坐标为(0, 0)
        for (ll i = 0; i < s.length(); i++) { // 遍历整条命令
            if (s[i] == 'U') x++;
            else if (s[i] == 'D') x--;
            else if (s[i] == 'L') y++;
            else if (s[i] == 'R') y--;
            res += mp[{x, y}]; // 累加当前位置(x, y)在前面出现的次数
            mp[{x, y}]++; // 记录当前位置
        }
        cout << res << '\n';
    }
    return 0;
}

赏

谢谢你请我吃糖果

微信