CSP 2025 炸了，意識到 CTT 再炸就沒有 WC 玩了，很生氣！

記錄了日常訓練中的一些題。

2025-11-03 洛谷 P10707 永恒（Eternity）

求出大小為 \(n\) 的可重集滿足最大子集 \({\rm xor}=m\) 數量，\(n\le10^5,m<2^{60}\)。

把線性基最小化后對著最小化線性基數量以及維度對應可重集數量分別算一下就可以做到 \(\mathcal{O}(n\log m+\operatorname*{poly}(\log m))\) 了。

2025-11-03 QOJ 4885 Triangular Cactus Paths

給定一棵仙人掌，保證環長 \(\le 3\)，\(q\) 次詢問 \(x\to y\) 長度為 \(k\) 的簡單路徑數量，\(n,q\le2\times10^5\)。

隨便圓方樹算出最小距離和路徑上三元環數量組合計數就好了，時間復雜度 \(\mathcal{O}(n+q)\)。

2025-11-03 QOJ 4883 Bayan Testing

給定 \(n\) 和 \(2m\) 個區間，構造長度為 \(n\) 的數列使得恰有 \(m\) 個區間所有元素互不相同，\(n\le2\times10^5,m\le10^5\)。

構造形如 1 2 3 4 5 6 ... x y y y y y y 的數列即可（\(y\le x\)），把 \(l\ne r\) 的區間排序后隨便弄弄就做到 \(\mathcal{O}(n+m)\) 了。

2025-11-03 QOJ 4879 Standard Problem

給定 \(n\) 個 \([1,m]\) 的區間，區間帶權，選出一個子序列使得存在一種在每個區間內選數的方法使得其不降，問最多選的權值和以及方案數，\(n,m\le2\times10^5\)。

發現就是對于每個區間，其前面的 \(l\) 最大值不超過 \(r\)，那么線段樹維護 dp 值就好，下標記錄的是當前 \(l\) 最大值，時間復雜度 \(\mathcal{O}(m+n\log m)\)。

2025-11-03 QOJ 4880 Network Transfer

有 \(n\) 個文件要傳輸，給定帶寬和每個文件的大小和發送時間，然后每個文件有優先級，同時傳的時候按照優先級成比例分配，問每個文件收到時間，\(n\le2\times10^5\)。

帶寬是 \(w\)，然后大小 \(s\)，優先級 \(a\)，優先級總和 \(b\)，那么發送時間是 \(T=\frac{s}{wa/b}=sb/wa\)，可以看作有一個隨著時間增加的變量 \(c\)，其增長速度為 \(w/b\)，然后這個文件需要 \(c\) 增長到 \(s/a\) 的時候結束，所以用 set 維護傳輸中的文件，然后這些文件收到的順序其實固定了，處理一下文件的加入和刪除同時動態維護 \(b\)，模擬一下即可，時間復雜度 \(\mathcal{O}(n\log n)\)。

2025-11-03 QOJ 4888 Decoding The Message

有一個序列 \(a\)，對于 \(i\in[0,256)\cap\mathbb{Z}\) 有 \(c_i\) 個 \(i\)，對于 \(n!\) 個排列，記將 \(a\) 看作 \(256\) 進制數的結果為 \(k\)，求出所有 \(k\) 的乘積 \(\bmod 65535\)，詢問 \(100\) 次。

考慮分別求出 \(\bmod 255\) 和 \(\bmod 257\) 然后 CRT，前者每一位的位權都是 \(1\)，后者 \(1,-1\) 交錯。

然后相當于把這些數分成兩類然后求出它的 \(w=\left\lfloor\frac{n}{2}\right\rfloor!\left\lceil\frac{n}{2}\right\rceil!\) 次冪，如果 \(n\le 11\) 暴力，否則 \(w=0\)，只要求出底數是否為 \(0\)，顯然當有至少兩個數數目大于 \(2\times257+10\) 的時候底數為 \(0\)，否則對于除了出現次數最多的數以外背包即可，時間復雜度 \(\mathcal{O}(1)\)。

\(\color{red}\Huge\text{今天墮落了，引起重視！！！}\)

2025-11-04 QOJ 4887 Fast Bridges

\(n\times n\) 的網格圖，都是無向邊，邊權均為 \(1\)，有 \(m\) 條特殊雙向邊連接 \((a,b),(c,d)\)，邊權為 \(|a-b|+|c-d|-1\)，保證 \(a\ne c,b\ne d\)，求所有點對最短路之和，\(m\le500\)。

假設從 \((A,B)\) 走到 \((C,D)\)（\(A\le C,B\le D\)），肯定一直往右下走，最短路就是 \(C-A+D-B\) 減去最多經過特殊邊數量，前者的和好算，后者我們把往右下走的邊和往右上走的邊分開算，顯然是對稱的。

對于前者，算出 \(f_{i,j}\) 表示從第 \(i\) 條管道走到第 \(j\) 條的最多經過管子數量，然后枚舉當前考慮小矩形，那么其開始管道有 \(m\) 種，枚舉一下管道 \(t\) 然后對于每個 \(x\) 算出 \(f_{t,*}\ge x\) 的 \(*\) 對應管道右下角的舉行并，這樣復雜度是四方的，但是不用更新所有管道，有的信息可以重復利用就做到 \(\mathcal{O}(m^3)\) 了。

\(\color{red}\Huge\text{今天墮落了，引起重視！！！}\)