14449 - Big orange cat's puzzle II

希望大家不要討厭大橘 QQ

為了跟程式碼比較接近，接下來的敘述會以 0-based 為主

題意

找到一個最小的合法區間

$[l,r]$，然後輸出從

$B_l\sim B_r$ 拿出一些字元重新排列後，有辦法組出

$A$ 的最小字典序解

Subtask 1

其實跟 HW, Lab 的第一個子任務一樣，只需要判兩個字串是不是一樣就好了

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

char A[10005], B[10005];
int cnt[150], cnt1[150];
int ans[10005];

int main() {
    int n, m, k;
    scanf("%d", &n);
    while (n--) {
		scanf("%s %s", A, B);
		int al = strlen(A);
		int bl = strlen(B);
        if (strcmp(A, B) == 0) {
            printf("1 %d\n", al);
            for (int i = 1; i <= al; i++)
                printf("%d%c", i, " \n"[i == al]);
            continue;
        }
        else {
            printf("baganono\n");
        }
    }
    return 0;
}

這樣理論上可以對一筆，但我第二個測資有點出太爛，導致這樣可以對兩筆，2/6

Subtask 2

跟 HW4, Lab4 的子任務一樣，我們複習一下 Lab4:

然後在 Lab4 的輸出中加上：printf("%d %d\n", ans[0] + 1, ans[al - 1] + 1);，就能完成這個子任務了

Subtask 3

這個子任務你需要找到一個最好的

$l,r$，Hint 告訴你需要枚舉 l, r，那我們先將其放到程式碼中

接著我們再複習一次 lab4 的內容，把 lab4 裡面在判斷的程式碼全部放進去。有幾個地方需要修改：

• 一開始是用 for (int k = 0; k < bl; k++)，但現在我們需要限制範圍，所以改成：for (int k = l; k <= r; k++)
• 怎麼知道哪個是最好的？
  • 首先紀錄 ansl, ansr，代表目前最好的答案（初始值可以設定為 0, 100000000 之類的）
  • 原本算答案是用 ans[now++] = k，但現在這個可能不是最好的答案，所以先用其他陣列存著：tmpans[now++] = k
  • 如果有答案，如果 r - l < ansr - ansl，那麼就將 tmpans 的複製過去 ans，並更新 ansl, ansr
• 最後就是判斷有沒有解並輸出，相信這個不需要額外說明
• 這個解的時間複雜度會是
  $\mathcal{O}(n\times \mid S{\mid }^2)$

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

int main() {
    int n, m, k;
    scanf("%d", &n);
    char A[10005], B[10005];
    int cnt[150], tmpcnt[150];
    int ans[10005], tmpans[10005];
    for (int i = 0; i < n; i++) {
        scanf("%s %s", A, B);
        int al = strlen(A);
        int bl = strlen(B);
        int flag = 1;
        int ansl = 0, ansr = 10000000;
        for (int l = 0; l < bl; l++) {
            for (int r = l; r < bl; r++) {
                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 = l; k <= r; k++) {
                    if (cnt[B[k]] > 0) {
                        cnt[B[k]]--;
                        tmpans[now++] = k;
                    }
                }

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

Subtask4

這個子任務其實只是 Subtask5 的弱化版，沒有特別意義，如果你 Subtask3 使用的計算方式足夠快，或是 Subtask5 的太慢，那你就會得到這個測資

這裡提供幾個加速方式：

1. 如果目前的 r - l > ansr - ansl，那就不需要再枚舉一次
2. 不要在枚舉的過程中構造答案，先得出最好的 l, r 再說

出題者在出這題的時候其實不知道有沒有辦法拿到 5/6，只是假設可能有人 Subtask5 沒寫好還是有一點分數

Subtask5

這裡用到一個叫做雙指針的技巧，假設有一個 function valid(l, r)，會回傳那個區間是不是合法的，那麼 l, r 對於 valid 將會有單調性（單調性應該在微積分中學到過了），也就是對於一個固定的 l，r 越大就越有可能是合法的；對於固定的 r，l 越大越不可能是合法的，我們可以好好利用這個性質

1. 首先固定 l = 0，找到第一個使其合法的 r，這是第一組答案
2. 將 l 往右一格，這時會有兩種情況：
   • 還是合法的：那你得到了一個更好的答案
   • 變不合法：那就再把 r 往前推直到合法
3. 不斷重複此過程，並在過程中記錄最好的區間，就會得到答案，時間複雜度
   $\mathcal{O}(n\times n)$，約等於
   $5\times {10}^6$，能夠 AC

#include <stdio.h>
#include <string.h>
// using namespace std;

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

		int now = 0;

		for (int i = 0; i < 150; i++)
			cnt[i] = 0;
		for (int i = 0; i < al; i++)
			cnt[A[i]]++;
		int l, r, remain = 0;
		for (int j = 0; j < 150; j++)
			remain += (cnt[j] > 0);

		l = 0, r = 0;
		int bestl = 0, bestr = bl;
		for (; r < bl; r++) {
			cnt[B[r]]--;
			if (cnt[B[r]] == 0)
				remain--;
			while (remain == 0 && cnt[B[l]] < 0) {
				cnt[B[l]]++;
				l++;
			}
			if (remain == 0 && r - l < bestr - bestl) {
				bestl = l;
				bestr = r;
			}
		}

		for (int i = 0; i < 150; i++)
			cnt[i] = 0;
		for (int i = 0; i < al; i++)
			cnt[A[i]]++;
		for (int i = bestl; i <= bestr; i++) {
			if (cnt[B[i]] > 0) {
				cnt[B[i]]--;
				ans[now++] = i;
			}
		}

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

其他

• 後來去看紀錄，好像有點少人寫 HW，希望大家多多練習，因為 lab 或是考試可能就有一部分是跟 hw 一模一樣的（這題包含了 HW4 & Lab4）
• 有些子任務可能很好拿，像是直接判 A 跟 B 有沒有一樣的子任務，這部分我在上一題的題解中有提到，希望大家都有看到 🥲
• 有疑問也可以在 Discord 群組中提出，我看到就會回答