2026 S1¶

2071. 你可以安排的最多任务数目¶

• Score: 2648

• Quality: 0

• Date: 2026/01/07

• Comment:

  因為寫的是雙序列貪心的題單，所以思路一直卡在如何將兩個序列配對。

  這題是二分答案，主要的貪心想法是可以使用最小的 k 個去配對最大的 k 個。若是有需要使用操作的部分則儘可能的讓該元素去配對比較大的元素，因此使用 deque 把可以配對的元素加進佇列中，貪心的部分是這題的另一個難點。

2673. 使二叉树所有路径值相等的最小代价¶

• Score: 1917

• Quality: 8

• Date: 2026/01/22

• Comment:

  這題我用換根想法去做，但是這題若可以緊抓其核心想法，可以有更好的寫法。

  核心的想法是對於兄弟節點(相同父節點的葉子節點)由根節點至其父節點的路徑和都是相同的，唯一不同的地方是兄弟節點的部分，若是兄弟節點為 x, y， 且 \(x \le y\)，則可以對答案作出貢獻 y - x。這個結論沒有那麼直觀，因為會考慮到必須調整至最大路徑和，但是我們在由下往上的過程中會不斷的維護使兄弟節點一致的性質，可以確保最終獲得路徑和相同的性質。

1488. 避免洪水泛滥¶

• Score: 1974

• Quality: 8

• Date: 2026/01/23

• Comment:

  這題之前做過，但是這次寫還是錯誤很多，一開始想到的解法是反悔貪心的想法，但是錯在 [0, 1, 1] 這種例子上，我們必須在相同的基礎上加上範圍的選取，以解決這種 [2,0,1,0,1,2] 例子。

  因此直覺的寫法是使用 set 的 lower_bound 選擇最靠近上次下雨時間的下標。

  但是這題還有更快的作法是使用 UF。因為我們需要的操作是"找到上次下雨時間最靠近的晴天進行抽水"，所以需要一種資料結構可以快速的指到最近的晴天並且跳過中間的雨天 -> 快速跳過元素 -> Union and Find。

  把每次雨天都指到下一天，那最後會停在最近的晴天，那下次遍歷到的時候就可以快速地拿到晴天的時間，如果最後指到的時間是當前時間，表示從上次下雨至當前時間都沒有晴天可以抽水，直接回傳不合法。

  這是把 UF 當作陣列使用的應用，題目需求的操作是能夠快速地跳過無用元素。

3007. 价值和小于等于 K 的最大数字¶

• Score: 2250

• Quality: 0

• Date: 2026/01/27

• Comment:

  一開始有想到方向但是沒有信心寫下去，這題有兩種寫法，一種是二分+數位DP，另一種是試填法。

  試填法是經典套路先假定 i-th 填 1 ，計算產生的貢獻，如過 cost <= k 那就減去 cost 把這位設為 1，最後要小心的是得到的答案要減 1，因為所求是至多 k。也因為不確定是否能夠直接減 1 所以沒有信心寫。

  計算貢獻的方式為，假設目前為 i-th，那左邊符合題目要求且為 1 的貢獻為 \(pre_1 \times 2^i\)。而一旦 i-th 設為 1 ，那 i-th 為 0 的部分則要計算 \([0, 2^i - 1]\) 與前綴產生的貢獻。這部分是計算右邊 \([0, 2^i - 1]\) 的貢獻，此時貢獻為 \(\lfloor \frac{i}{x} \rfloor \times 2^{i - 1}\)。可以看成每 x 位可以產生的貢獻為 \(2^{i - 1}\) ，因為對於 x 位之外的位置只有 0, 1 兩種可能，又因總共只有 \(\lfloor \frac{i}{x} \rfloor\) 個位置。最後得到 \(cnt = pre_1 \times 2^i + \lfloor \frac{i}{x} \rfloor \times 2^{i - 1}\)。

2749. 得到整数零需要执行的最少操作数¶

• Score: 2132

• Quality: 0

