Preface

At first, I was stuck on Problem A for 20 minutes, which was a bit annoying. Then I noticed that more people had solved Problem E than Problem D, so I went for E, but it turned out that D was actually more suitable for me.

Sorting Problems: Prioritize problems that can be solved fastest based on the effort required. (Order of answering: previously solved, easy, unfamiliar, hard)
— Li Bojie, Guide to Cheating P.114

Next time, I should pick the problem that feels more intuitive, rather than blindly following the crowd (unless I have no clue about any of them).

A. Tricky Template

I'm the one who got stuck on a beginner-level problem for twenty minutes.

If (a_i = b_i), then (s_i) can be lowercase (a_i) (which ensures (c_i \neq a_i, b_i)), or an uppercase letter other than (a_i) (which ensures (s_i = c_i)).

If (a_i \neq b_i), then (s_i) must be uppercase (c_i) (which ensures (c_i \neq a_i) and (c_i \neq b_i)).

If any character cannot satisfy the above conditions, the answer is NO; otherwise, it's YES.

#include <cstdio>
using namespace std;

const int N = 25;
int n;
char a[N], b[N], c[N];

bool check() {
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i] && c[i] != a[i]) return true;
        if (a[i] != b[i] && c[i] != a[i] && c[i] != b[i]) return true;
    }
    return false;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%s%s%s", &n, a + 1, b + 1, c + 1);
        printf("%s\n", check() ? "YES" : "NO");
    }
    return 0;
}

B. Forming Triangles

Under the given conditions, a triangle is valid only if two sides are equal and the third side is not greater than these two sides (i.e., (a_i = a_j) and (a_k \le a_i, a_j)).

To avoid duplicates, we classify triangles into equilateral and non-equilateral.

Sort the side lengths in ascending order and iterate through all sides. For non-equilateral triangles, we count the number of sides equal to (a_i) multiplied by the number of sides less than (a_i). For equilateral triangles, we use the combination formula (C_x^2 = \frac{x \times (x-1)}{2}), where (x) is the count of sides equal to (a_i) encountered so far.

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 3e5 + 5;
int n, a[N], cnt[N];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        long long ans = 0;
        int end = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] != a[i - 1]) end = i - 1;
            ans += 1ll * cnt[a[i]] * end;
            ans += 1ll * cnt[a[i]] * (cnt[a[i]] - 1) / 2;
            cnt[a[i]]++;
        }
        printf("%lld\n", ans);
        for (int i = 1; i <= n; i++) cnt[a[i]]--;
    }
    return 0;
}

C. Closest Cities

Greedy approach: In the path from (x) to (y), you cannot go backwards because doing so would not shorten the distance (the nearest city is always adjacent).

Since the way forward does not affect the way backward, and all points on the path must be visited, if (x < t < y), the path length from (x) to (y) equals the path length from (x) to (t) plus the path length from (t) to (y).

Therefore, we can use a prefix-sum approach. Precompute the path lengths from city 1 to all cities. Then, for a query, we can get the answer in (O(1)) time by simple subtraction.

However, since (x) might be greater than (y), we also need to do this in reverse (because the path length forward and backward may differ). Precompute the path lengths from city (n) to all cities (suffix sum).

Note: The path length is edge weight, not node weight, so we don't need to adjust indices; direct calculation works.

#include <cstdio>
using namespace std;

const int N = 1e5 + 5;
int n, q;
long long a[N];
long long presum[N], sufsum[N];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            presum[i] = sufsum[i] = 1e18;
        }
        a[0] = -1e18, a[n + 1] = 1e18;

        presum[1] = 0;
        for (int i = 1; i < n; i++) {
            if (a[i + 1] - a[i] < a[i] - a[i - 1])
                presum[i + 1] = presum[i] + 1;
            else
                presum[i + 1] = presum[i] + a[i + 1] - a[i];
        }
        sufsum[n] = 0;
        for (int i = n; i > 1; i--) {
            if (a[i] - a[i - 1] < a[i + 1] - a[i])
                sufsum[i - 1] = sufsum[i] + 1;
            else
                sufsum[i - 1] = sufsum[i] + a[i] - a[i - 1];
        }

        scanf("%d", &q);
        for (int i = 1; i <= q; i++) {
            int x, y; scanf("%d%d", &x, &y);
            if (x < y)
                printf("%lld\n", presum[y] - presum[x]);
            else
                printf("%lld\n", sufsum[y] - sufsum[x]);
        }

        for (int i = 0; i <= n + 1; i++)
            a[i] = sufsum[i] = presum[i] = 0;
    }
    return 0;
}

