CF626A Robot Sequence 题解

· · 题解

题目传送门

题目大意

给你一个长度为 n 的字符串 s，要你计算有多少个非空子串可以让 Calvin 的机器人从原点出发回到原点。

解题思路

算法 1 暴力枚举 时间复杂度 O(n ^ 3)

具体思路 ：

枚举子串的左右两个端点，判断其是否满足条件。（条件判断即为该子串中 U 和 D 、 L 和 R 的个数是否一致）

没啥好说的，上代码！ (用 unordered_map 记录 U, D, L, R 的出现次数。)

#include <unordered_map>
#include <iostream>
using namespace std;
int n, res;
string s;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s; // 输入
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) { // 枚举 i, j
            int x = 0, y = 0;
            unordered_map<char, int> cnt;
            for (int k = i; k <= j; k++)
                cnt[s[k]] += 1; // 计算UDLR的出现次数
            if (cnt['U'] == cnt['D'] and cnt['L'] == cnt['R'])
                res += 1;
        }
    }
    cout << res << "\n"; // 输出res
    return 0;
}

由于该题评测数据水，所以该算法可以通过此题!

算法 2 前缀和 时间复杂度 O(n ^ 2)

具体思路 :

基于算法 1，因为我们在最内层循环中用了 O(n) 的时间统计 UDLR 的出现次数，所以可以考虑使用前缀和算法预处理出各个字母的出现次数，这样我们的算法的时间复杂度就由 O(n ^ 3) 降到 O(n ^ 2) 了。

#include <iostream>
#define maxn 512
using namespace std;
int n, res;
string s;
int cnt[5][maxn];
string letter = "$UDLR";
int Count(int, int, int);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s; // 输入
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= 4; j++)
            cnt[j][i] = cnt[j][i - 1] + (s[i] == letter[j]);
            // 前缀和预处理
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            if (Count(1, i, j) == Count(2, i, j) and Count(3, i, j) == Count(4, i, j))
                res += 1;
                // O(1) 计算是否满足条件
    cout << res << "\n"; // 直接输出
    return 0;
}
int Count(int alpha, int Left, int Right) {
// 函数功能 ：计算字母alpha在s的子串(Left, Right)中出现的次数
    return cnt[alpha][Right] - cnt[alpha][Left - 1];
}

（所有代码均可直接通过，请放心食用！）