2025 S4¶

Weekly contest #470¶

Q2. Longest Subsequence With Non-Zero Bitwise XOR

這題很快想到至少某一位bit的數量必須是奇數可以xor全部，否則剔除一個數做xor，第一發wa因為沒考慮到有0的情況，第二發wa是沒考慮到全為0的情況

• 要確認題目的邊界

Q3. Remove K-Balanced Substrings

• tag: stack

讀完題馬上想到要用stack，但是在狀態設計上沒有考慮清楚，在k = 2 的時候 若是長這樣 (() (())) ，會先消除兩個 () 然後剩下一個 ) 可以跟左邊留下來的部分再次組成 (()) 做消除。

• 腦袋不清楚，沒睡飽
• 測資想的不夠全面
• 或許可以考慮寫個對拍?

Q4. Count No-Zero Pairs That Sum to

• tag: digit dp

看完題目馬上想到數位DP，但是只考慮了從高位至低位，(a,b)中枚舉a的時候如果含有0或是不含0的情況，但是沒辦法處理另外一半含有0的情況 因為若是 total - (a有0的情況) ，則只會計算 (a有0的情況, b), (a有0的情況, b有0的情況) 這種情況，沒辦法處理 (a, b有0的情況)。

• 想到這邊或許應該馬上放棄思考這條路徑?

