The 3rd Universal Cup. Stage 8: Cangqian

• 連結：https://qoj.ac/contest/1780
• 時間：2025 Apr 2, 07:00-12:00
• 團隊：SorahISA
• 成績：5 / 13, Penalty 596, dirt 44% ( A B C D E F G H I J K L M )

在 A 大坐牢，寫了 python 不知道為什麼會 RE 卡了一個小時。

Problem A. Bingo

待補

Problem B. Simulated Universe

待補

Problem C. Challenge NPC

Tags: constructive

構造一張簡單無向圖 $G$ 使得存在一個正整數 $c$ 滿足最小點著色數 $\le c$ 且 greedy 解至少要用 $c+k$ 個顏色。

• Greedy 解：對 $i=1,2,\dots ,n$，將點 $i$ 著 $\mathrm{mex}\{c_u:u<i\wedge (u,i)\in E(G)\}$ 的顏色（此處的 $\mathrm{mex}$ 為 $1$-based）。

• $k\le 500$、$n\le 1024$

$k$ 這麼大，感覺就可以弄一張二分圖做到 $2$ 跟 $n/2$，所以就做完了。

只要把第 $k$ 小的奇數／偶數連向第 $1,2,\dots ,k-1$ 小的偶數／奇數就可以了。

• 因為是二分圖，所以最佳解顯然是 $2$。
• 第 $k$ 小的奇數／偶數會被 greedy 解填上顏色 $k$。

Problem D. Puzzle: Easy as Scrabble

待補

Problem E. Team Arrangement

Tags: greedy, bit operation

要把 $n$ 個人分成若干組，第 $i$ 個人希望自己在的小組有 $[{\ell }_i,r_i]$ 個人。如果一種分組方法每一組分別有 $c_1,c_2,\dots ,c_k$ 個人，那麼總價值就是 $\sum _{j=1}^k{w}_{c_j}$。

請求出最大價值的分組，或判斷其不可能達成。

• $n\le 60$、$|w_i|\le 10^7$

第一直覺是先枚舉每一組的大小，再判斷該分組能不能被達成。$n$ 個人的分組數量是 $p(n)$，而 $p(60)=966467$，於是大概要一個 $\mathcal{O}(n)$ 的方法來判斷。

最簡單的方法是 greedy：先將區間們依照右界小到大排序，再每次取 ${\ell }_i$ 的 lower bound 出來。用 multiset 果不其然的吃了 TLE，改成 map 之後有稍微改善，但複雜度仍然有一個 $\log n$。

注意到這題 $n\le 60$，每一組的大小也只有 $60$ 以下，可以用一個 uint64_t 來儲存！

• 跟用 map 的做法一樣，存在 $x$ $⟺$ (val >> x) & 1。
• 求 $\ell$ 的 lower bound 可以用 __builtin_ctzll(val >> l << l) 來做，這樣就可以在 $\mathcal{O}(1)$ 的時間內找到。
  • 注意 __builtin_ctzll(0) 會是 undefined behavior，可以特判，或是一開始就放 1 << (n+1) 進 val 裡面。

於是這樣的複雜度就變成 $\mathcal{O}(p(n)\cdot n^2/w)=\mathcal{O}(p(n)\cdot n)$ 了。

Problem F. Stage: Agausscrab

水題，跳過

Problem G. Crawling on a Tree

待補

Problem H. Permutation

待補

Problem I. Piggy Sort

待補

Problem J. Even or Odd Spanning Tree

Tags: mst, lca

給一張帶正邊權的 $n$ 點 $m$ 邊無向圖 $G$，求 weight 分別是奇數跟偶數的最小生成樹，輸出 weight 即可（不存在則輸出 $-1$）。

• 多筆測資、$\sum n\le 200000$、$\sum m\le 500000$

顯然有一邊的答案就是 MST 本身。

• $\text{Claim 1.}$ 令 $f(k)$ 是選了 $k$ 條奇邊的最小生成樹 weight，如果最小生成樹選了 $a$ 條奇邊，那答案一定是 $f(a-1)$ 或 $f(a+1)$。

• $\text{Claim 2.}$ 要得到 $f(a\pm 1)$ 只要枚舉樹外邊 $(u,v)$ 跟 $u⇝v$ 路徑上奇偶性相異的最大值換就好。

於是只要用 LCA 維護路徑上的奇數 weight、偶數 weight 最大值是多少就可以了。

時間複雜度：$\mathcal{O}(m\log n)$。

Problem K. Sugar Sweet 3

待補

Problem L. Challenge Matrix Multiplicatio

待補

Problem M. Triangles

待補