• Date: 2026/02/12

• Comment:

  這題求 \(num1 = (2^{i_0} + 2^{i_1} + 2^{i_2} ... + 2^{i_k}) + k \times num2\)，可以將式子化為 \(num1 - k \times num2 = x\)。也就是我們可以將 \(x\) 拆分成 k 個二進制表示，很顯然的是 \(popcunt(x) \le k\)，因為對 \(2^i\) 進行拆分只會使結果增加，所以 k 的下界為 \(popcunt(x)\) ，而 k 的上界為 \(x\) 個 \(2^0 = 1\)，可以得到不等式:

  \[popcunt(x) \le k \le x\]

  接著要確認 k 的上限最多為多少，可以知道 \(-10^9 \le num2\)，且 \(k \in [0, 60]\)，所以 \(x\) 最大為 \(10^9 - 60 \times (-10^9) = 61 \times 10^9\)，而 \(\log{(61 \times 10^9)} < 36\)，也就是說 \(popcount(x) \le 36\) ，由於 \(popcunt(x)\) 不會超過 x 的二進制長度，因此 k 一定有解，且 \(k \le 36\)。

2910. 合法分组的最少组数¶

• Score: 2132

• Quality: 0

• Date: 2026/02/15

• Comment:

  由題意可以知道這題關注的是不同元素的頻率，此外可以發現每組的個數會受限於最頻率最少的元素，因為若是分配的每組個數超過最少的頻率的話會顯然地無法進行分組。

  假設有一組 \(freq[x] = 32\) 可以如何分組? 若是 10 個一組，會有 \(10, 10, 10, 2\) ，多出來的 2 可以分給另外兩組，剛好差一個。若是 \(freq[x] = 34\)，會有 \(10, 10, 10, 4\) 多出來 4 無法分給另外三組。

  可以知道要能夠分組必須滿足不等式，設每組 k 個:

  \[\lfloor \frac{freq[x]}{k} \rfloor \ge freq[x] \pmod k\]

  可以得到分組:

  \[\lceil \frac{freq[x]}{k + 1} \rceil\]

3515. 带权树中的最短路径¶

• Score: 2312

• Quality: 8

• Date: 2026/02/20

• Comment:

  這題的核心思想是如何處理子樹上的區間修改，利用 DFS 時間戳可以將子樹轉換成陣列區間，透過前綴和 + 差分 + BIT 可以維護修改子樹的操作。

  這題要注意的地方是我一開始的作法是維護一個前綴和陣列和差分 BIT，但是這樣做的常數會比較大，需要多花操作。

  可以直接維護差分 BIT 就好，相當於在 BIT 上維護前綴和。

2234. 花园的最大总美丽值¶

• Score: 2312

• Quality: 3

• Date: 2026/02/21

