14444 - Big orange cat's puzzle

Key points: How to determine + construct the solution. You've already written the determination part in HW4, so how do we construct the solution?

In HW4, you probably used an array to record how many times each character appeared. In other words, that array recorded which characters you need. We can make good use of this property.

One hint is that Big Orange is very lazy and wants to take from the front. Therefore, we can start directly from the left, adding each needed letter to the answer as we encounter it, then decrementing the corresponding position in the array by 1. Finally, if we've collected the same number of characters as in

$A_i$, it means we can construct the solution.

As for the lexicographically smallest order, since you're trying to take from the leftmost side, this approach naturally results in the lexicographically smallest order.

Subtask 1

$A$ and

$B$ are of equal length and each is sorted in ascending lexicographical order. This means you only need to directly check if the two strings are equal. If they are equal, simply output all indices.

Subtask 2

This is your homework problem, just with the additional requirement of outputting all indices if it's feasible.

Subtasks 3 and 4

The approach is the same as the full-score solution. Subtask 3 is designed to prevent potential special methods (I'm not sure what they might be) that can't achieve the lexicographically smallest order.

AC Code

#include <stdio.h>
#include <string.h>

int main() {
    int n, m, k;
    scanf("%d", &n);
    char A[10005], B[10005];
    int cnt[150];
    int ans[10005];
    for (int i = 0; i < n; i++) {
        scanf("%s %s", A, B);
        int al = strlen(A);
        int bl = strlen(B);

        int now = 0;

        for (int j = 0; j < 150; j++)
            cnt[j] = 0;
        for (int j = 0; j < al; j++)
            cnt[A[j]]++;
        for (int k = 0; k < bl; k++) {
            if (cnt[B[k]] > 0) {
                cnt[B[k]]--;
                ans[now++] = k;
            }
        }

        if (now != al) {
            printf("baganono\n");
        }
        else {
            for (int j = 0; j < al; j++) {
                printf("%d", ans[j] + 1);
                if (j != al - 1) {
                    printf(" ");
                }
                else {
                    printf("\n");
                }
            }
        }
    }
}

Tips

Please review the approaches for all problems and the content of the solution presentation slides : )