• Published:

A. Three Doors

This one is very straightforward once you stop overthinking it.

Start from the door whose key you already have, then keep following the key you obtain from each newly opened door. If at some point the key becomes 0, the chain ends. If you managed to open all 3 doors in total, the answer is YES; otherwise it is NO.

Idea

  • Begin with the given key.
  • Use it to open the corresponding door and get the next key.
  • Continue until the next key is 0.
  • Count how many doors were opened along the way.
  • If the count is exactly 3, print YES.

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 10;

void solve(){

    int a[N];

    int n;

    cin >> n;

    int flag = 1;  //记录打开的门的数量

    for(int i = 1; i <= 3; i++) cin >> a[i];

    for(int i = n; a[i] != 0; i = a[i]) flag++;

    if(flag == 3) cout << "YES" << "\n";
    else cout << "NO" << "\n";

}

int main(){

    int _;

    cin >> _;

    while(_--){
        solve();
    }

    return 0;

}

B. Also Try Minecraft

The key observation here is that each query asks for the total damage over a segment, but the direction matters.

This can be preprocessed with prefix-style accumulation from both sides:

  • one array for the cost when moving left to right,
  • another for the cost when moving right to left.

Then each query becomes an O(1) subtraction.

Idea

  • Use a prefix sum array to record the total drops when moving forward.
  • Use another cumulative array to record the total increases, which are needed for answering reverse-direction queries.
  • For each query:
  • if l < r, answer with the forward prefix result,
  • if l > r, answer with the backward one.

And yes, this needs long long.

Really, use long long.

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 10;

int a[N];

int b[N],c[N];

void solve(){

    int n, m;

    cin >> n >> m;

    for(int i = 1 ; i <= n ; i++){

        cin >> a[i];

        if(a[i] < a[i-1]){
            b[i] = a[i-1] - a[i];  //处理前缀
        }
        else if(a[i] > a[i-1]){
            c[i] = a[i] - a[i-1];   //处理后缀
        }

        b[i] += b[i-1];  //构造前缀和数组
        c[i] += c[i-1];  //构造后缀和数组

    }

    while(m--){

        int l, r;

        cin >> l >> r;

        if(l < r){
            cout << b[r] - b[l] << "\n";
        }
        else cout << c[l] - c[r] << "\n";

    }

}

signed main(){

    solve();

    return 0;

}

C. Recover an RBS

This one uses a greedy approach.

Let:

  • dep be the number of currently unmatched ( while scanning,
  • vis be the number of ? seen so far.

Scan the bracket string from left to right.

  • If s[i] == '(', then dep++.
  • If s[i] == ')', then dep--.
  • If s[i] == '?', then vis++.

What matters is how the current dep affects whether the sequence can still be valid and whether the choices for ? become forced.

Greedy reasoning

If at some point dep < 0, then among the previously seen characters there must be at least one ? available (vis > 0) that can be turned into ( to repair the sequence. In that case, that ? is no longer ambiguous: its value is forced. So we do:

  • dep++
  • vis--

If dep < 0 and there is no such ?, then the sequence cannot be made valid.

Another special case is when dep == 0 && vis == 1. Then that single pending ? also becomes forced, so we again do:

  • dep++
  • vis--

By the time the scan finishes, all states that were uniquely determined during traversal have already been eliminated. What remains are only the unresolved dep and vis values.

At the end:

  • if abs(dep) == vis, then the rest can also be uniquely resolved and the bracket sequence is valid with a unique recovery, so print YES,
  • otherwise print NO.

Code

#include <bits/stdc++.h>
using namespace std;

void solve(){

    string s;

    cin >> s;

    int dep = 0, vis = 0;

    for(int i = 0 ; i < s.size() ; i++){

        if(s[i] == '(') dep++;
        else if(s[i] == ')'){dep--;
            if(dep < 0){
                if(vis > 0)dep++, vis--;
                else{  //vis <= 0 说明无法匹配，序列非法
                    dep = 1, vis = 0;
                    break;
                }
            }
        }
        else vis++;

        if(dep == 0 && vis == 1) dep++, vis--;

    }

    if(abs(dep) == vis) cout << "YES" << '\n';
    else cout << "NO" << '\n';

}

int main(){

    int _;

    cin >> _;

    while(_--){
        solve();
    }

    return 0;

}

A few afterthoughts

Problem A was basically free points, but there were so many possible ways to write it that it was oddly easy to get messy while coding.

Problem B looked exciting at first because of the Terraria-flavored setting, but once the statement is understood, it is just a prefix-sum problem and not difficult.

The annoying part was missing the range of a_i during the contest and forgetting long long, which caused four wrong answers in a row.

WA screenshot

So once again:

  • remember long long
  • remember long long
  • remember long long

As for Problem C, bracket sequence problems still feel painful. This one was a reminder to spend more time filling that gap, because not being comfortable with greedy on parentheses is a pretty helpless feeling.

Even more surprising: apparently more people solved D than C. D seemed to be a sparse table template problem, and that topic still needs work.

Also, when reading English statements, it really pays to make sure the problem is understood correctly. Solving the wrong interpretation hurts way more than the actual implementation.

Related Posts