HackMD
14449 - Big orange cat's puzzle II
希望大家不要討厭大橘 QQ
為了跟程式碼比較接近，接下來的敘述會以 0-based 為主
題意
找到一個最小的合法區間
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
這個子任務你需要找到一個最好的
接著我們再複習一次 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
- 首先紀錄
- 最後就是判斷有沒有解並輸出，相信這個不需要額外說明
- 這個解的時間複雜度會是
#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 的太慢，那你就會得到這個測資
這裡提供幾個加速方式：
- 如果目前的
r - l > ansr - ansl，那就不需要再枚舉一次 - 不要在枚舉的過程中構造答案，先得出最好的 l, r 再說
出題者在出這題的時候其實不知道有沒有辦法拿到 5/6，只是假設可能有人 Subtask5 沒寫好還是有一點分數
Subtask5
這裡用到一個叫做雙指針的技巧，假設有一個 function valid(l, r)，會回傳那個區間是不是合法的，那麼 l, r 對於 valid 將會有單調性（單調性應該在微積分中學到過了），也就是對於一個固定的 l，r 越大就越有可能是合法的；對於固定的 r，l 越大越不可能是合法的，我們可以好好利用這個性質
- 首先固定 l = 0，找到第一個使其合法的 r，這是第一組答案
- 將 l 往右一格，這時會有兩種情況：
- 還是合法的：那你得到了一個更好的答案
- 變不合法：那就再把 r 往前推直到合法
- 不斷重複此過程，並在過程中記錄最好的區間，就會得到答案，時間複雜度
#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 群組中提出，我看到就會回答