• Solution:

  真正的解法應該使用從低位到高位。

  • a + b = n 從基本的加法開始觀察

    1. 設當前數位為 d = s[i]。如果低位 (i + 1) 發生借位 -> d - 1
    2. d 可以像高位借位 -> d + 10
    3. 如果 d = 0 ， 如果此時低位借位了，必須同時向高位借位 -> d = -1, d + 10 = 9

  • 拆分方案數:

    • \(d = a + b\) 且 \(a,b \in [1, 9]\)

    • 若是不借位則， (a, b) = (1, d - 1), (2, d - 2) ... ..., (d - 1, 1)

      \[ cnt((a, b)) = \left\{ \begin{array}{ll} d - 1, & \text{for } d >= 2\\ 0, & \text{for } d < 2 \end{array} \right. \]

    • 若是向高位借一位，則要算 d + 10 = a + b的方案數，ex. 14 = (5, 9), (6, 8), (7, 7), (8, 6), (9, 4)， 則會發現 \((a, b) = (d + 1, d + 10 - (d + 1)), (d + 2, d + 10 - (d + 2)) ... = (d + x, 10 - x)\) ，一共有 9 - d(a < d 有多少個) 個也就是 19 - (d + 10) 個

  • 前導 0:

    • d = a + b 時，至少有一位是 0

    • 若 a = 0，則更高位的 a' 必須也是 0 -> 前導 0

    • 此時 b = d

    • 分類討論:

      • 若 d != 0:
        • b = d 只有一種，若是 d < 0 則要借位
        • 剛開始填前導 0 時，可以利用對稱性把方案數 * 2
      • 若 d = 0， 則 b = d = 0:
        • 若是 i > 0，因為沒有向高位借位，b的高位至少一個非0數字b，前面不能都是0 -> 無解
        • 否則 i=0，兩個數的最高位都是 0，這是合法的。例如 100 = 49+51，49 和 51 的百位都是前導零。

• code

• 補充題目:

  • F. Jee, You See?

Weekly contest #471¶

Q3. Longest Balanced Substring II

• Thought in the contest:

  最一開始的時候想到了前綴和，滑動窗口這幾個想法。

  • 滑動窗口的部分沒有好的方式限制窗口

  • 前綴和的方式後來有想到 01010 這種方式若是可以讓前綴和為 0 就可以找到頻率一樣的區間了。對於 (a, b), (a, c), (b, c) 都可以找，但是卡在了 (a, b, c) 這上面沒想到如何解決 a + b + c = 0 的情況。

• Solution:

  • 對於某個子字串如果要符合要求那必須，\(cntA_{[l,r]} = cntB_{[l,r]} = cntC_{[l,r]}\)。接著拆分成
  \[ \left\{ \begin{array}{ll} cntA_{[l,r]} = cntB_{[l,r]}\\ cntB_{[l,r]} = cntC_{[l,r]} \end{array} \right. \]

  移項後

  \[ \left\{ \begin{array}{ll} cntA_{[l,r]} - cntB_{[l,r]} = 0\\ cntB_{[l,r]} - cntC_{[l,r]} = 0 \end{array} \right. \]

  • 若是子字串的中的 \((cntA_{[l,r]} - cntB_{[l,r]}, cntB_{[l,r]} - cntC_{[l,r]})\) 相等表示這段子區間內的頻率相同。

  • 這裡有個容易錯的地方是前綴和會有負數，用 long long 似乎因為負數會導致hash錯，所以要加 n 使得 hash 非負數

Q4. Sum of Perfect Square Ancestors

• tag: 平方剩餘和預處理

• Thought in the contest:

  這題困難點在如何提取出平方剩餘和，也就是奇數次方的乘積。

• Solution:

  要用類似埃式篩的方式計算

• 類似題目:

  • 完全平方数的祖先个数总和

  • 完全子集的最大元素和

Weekly contest #472¶

Q1. Smallest Missing Multiple of K

因為粗心 wa 一發

• 沒利用極值測試

Q2. Longest Balanced Subarray I

• 要寫暴力的話，就寫單純的方法就好，不要花力氣去想複雜的方法
• 速度太慢

Q3. Lexicographically Smallest Permutation Greater Than Target

這題有抓到問題的本質，字典序最小的話就要沿著目標字串構造，一但有無法構造的部分就是從那個位置開始構造。

• 少想一個邊界值 wa 了一發，順序過去找到關鍵位置後要往回走，類似反悔貪心。

Q4. Longest Balanced Subarray II

這題跟上禮拜的很類似，都是利用 +1/-1 前綴和為 0 的性質找個數相等的子區間，但是對於重複元素的部分無法考慮清楚，比賽的時候卡在這部分。

講解

有想到對於重複元素應該使得其貢獻為 0, 但是我使用的想法是對於第一個出現的元素 +1 or -1 這會導致對於前綴和無法得到對應的區間 -> 問題所在

• 雖然有觀察到對於重複元素如果可以選，那應該越多越好 -> 想到這個應該要想到哪一個元素當第一個元素比較適合?
• 在前綴和的框架下我們會不斷的枚舉右端點，此時對於子區間會造成貢獻的是第一個出現的元素，之後出現的重複元素對於前綴和應當都是 0。
• 接著就會帶到，如果向右枚舉出現一個重複元素，那必須把這個元素當成第一個元素，左邊的其他元素的貢獻應該改為 0 -> 要做區間修改的操作 -> 線段樹/BIT
• 接著我們想找區間合為 0 的前綴和位置 -> 線段樹二分 -> 用 {min, max} 表達區間內的最大最小值(因為前綴和值的變化是整數連續的) -> lazy 線段樹

題目: * HH 的项链

Weekly contest #473¶

Q3. Stable Subarrays With Equal Boundary and Interior Sum

用 pair 的方式要看一下思路，這樣不用二重 hash。

tutorial

Q4. Count Distinct Subarrays Divisible by K in Sorted Array

一開始想到利用統計 [0, k - 1] 結尾的個數方式計算 subarray。

• 想到一半的時候已經想到可能會 TLE ，因為 \(O(nk)\)，但還是執意去做因為猜可能 k 循環次數會比較少，應該馬上放棄這個想法才對

• 另外調整太久才得到 TLE 的答案，沒想清楚

tutorial

Weekly contest #474¶

Q4. Lexicographically Smallest Palindromic Permutation Greater Than Target

• Thought in the contest:

比賽的時候沒有找到正確的思路，因為回文的限制導致沒看清題目的本質。

比賽的時候想的思路是先沿著target利用 lower_bound 在 s 中找答案，如果沒辦法產生一個合法解那就往回撤銷直到可以構造出一個 >= target 的解。

這個想法跟答案其實很接近，問題出在一開始使用 lower_bound 找 >= target 的可行解，但是 lower_bound 不保證最後得到的答案會是最小的。

• Solution:

這題跟 3720. 大于目标字符串的最小字典序排列 的思路是一樣的。

先想辦法盡可能沿著 target 構造一個初步可行解，直到沒辦法繼續構造為止，此時產生出來的字串會是最小的，接著我們必須產生出剛好大於等於 target 的合法解，如果剩下來的字母無法構造的話，那就往回撤銷之前已經填好的字母嘗試構造，直到有合法解為止。

題解

Weekly contest #475¶

Q4. Maximize Cyclic Partition Score

• Thought in the contest:

  比賽的時候想到的是從無環的情況出發做約束劃分型dp(O(nk))，但是當考慮到環後會因為處理環的情況導致複雜度爆炸。

• Solution:

  對於沒有環形的約束下，整體的題目框架是股票交易模型 3573. 买卖股票的最佳时机 V，其中子陣列中只有最大最小值是有意義的其他不關心。

  • 换句话说，3573 题可以更抽象地描述为，划分成至多 k 段子数组的极差之和的最大值。

  可以寫成:

  \[\begin{array}{ll} max\sum_{i = 1}^{k} = |a_{r_i} - a_{l_i}| \end{array}\]

  用max轉換成:

  \[\begin{array}{ll} \sum_{i = 1}^{k} = max(a_{r_i} - a_{l_i}, a_{l_i} - a_{r_i}) \end{array}\]

  • 環型陣列的題目突破點應該是如何處理環形陣列，也就是說如何把環形攤平成普通陣列做計算。

    這題攤平成普通陣列的方法是考量到最大元素必定會包含在某一子陣列中，以及我們只考量子陣列中的最大最小值，所以我們可以貪心的將最大值截斷將其當成陣列的開頭或是結尾，把環形陣列攤平。

  code

Weekly contest #476¶

Q4. Count Stable Subarrays

• Thought in the contest:

  比賽的時候被逆序對給迷惑住了，一直思考如何有效率的計算全部的順序 subarray，並且最後考慮實作莫隊，結果在分塊交界的邏輯卡住了。

• Solution:

  比賽結束後看到把每個順序 subarray 做分塊，馬上就完成了，基本上也算是個套路題，透過將每個順序 subarray 分組 + 前綴和可以有效率的算出區間內的答案。

  其中要注意的是題解的套路，對於一個順序的 subarray，可以透過累加當前長度的方式得到這個區間的解，而我們需要分別將左右兩邊單獨計算和利用前綴和直接計算中間部分。

  code

Weekly contest #477¶

Q3. Concatenate Non-Zero Digits and Multiply by Sum II

這題因為不熟悉 string hash 所以搞了很久，不過可以透過這題來複習 string hash。

link

Q4. Number of Effective Subsequences

• Thought in the contest:

  比賽得時候有想到是不是 SOS DP，但是想的不夠深入，此外時間不夠所以沒寫出來，另外比賽的時候把 or 看成 xor。

• Solution:

  題目要求計算全部元素 or 後 < x 的子序列個數，但是直接統計 < x 是相對麻煩的。所以反向計算: or(all elements) - >= x 的子序列個數。 然而又因為 or(all elements) 不會超過 x 所以 -> or(all elements) - (=x 的子序列個數)。

  接著要計算子序列恰好等於 x 是困難的 -> 至多/少 x 比較好算(這裡用子集的方式表示，至多在這裡指的是 \(\in\) )

  用容斥原理計算: ex. \(or = 11_2\) 的方案數為 \(2^{f{11}} - 2^{f{10}} - 2^{f{01}} + 2^{f{00}}\)

  接著要計算在 nums 中有多少個數(元素個數)是 S 的子集 -> SOS DP

Weekly contest #478¶

Q1. Count Elements With at Least K Greater Values

因為沒理解題意導致 wa 了五次，下次 w 兩次後要回去確認題意。

Q4. Minimum Operations to Equalize Subarrays

• Thought in the contest:

  比賽中對於判斷區間是否可以操作，想到的是計算模數的前綴和，判斷是否為區間長度的倍數。這個方法有一個問題，當某幾個元素是 0 的情況會導致加總後的和儘管是長度的倍數，也有可能是其他模數的和。

  另外一部分是要求區間的中位數，因為沒想到如何求區間中位數而卡住，雖然不會可持久化線段樹，但還有對頂堆的方式快速求中位數，這是應該要想到的。

• Solution:

  對於判斷區間是否可以操作，只要記錄下連續相同模數的區間就好，容易就連想到可以用二分或是 DP

  另一部分求區間中位數要使用的是可持久化線段樹。

  解說

Weekly contest #479¶

Q1. Sort Integers by Binary Reflection

這題錯在低級錯誤，想寫比較好看的寫法但是，忘記 arr 內我用的就是 idx 然後還再 轉換一次 nums[arr[a]] 導致排序錯誤，debug花太久時間。

Q2. Largest Prime from Consecutive Prime Sum

沒仔細讀題，要找的是從 2 開始累加，且得到的"和仍然是質數"。

Q3. Total Score of Dungeon Runs

• Thought in the contest:

這題問題出在一直想要快速地求出 減去 damgage[i] 後 >= reqs[i] 的個數。但是這個是很難求的，因為在改變起點後，減去 damage[i] 後的 位置每個數的變化都不一樣，同時要求出 >= reqs[i] 的個數是很困難的。

• 思考的密度，靈活度不夠，沒有快速的判斷出由 damage 出發有問題。

• Solution:

前面這個想法是基於 damage 的方向出發，可以知道這個方向會因為要快速求出減去 damage[i] 後 >= reqs[i] 是比較困難沒什麼想法的。

• 比賽中有幾個變數就應該要嘗試從不同的變數的角度，值域思考

雖然一開始有想到關於貢獻的部分，但是 damage[i] 和 reqs[i] 兩個相減後看起來沒什麼關聯所以就沒有往下想。

有另一種貢獻是看對於答案有幾個起點可以滿足。

比賽的最後有想到使用二分找前綴和最遠可以滿足的位置。

Q4. Maximum Subgraph Score in a Tree

比賽的時候猜測這題比Q3簡單，確實也是，雖然沒有馬上反應到換根，但是用貪心的想法去做應該有機會做出來。

• Solution:

  容易卡住的點在如何計算當前節點另一邊的 score，這裡要注意的是對於答案 ans[x] 表示的是必須包含 x 的最佳 subgraph，所以要往下計算 child y 時要從當前 ans[x] 減去 max(score[y],0) 來得到對於 child y 的另一邊的 score。

Weekly contest #480¶

Q3. Minimum Moves to Balance Circular Array

這題漏看條件，導致完全卡死，漏看"至多只有一個負數"。

• 比賽中有幾個變數就應該要嘗試從不同的變數的角度，值域思考

相似題目: 517. 超级洗衣机

有多個負數的作法:

todo

Q4. Minimum Deletions to Make Alternating Substring

其實看錯題目但是最後還是對的，題目要求的是操作二要刪除字母，比賽的時候看成替換字母，不過核心思想還是利用 01 變化的差分的前綴和。

另外還有分治利用線段樹的做法

ref

Weekly contest #481¶

Q3. Minimum Swaps to Avoid Forbidden Values

題目的本質是相鄰不同貪心的應用，但是花太長時間思考導致 Q4 沒有時間思考。

對於陣列 nums \(n_i\) 和 forbidden \(f_i\) 組成的配對 \(p_i = (n_i, f_i)\) 必須透過交換 \(swap(n_i, n_j), i \neq j\)，使得 \(p_i = (n_j, f_i), n_j \neq f_i\)，求最小的交換次數。

很顯然的我們必須將 \(n_i = f_i\) 的配對做交換，假設 (a, a) 是一個 \((n_i, f_i)\) 配對，那可以和他進行交換的配對為 (b, b), (b, c) 兩種選擇，可以知道與 (b, b) 進行交換是比 (b, c) 更好的選擇，因為一次交換可以減少兩個 \(n_i = f_i\) 的配對。因此可以得到對於 \(n_i = f_i\) 的配對，可以先將他們進行組內的交換，而多出來的部分再與 (b, c) 做交換，如何交換則是應用相鄰不同貪心。

Q4. Total Sum of Interaction Cost in Tree Groups

比賽最後想到的是可能要用換根，但是最後時間不夠沒想明白。

換根的作法，由點的視角出發:

第一次 dfs 的時候計算 sub[x] 和 f[x]，sub[x] 為以 x 為根的子樹內合法節點的個數，f[x] 以 x 為根到子樹中合法節點的貢獻。

由於我們要計算的是 x 到子樹中合法節點的貢獻，所以在計算貢獻的時候除了加上 f[y] 還要加上 sub[y] 表示從 x->y 這條邊的貢獻(f[x] += f[y] + sub[y] 每次往上走一條邊會增加 sub[y] 的貢獻)。

第二次作 dfs 的時候，每遇到一個合法節點，計算這個節點所做出的貢獻 f' + f[x]， f' 為從這個節點到其他合法節點的貢獻，也就是除了 x 的子樹以外的合法節點。

在遞歸到子樹 y 的時候要將 f' 傳到子樹 y，並且加上變化量，f'' = f' + f[x] - (f[y] + sub[y])，f[x] 當前節點到其他合法節點的貢獻，f[y] + sub[y] 為扣掉子樹 y 的部分。

另一個做法為邊的貢獻法，由邊的視角出發:

走訪每條邊同時計算對答案的最終貢獻，貢獻的計算方式為利用邊將圖一分為二，而對答案的貢獻為兩邊合法節點的相乘，表示有多少對合法節點的配對經過這條邊。

Weekly contest #482¶

Q2. Minimum Cost to Acquire Required Items

分類討論不夠細心，沒導致比賽的時候 wa 了 2 次

Q3. Smallest All-Ones Multiple

這題因為題目看不太懂結果花了太長的時間，中間還想到歐拉函數，懂題目後秒殺題。

Q4. Number of Balanced Integers in a Range

模板，因為沒有宣告 long long wa 了一次。