D. Berserk Monsters

During the contest, I saw that more people had solved Problem E, so I went for it, but actually I should have been better at this problem.

I instantly figured out the approach, but the implemetnation had many details.

First, the monster attacking both sides can be rephrased as being attacked by both sides. That is, if the sum of the attack power of the left and right neighbors exceeds the monster's defense, the monster dies.

Only after a monster is killed do its neighboring monsters get a chance to attack others, potentially causing more deaths. Therefore, for each round, we only need to consider the neighbors of the monsters that died in the previous round (i.e., the monsters that successfully attacked others).

This process can be implemented using BFS, along with rolling arrays or queues to record the monsters to be processed in the current round and the next round.

Special Note: When data needs to be processed in layers, never let the data of the current layer and the next layer interfere with each other; i.e., never mix data from different layers.

In this problem, monsters that should die in the next round must not die in the current round.

We also need to quickly update the neighbors of each monster after a death in each round. This can be efficiently done using a linked list (a data structure that seems to have been gathering dust — when was the last time you used a linked list?).

#include <cstdio>
#include <queue>
using namespace std;

const int N = 3e5 + 5;
int n, a[N], d[N];

struct Node {
    int prev, next;
} ls[N];

void Build(int n) {
    for (int i = 1; i <= n; i++)
        ls[i] = {i - 1, i + 1};
}

void Remove(int x) {
    ls[ls[x].prev].next = ls[x].next;
    ls[ls[x].next].prev = ls[x].prev;
}

queue<int> q[2];
bool inq[2][N];
int ans[N], dead[N];
int toRemove[N], removeIdx;

void Clear() {
    for (int i = 1; i <= n; i++) {
        inq[0][i] = inq[1][i] = false;
        ans[i] = 0;
    }
    while (!q[0].empty()) q[0].pop();
    while (!q[1].empty()) q[1].pop();
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &d[i]);

        Build(n);
        a[0] = a[n + 1] = 0;
        for (int i = 1; i <= n; i++) {
            q[1].push(i);
            inq[1][i] = true;
            dead[i] = 0x3f3f3f3f;
        }
        for (int round = 1; round <= n; round++) {
            int cur = round & 1;
            while (!q[cur].empty()) {
                int x = q[cur].front(); q[cur].pop();
                if (dead[x] <= round) continue;
                inq[cur][x] = false;
                int l = ls[x].prev, r = ls[x].next;
                if (a[l] + a[r] > d[x]) {
                    toRemove[++removeIdx] = x;
                    dead[x] = round + 1;
                    ans[round]++;
                    if (l != 0 && !inq[!cur][l]) {
                        inq[!cur][l] = true;
                        q[!cur].push(l);
                    }
                    if (r != n + 1 && !inq[!cur][r]) {
                        inq[!cur][r] = true;
                        q[!cur].push(r);
                    }
                }
            }
            for (int i = 1; i <= removeIdx; i++)
                Remove(toRemove[i]);
            removeIdx = 0;
        }
        for (int i = 1; i <= n; i++)
            printf("%d ", ans[i]);
        putchar('\n');
        Clear();
    }
    return 0;
}

E. Increasing Subsequences

I saw that many people solved this problem, so I went for it, which turned out to be a mistake.

Consider adding a new number to the sequence: adding the smallest number increases the count of increasing subsequences by 1; adding largest number multiplies the count by 2 and adds 1. The multiplication by 2 comes from the fact that the new number can combine with all previous subsequences, and the +1 is because the new number itself forms a subsequence. However, if we consider the empty set as a valid subsequence (as per the problem statement), then this +1 essentially corresponds to combining with the empty set. If we treat the set as initially containing the "empty" element, then each new element alone corresponds to combining with the empty set, so when adding the largest number, we no longer need to account for the subsequence consisting of just that number. All new subsequences are formed by combining with previous ones, so we only need to multiply by 2.

Thus, the problem reduces to: starting from 1, use operations +1 and ×2 to reach (X). This can be easily done via binary decomposition. There are many ways to implement this; here's one:

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 205;
int ans[N];
long long x;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%lld", &x);
        int idx = 0, tmp = 1e9;
        while (x > 1) {
            if (x & 1) {
                ans[++idx] = 0;
                x--;
            } else {
                ans[++idx] = tmp--;
                x >>= 1;
            }
        }
        printf("%d\n", idx);
        for (int i = idx; i >= 1; i--)
            printf("%d ", ans[i]);
        putchar('\n');
    }
    return 0;
}