• Comment:

  這題算是有抓到題目的核心思想，但是實作很麻煩，問題是卡在如何將想法實作出來，因為其中有好幾個狀況需要考慮所以在思考的時候沒辦法想清楚。

  第一個是假設可以全部種滿花，第二個是 partial > full 造成的影響，這導致討論起來有點複雜。主要的想法是雙指針，右邊指向可以種滿的位置，左邊則是剩下的花可以使得最小的花最大為多少，透過不斷的將右指針向右移動，找出最大的答案。

  對於 \(x \ge target\) 的元素已經符合題目所需所以必須先排除。

  1. 首先考慮若是全部都不需要種花的情況，此時 \(\sum{flowers[i]} \ge n \times target\) 。最大值為: $\(n \times full\)$

  2. 接著考慮利用額外操作 \(ops\) 使得全部花園都可以合法的情況，此時需要的操作為 \(\sum{target - flowers'[i]} \le ops\)，\(flowers'[i]\) 為 \(flowers[i] < target\) 的元素。可以得到不等式 $\(left = ops - (\sum{target - flowers'[i]}) \ge 0\)$ 此時剩餘的花朵 \(left\) 若是大於等於 0 的話則表示可以透過操作將所有的花園種到 target。 要注意的是此時最大值會有兩種可能 $\(max(n \times full, (n - 1) \times full + (target-1) \times partial)\)$

  3. 上面 1, 2 兩種情況可以合併成 \(left - n \times target\) 再遍歷一次陣列，遍歷過程中做 \(left += min(x, target)\) ，最後會得到 \(left = ops - (\sum{target - flowers'[i]})\)

  4. 討論完種滿的情況，接著考慮會剩下沒種滿的情況，此時我們要考慮如何最大化花得最少數量。 目標是最大會最小值，由小至大想像我們往前綴中倒水，水會不斷慢慢地從最低的位置往前漫上來。假設我們剩下 \(left\) 朵花可以種到前綴 [0, j - 1] 中。那麼我們會共有 \(avg \cdot j\) 朵花，有不等式:$\(avg \cdot j \le left + \sum_{k = 0}^{k=j-1}{flowers'[k]}\)$

     因此可以知道最大值 \(avg\): $\(\lfloor \frac{left + \sum_{k = 0}^{k=j-1}{flowers'[k]}}{j} \rfloor\)$

  5. 細節

     把超過 target 的 flowers[i] 改成 target。這一來可以簡化雙指針的計算，二來可以加快排序的效率，尤其是當很多 flowers[i] 都超過 target 的情況。

3273. 对 Bob 造成的最少伤害¶

• Score: 2013

• Quality: 3

• Date: 2026/02/21

• Comment:

  • 這題的關鍵是注意到兩個敵人誰先誰後，從特殊推廣至一般

  假設有兩個敵人 \(a, b\) 分別可以造成傷害 \(D_a, D_b\) 和生命值 \(H_a, H_b\)，而消滅一個敵人要花的時間為 \(t_i = \lceil \frac{H_i}{power} \rceil\)，先消滅 a 的情況所受到的傷害為 \(D_a t_a + D_b(t_a + t_b)\)，而先消滅 b 的情況所受到的傷害為 \(D_b t_b + D_a(t_a + t_b)\)，由小至大排序的話會有下列不等式:

  \[D_a t_a + D_b(t_a + t_b) < D_b t_b + D_a(t_a + t_b)\]

  展開化簡:

  \[D_b t_a < D_a t_b \]

  利用這個不等式排序後可以由小至大遍歷得到答案。

  ---

  我一開始的想法會是從貢獻著手，假設最優的順序為 \(\pi_1, \pi_2, \pi_3 ... \pi_n\)，展開總合為

  \[d[\pi_1](t[\pi_1]) + d[\pi_2](t[\pi_1] + t[\pi_2]) + ... \]

  所求為:

  \[min{\sum_{i \le j} d[\pi_i]t[\pi_j]}\]

  其中當 \(i = j\) 時，與 \(\pi\) 無關因此:

  \[min{\sum_{i < j} d[\pi_i]t[\pi_j]}\]
  • 鄰項交換法:

  觀察其中兩個元素下標為 i, j，且 i < j。考慮兩個元素位置交換後的變化

  • 原始順序: \(d[i] \cdot t[j]\)

  • 交換順序: \(d[j] \cdot t[i]\)

  交換這兩個相鄰元素，並不會影響到它們之前的元素對，也不會影響到它們之後的元素對，更不會影響到它們與其他位置元素組成的 \(d \cdot t\) 項。

  若我們希望原始順序優於交換後的順序（即原始總和更小），則需滿足：$\(d[i] t[j] < d[j] t[i]\)$

  • 直觀理解:

    • 這個公式可以想像成一種「代價」的累積：\(t[j]\) 可以看作是第 \(j\) 個任務的「權重」或「重要度」。

    • \(d[i]\) 可以看作是第 \(i\) 個任務產生的「延遲係數」。

  如果你有一個很大的 \(d[i]\)，它會與後面所有的 \(t[j]\) 相乘。為了不讓總和暴增，我們應該儘量讓這個「放大器」\(d[i]\) 後面跟著的 \(t[j]\) 越少越好，所以 \(d[i]\) 應該往後排。

  相反地，如果你有一個很大的 \(t[j]\)，它會被前面所有的 \(d[i]\) 累加。為了保護它，我們應該讓它往前排，減少被前面 \(d[i]\) 乘到的機會。

2412. 完成所有交易的初始最少钱数¶

• Score: 2092

• Quality: 0

• Date: 2026/03/04

• Comment:

  原本想用交換論證的方式比較兩個先後順序的貢獻，但是沒有做出來，沒有抓到這題的核心想法。這題的重點在 transactions \(t_i\) 只有在每次都做虧錢交易時，會使得你需要投入的初始資金不斷增加。也就是對於 \(t_i = \{cost_i, cash_i\}\) ，當 \(cost_i > cash_i\) 必須比 \(cost_i \le cash_i\) 先做才能虧得更多錢，我原本的想法就是缺少了這一步驟所以沒有做出來。

  接著就是比較怎樣可以得到多的貢獻， 排序中比較:

  \[max(cost_b - cash_a, 0) + cost_a > max(cost_a - cash_b, 0) + cost_b\]

  這個方法的複雜度為 \(O(n\log{n})\)，瓶頸在排序上。

  • 由上面的想法可以得到一個結論，那就是必須先做完所有的虧錢交易，才能得到最大的初始資金，因此要先做完所有 \(cost_i > cash_i\) 的交易，虧的錢為 \(\sum_{cost_i > cash_i}{cost_i - cash_i}\)。

  對於賺錢的交易:

  1. 假設是(虧錢後)第一筆交易，為了完成這筆交易會需要至少 cost，此時的初始資金為 \(initial - totalLose \ge cost\)，移項後 \(initial \ge totalLose + cost\)

  2. 假設是虧錢的最後一筆交易 \(initial - (totalLose - (cost - cash)) \ge cost\)，移項後 \(initial \ge totalLose + cash\)

  可以將所有情況取最大值，以保證任何順序下都可以完成交易:

  • 假設虧錢交易 \(cost_i > cash_i\)，\(totalLose\) 要加上的是兩者的較小值 \(cash_i\)

  • 假設賺錢交易 \(cost_i \le cash_i\)，\(totalLose\) 要加上的是兩者的較小值 \(cost_i\)

  因此可以得到初始資金為 \(totalLose + max(min(cost_i, cash_i))\)

3664. 两个字母卡牌游戏¶

• Score: 2158

• Quality: 0

• Date: 2026/03/09

• Comment:

  這題卡在最後分配萬用牌 xx 上，萬用牌可以分配給兩組，但是卡在沒辦法貪心的最優分配，分配問題應該要注意到能否"枚舉分配"，若是能想到枚舉分配個數很快就解決。

3495. 使数组元素都变为零的最少操作次数¶

• Score: 2206

• Quality: 0

• Date: 2026/03/10

• link

• Comment:

  這題要計算閉區間 \([l, r]\) 內的整數，每兩個一對做整數除法 \(\lfloor \frac{x}{4} \rfloor\)，總共要做幾次使得區間內整數為 0。

  可以很直覺的知道若是 \(S_{l,r} = \sum_{l}^{r} D(x)\)，答案為 \(\lceil \frac{S_{l, r}}{2} \rceil\)，\(D(x)\) 為將整數 \(x\) 做 \(\lfloor \frac{x}{4} \rfloor\) 要花多少次可以使得 \(x\) 為 0。

  計算 \(D(x)\) 的時間複雜度為 \(\log_4{x}\)，本題會有 \(q\) 個詢問，每個詢問要回答範圍為 \([l,r]\)，暴力的複雜度為 \(O(qL\log_4{x})\)，\(L = r - l + 1\)。\(q\) 跟 \(L\) 的範圍分別是 \(10^5\) 和 \(10^9\)。

  由上面可以知道要是能夠快速地計算區間 \([l,r]\) 的 \(S_{l,r}\) ，就有辦法解決這題，。

  對於區間計算，或是區間計數問題，經典套路就是前綴和的思想，設 \(cnt(n)\) 為要做幾次操作可以使 \([1,n]\) 的整數為 0: $\(S_{l,r} = \sum_{l}^{r} D(x) = \sum_{1}^{r} D(x) - \sum_{1}^{l - 1} D(x)= cnt(r) - cnt(l - 1)\)$

  觀察 \(D(x)\) 的分布，\(D(1) = 1, D(2) = 1, D(3) = 1, D(4) = 2, .... D(16) = 3\):

  \[D(x) = 1, 1, 1, 2, 2, ... 2, 3, 3 ... ，\text{for x} \in [1, n]\]

  由上面可以觀察到一個非嚴格遞增的數列，設 \(k = \lfloor \log_4{x} \rfloor\)，而 \(D(x) = k + 1\)，且:

  \[ D(x) = \left\{ \begin{array}{ll} 1, \text{ x } \in [1, 3] \\ 2, \text{ x } \in [4, 15] \\ 3, \text{ x } \in [16, 63] \\ ... \\ k + 1, \text{ x } \in [4^{k}, 4^{k + 1} - 1] \\ \end{array} \right. \]

  要得到 \(cnt(n)\) 透過枚舉 \([1, k]\) 計算 \([1, 4^{k - 1}]\) 的 \(D(x)\)，剩下部份的則是 \(n - (4^k - 1)\):

  \[cnt(n) = \sum_{j = 1}^{k} j(4^j - 4^{j - 1}) + (k + 1)(n - (4^k - 1))\]

  auto cal = [&](ll n) -> ll {
      ll res = 0;
      int i = 1;
      ll base = 0;
      for(; n >> (i * 2); i++) {
          ll base = 1LL << (i * 2);
          res += (base - (base >> 2)) * i;
      }
      base = (1 << ((i - 1) * 2)) - 1;
      return res + (n - base) * i;
  };
  

  由上面可以知道這個方法需要 \(O(\log_4{n})\) 的時間計算 \(cnt(n)\)。

  將 \(cnt(n)\) 展開可以得到:

  \[ \begin{aligned} cnt(n) &= (4^1 - 4^0) \cdot 1 + (4^2 - 4^1) \cdot 2 + ... + (4^k - 4^{k - 1}) \cdot k + (n - (4^k - 1))\cdot (k + 1)\\ &= -4^0 \cdot 1 + (4^1 - 4^1 \cdot 2) + (4^2 \cdot 2 - 4^2 \cdot 3) + ... + (4^{k - 1} \cdot (k - 1) - 4^{k - 1} \cdot k) \\ &+ 4^k \cdot k + (n - (4^k - 1))\cdot (k + 1)\\ &= -4^0 -4^1 -4^2 - ... -4^{k - 1} + 4^k \cdot k + (n - (4^k - 1))\cdot (k + 1) \\ &= -\sum_{i = 0}^{k - 1}{4^i} + 4^k \cdot k + (n - (4^k - 1))\cdot (k + 1) \\ &= - \frac{4^0(1 - 4^k)}{1 - 4} + 4^k \cdot k + (n - (4^k - 1))\cdot (k + 1) \\ &= 4^k \cdot k + (n - (4^k - 1))\cdot (k + 1) - \frac{4^k - 1}{3}\\ \end{aligned} \]

  auto cal = [&](int n) -> ll {
      if(n == 0) return 0;
      int b = bit_width((unsigned) n);
      int k = (b - 1)/ 2;
      ll base = 1 << (k * 2);
      return base * k - (base - 1) / 3 + ((n - base) + 1) * (k + 1);
  };
  

  ¶

3139. 使数组中所有元素相等的最小开销¶

• Score: 2666

• Quality: 5

• Date: 2026/03/11

• link

• Comment:

題目基本想法是要將一堆數 \(x_i\) 透過成本為 c1 的 op1 或成本為 c2 的 op2，使得最終所有的 \(x_i\) 相等。

觀察題目可以發現，顯然最終相等的數值至少會是所有元素的最大值 \(M\)。

我的思路為分類討論情況，然後取最小值:

\(S = M \times n - \sum{x_i}\)

1. 全部都使用 op1:

   \[cost = \rfloor \times c1\]

2. 使用 op2 + op1: 因為 op2 需要兩兩配對，所以需要使用相鄰貪心的思想，找到相差最大的元素進行配對:

   \[d = M - m, m = min(x_i)\]

   此時:

   \[ \begin{aligned} pairs &= min(\lfloor \frac{S}{2} \rfloor, S - d)\\ rest &= S - 2 \cdot pairs\\ cost &= pairs \cdot c2 + rest \cdot c1\\ \end{aligned} \]

3. 有可能 c1 特別的高，使得多做 op2 會比做 op1 更划算，此時的最終值 \(M' > M\)，由相鄰貪心可以知道，在這個限制下一定可以有兩兩配對:

   \[ \begin{aligned} d' &= M' - m\\ S' &= M' \times n - \sum{x_i}\\ d' &\le S' - d'\\ \end{aligned} \]

   展開後移項:

   \[ \begin{aligned} M' - m \le M' \times n &- \sum{x_i} - (M' - m)\\ \sum{x_i} - 2m &\le M' \cdot (n - 2)\\ \frac{\sum{x_i} - 2m}{n - 2} &\le M'\\ \end{aligned} \]

   將 M' 帶回 2. 計算。

4. 上面就是我自己寫時想的思路，看完答案後發現雖然基本思路都有想到，但是卡在一些細節上:

5. 對於全部都是 op1 的情況可以直接用 \(2 * c1 \le c2\) 討論，使用兩個 op1 的成本會比使用 op2 的成本還低那就不需要往下討論。

6. 情況 2 的想法沒問題，但是一個小細節是如果將計算 pairs 放到 cost 一起計算的話兩種情況要取 max ，也就是:

   \[cost = max(\lfloor \frac{S}{2} \rfloor \cdot c2 + (S \& 1) \cdot c1, (S - d) \cdot c2 + (2d - S) \cdot c1)\]

...

1. 第三種情況就是沒有處理好的部分，對於不等式:

移項後，如果要將實數化為整數此時必須上取整:

最後將 M' - 1, M', M' + 1 代入 2. 計算最小值。

2813. 子序列最大优雅度¶

• Score: 2582

• Quality: 5

• Date: 2026/03/19

• link

• Comment:

這題首先直覺的對 profit 按大至小排序，原本的想法是將前 k 元素分別 push 至兩個 stack，一個是 diff 表示第一個被選到 category 的 profit，第二個 stack same 表示前面已經選過 category 的 profit。接著由 idx = k 開始遍歷，一旦遇到已經被選的 category 那就跟 diff 的頂端比較貢獻，若是遇到尚未被選的 category 則跟 same 的頂端比貢獻，最後得到的就是答案。

這個想法已經很接近答案了，主要是我沒想清楚選擇策略，一開始選前 k 個是答案下限，不能用重複 category 的元素 x 替換得到更好得答案。當 idx >= k 的元素若是已經被選過了，那無法對答案產生更好的貢獻，此時有兩種情況:

1. 替換前面的重複元素 y，此時 \(y \ge x\)，此時不同元素數量不會改變，因此無法產生更好的答案。

2. 替換前面的不重複元素 y，此時 \(y \ge x\)，不同元素數量會因為交換變少，使得答案更差。

結合上面兩種情況，不能使用重複元素做交換。

用不同元素 x 進行交換，則可以有:

1. 替換前面的重複元素 y，此時 \(y \ge x\)，不同元素數量會上升，有機會在之後得到更好的答案。

2. 替換前面的不重複元素 y，此時 \(y \ge x\)，此時不同元素數量不會改變，無法產生更好的答案。

總結上面四種情況得出結論，只有在當前元素 x 為不重複元素，且被替換元素 y 為重複元素時，才有機會構造出比原本更好的答案。

計算答案的時候由 idx = k 開始遍歷，只使用不重複元素替換前面被選的重複元素，要注意的是每次替換後都要跟答案取 max ，因為最大值可能在這個過程中出現。

3049. 标记所有下标的最早秒数 II¶

• Score: 3111

• Quality: 0

• Date: 2026/03/20

• link

• Comment:

題目提供三種操作:

op1. 將 nums[i] 減一

op2. 將 nums[changeIndices[s]] 設為 0

op3. 將 nums[i] = 0 標記

一開始觀察到幾個性質:

1. 對於 nums[i] > 1，盡可能使用 op2 ，對同一個 i 使用 op1 後再使用 op2 會浪費。

2. 對於 nums[i] <= 1，使用 op2 和 op1 的花費是一樣的，因此盡量使用 op1。

3. op3 要盡量靠後

4. 要先將 nums[i] 歸 0 不然無法操作 op3

前三個性質沒問題，真的卡住的地方是第四個性質，最後沒寫出來。

• Solution:

這題有一個重要的性質一開始沒想到。

• 單調性: 合法答案的值域在 \([1, m]\) 之間，在值域範圍內若是答案秒數越多越有機會符合題目要求。

接著思考 op1, op2 的先後順序? 雖然上面觀察到了 1 但是有點問題，可以使用 op2 不代表不能使用 op1 完成要求 \(\rightarrow\) 但是每個 i 只會使用一種操作 op1 or op2

對於上面觀察到的 4. 可以知道一定是先做 op1/op2 才能做 op3，但是這樣會有一個問題，使用 op1/op2 時後面不一定有時間做 op3。

\(\rightarrow\) 所以必須先確定 op3 的位子才去決定是否使用 op2 / op1

\(\rightarrow\) 另一個重點，使用二分答案的 check 函數是判定問題，對於順序與逆序不影響判定。

\(\rightarrow\) 使用倒序遍歷

倒序遍歷:

• 不能做 op2:

  1. 那就將 free += 1 表示可以用來做 op1 or op3

• 可以做 op2:

  • 做 op2，消耗一個 free 執行 op3

  • 不做 op2 的情況:

    1. nums[i] = 0
    2. nums[i] = 1
    3. free = 0 無法做 op3 \(\rightarrow\) 思考是否這個 i 只能使用 op1 完成? \(\rightarrow\) 將之前使用過 free 的人替換改成自己，被替換的人使用 op1 \(\rightarrow\) 反悔貪心

• 結論: 這題有三個重要的性質要觀察到才能順利解決:

  1. 單調性
  2. 必須使用倒序遍歷，使用二分答案的 check 函數是判定問題，對於順序與逆序不影響判定。
  3. 反悔貪心的思考過程

• \(O(m\log{m})\) 的 方法 ，可以看懂方法，但是有點像在湊答案沒有辦法理解透徹。

1520. 最多的不重叠子字符串¶

• Score: 2363

• Quality: 0

• Date: 2026/03/23

• link

• Comment:

這題主要卡的點會是 ababa 這種例子，不知道怎麼處理比較好，在這個例子中要建立的關係是 \(a \rightarrow b\), \(b \rightarrow a\) 因為 b 的區間中也有 a，我原本想用兩端點判斷是否有包含或交叉，但是對於 ababa 這種情況會漏掉 b->a 這個部分。

如果區間內有其他字母就建一條邊，因此若是有這種 abcba 這種例子圖會長這樣 \(a \rightarrow b \rightarrow c\)，會有三個區間 \([0, 4], [1, 3], [2, 2]\) 正是我們需要的區間。

因此我們需要一個方式快速判斷某個字母是否有包含在這個區間中:

• 先把每個字母的位置分類

• 使用二分判斷是否出現位置包含在區間中