c++ - 解决 935B - Fafa 和 Codeforces 中的大门

Question

我有一个关于 CodeForces 中的 935B - Fafa 和 Gates 的问题。我的代码适用于第一个测试用例，但它卡在测试用例 20 上，这是我使用的代码，有人可以告诉我我在这里做错了什么吗？谢谢！

#include <iostream>
#include <string>
using namespace std;

int main(){
    long long a, x = 0, y = 0, total = 0;
    cin >> a;
    string s;
    cin >> s;
    for (long long i = 0; i <= a; i++){
        if (s[i] == 'U') x += 1;
        if (s[i] == 'R') y += 1;
        if (x == y && s[i] == s[i+1]) total += 1;
    }
    cout << total << endl;
}

标签： c++

Answer 1

除了i<=a我在上面的评论中提到的问题之外，还有另一个问题。

即使您将 for 循环修复为在 之后停止i<a，那么此语句：

if (x == y && s[i] == s[i+1]) total += 1;

仍将引用无效索引，s[i+1]因为i+1在数组的最后一次迭代中是无效索引。

在循环的每次迭代中，您需要先查看他是否在门口，然后更新x或y适当地更新，然后评估他是否改变了王国。

如果他在一个位置x > y，你就知道他在下界。同样，如果y > x，您知道他在地图上的上层王国。

我认为这更接近你想要的：

bool topKingdom = false;  // initially at 0,0.  Fafa is currently in the "lower kingdom" on the map

for (long long i = 0; i < a; i++){

    bool atGate = (x == y);

    if (s[i] == 'U') y++;
    if (s[i] == 'R') x++;

    // if we were previously "at a gate", assess if we are now in a new kingdom from before
    if (atGate && !topKingdom && y > x) {
        topKingdom = true;
        total++;
    }
    else if (atGate && topKingdom && x > y) {
       topKingdom = false;
       total++;    
    }
}
cout << total << endl;