Try   HackMD

14449 - Big orange cat's puzzle II

希望大家不要討厭大橘 QQ

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

題意

找到一個最小的合法區間

[l,r]，然後輸出從
Bl∼Br 拿出一些字元重新排列後，有辦法組出
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
  • 最後就是判斷有沒有解並輸出，相信這個不需要額外說明
  • 這個解的時間複雜度會是
    O(n×∣S∣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. 不斷重複此過程，並在過程中記錄最好的區間，就會得到答案，時間複雜度
    O(n×n)    ，約等於
    5×106    ，能夠 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 群組中提出，我看到就會回答
Last changed by 
 
Koying
0
253

Read more

HW2 陳克盈 112062205

依照 iters 參數分成兩種情況：

Nov 1, 2024
HW1 陳克盈 112062205

首先是輸入的部分，因為兩個節點在交換資料並 merge 的時候，在長度一樣的情況下會比較好實作，因此首先將每個節點的資料都

Nov 1, 2024
14444 - Big orange cat's puzzle

重點：如何判斷 + 構造解，判斷你們已經在 HW4 寫過了，那怎麼構造解呢？有一個 hint 是，大橘非常懶惰，想要拿最前面的，因此我們可以直接從左邊開始，每遇到一個需要的字母就把它加進答案，最後如果我們收集到了跟 A_i 一樣多的

Oct 8, 2024
競程常見數學符號

$\mathcal{O}()$：用來描述一個函數的「上界」，在競程中用來表示時間複雜度 $\displaystyle\sum_{i = 1}^{n}{i}$：求和符號（此例子表示 $1 \sim n$ 的和） $\displaystyle\prod_{i = 1}^{n}{i}$：連乘符號，運作原理與求和符號相似，不過把加改成乘 $\lceil \frac{a}{b} \rceil$：$\frac{a}{b}$ 取上高斯（小數點無條件進位） $\lfloor \frac{a}{b} \rfloor$：$\frac{a}{b}$ 取下高斯（小數點無條件捨去） $a \bmod b$：$a$ 除以 $b$ 的餘數 $a \equiv b \pmod{P}$：$a$ 與 $b$ 在 $\bmod P$ 的環境下同餘 $a \mid b$：$a$ 整除 $b$，$a \equiv 0 \pmod{b}$ $\gcd(a, b)$：$a, b$ 的最大公因數 $\text{lcm}(a, b)$：$a, b$ 的最小公倍數

Jan 26, 2023
Read more from Koying
Published on HackMD