在Codeforces中解决935B - Fafa和门

Question

我有一个关于935B - Fafa和CodeForces的门的问题。我的代码对于第一个测试用例是有效的，但是它在测试用例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;
}

Answer 1

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

即使您将for循环修复为在i<a之后停止，也可以使用以下语句：

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

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

在循环的每一次迭代中，您需要首先查看他是否在gate，然后适当地更新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;