2025.03 做題記錄

*：瞄了一眼題解就會了

**：看了題解

1. P5283 [十二省聯考 2019] 異或粽子 **

首先用處理出前綴異或和，開一個Trie全部存下。對于 \(\text{xor}[l,r]\) ， \(\text{xor}[r,l]\) 是相等的。所以考慮讓 \(k\gets 2k\)，這樣就不用讓 \(l<r\)。

對于 \(w\)，我們可以在 \(O(\log V)\) 求出與 \(w\) 異或后第 \(k\) 大的值。類似線段樹二分。

所以對于 \(i\in[0,n]\)，先求出與其最大的異或和，存入堆內。

每一次從堆頂取出元素，如果這是 \(w\) 的第 \(k\) 大值，就計算 \(w\) 的第 \(k+1\) 大值存入堆。這樣取 \(2k\) 次的和就是答案。

時間復雜度 \(O(n\log n\log V)\)。

提交記錄

2. P4559 [JSOI2018] 列隊 *

首先對于區間 \([l,r]\) 的學生，我們將其的位置排序后存入數組 \(a_{l\sim r}\)，一定存在一個 \(x\)，使得 \([a_l,x]\) 的學生都往右跑，\([x,a_r]\) 的學生往左跑。

所以考慮用主席樹+二分的方式，設區間 \([a_l,x]\) 有 \(k\) 個學生，則需找到 \(x\le X+k-1\) 最大的 \(x\)。其中 \(X\) 為集合位置。

這樣做是 \(O(n\log n\log V)\)，常數很大。只能拿 70pts。

考慮將主席樹外二分改為主席樹內二分?？梢詢灮?\(O(n\log n)\)?？梢酝ㄟ^。

提交記錄

3. P7518 [省選聯考 2021 A/B 卷] 寶石

把有向路徑 \((u,v)\) 拆成 \((u,lca)\) 和 \((lca,v)\)。

對于每一個點，對它祖先內最近的前一個寶石和后一個寶石連邊，構成兩種不同的樹。用于倍增。

先由 \(u\) 開始，向上并向后（寶石順序）倍增。找到 \((u,lca)\) 的填入寶石個數 \(x\)。

再考慮 \((lca,v)\)。如果從 \(lca\) 開始跳很不方便，路徑很難被限制。所以考慮從 \(v\) 向上跳。

開一棵主席樹記錄每一個節點的祖先中各個寶石的最近祖先節點。

然后在主席樹上二分，如果從該寶石的最近祖先節點開始，向上并往前跳，是否能跳到寶石順序 \(\le x\) 的點。

時間復雜度 \(O(n\log m\log n)\)。

提交記錄

4. P4587 [FJOI2016] 神秘數 **

首先要先搞懂如何查詢答案。

設當前可以表示 \([1,x]\) 的所有數，設下一個沒用過的最小的數為 \(u\)。

當 \(u\le x+1\)，則可以表示 \([1,x+u]\)。
否則不能表示 \(x+1\)。

所以考慮用可持久化值域線段樹維護區間的每個數的出現次數。動態維護 \(x\)，如果值在 \([1,x]\) 的數的和 \(sum\) 滿足 \(sum>x\)，則讓 \(x\gets sum\)。否則輸出 \(x+1\)。

根據打表可知每一次 \(x'\ge 2x\)。所以在 \(O(\log V)\) 次就會結束。

時間復雜度 \(O(n\log n+q\log n\log V)\)。

提交記錄

5. P6071 『MdOI R1』Treequery *

首先，需要維護出 \(\operatorname{lca}[l,r]\)。用線段樹維護。這里求LCA考慮用ST表+歐拉序列維護，以減小時間復雜度。

現在考慮 \((root,p)\) 這條路徑。\(\operatorname{lca}[l,r]\) 以下簡記為 \(lca\)。

進行分類討論：

如果 \(lca\) 在 \(p\) 的子樹內，則答案為 \(dis(lca,p)\)。
如果 \(lca\) 不在 \(p\) 的子樹內且 \(p\) 的子樹內有 \([l,r]\) 的點，則答案為 \(0\)。
如果 \(lca\) 不在 \((p,root)\) 路徑上，則答案為 \(dis(p,lca)\)。

判定辦法：如果 \(\operatorname{lca}(lca,p)\neq lca\)，則 \(lca\) 不在 \((p,root)\) 路徑上。
否則，則需找到 \((p,root)\) 上最深的點 \(x\) 使得該點的子樹內有 \([l,r]\) 的點。

這個 \(x\) 可以用主席樹+倍增找到。則答案為 \(dis(x,p)\)

那么如何判定 \(p\) 內是否有 \([l,r]\) 的點？

如果用啟發式合并+主席樹，需要 \(O(n\log ^2n)\) 的時空復雜度。但是如果用dfs序，就只用 \(O(n\log n)\) 的時空復雜度。

所以總時間復雜度 \(O(n\log n+q\log ^2n)\)。

提交記錄

6. P3567 [POI 2014] KUR-Couriers *

這么簡單的題怎么沒想到呢？

可持久化值域線段樹維護區間數的出現次數。

然后進行遞歸處理。如果左子樹的出現總數 \(\ge \frac{r-l+1}2\) 就遞歸左子樹，否則遞歸右子樹。

只會遞歸一個子樹，所以時間復雜度是對的。

時間復雜度 \(O(n\log n+q\log n)\)。

提交記錄

7. P5795 [THUSC 2015] 異或運算 *

怎么把可持久化01Trie+二分轉化為可持久化01Trie內二分這么簡單的優化方法都想不到呢？

首先發現 \(m\le 3\times 10^5\)，但是 \(n\le 1000,q\le 500\)。

感覺時間復雜度是個 \(O(nq\log V(\log V))\) 啥的玩意兒。

于是對 \(b\) 數組建一棵可持久化01Trie。然后對于每一次詢問，去二分最終答案，然后枚舉 \(a_i\) 去計算 \(b_j\ \text{xor}\ a_i\ge ans,j\in[l,r]\) 的個數。

然后就是 \(O(nq\log^2 V)\)。在可持久化01Trie的常數加持下，我們成功獲得 TLE 10pts 的好成績。

怎么優化？轉為可持久化01Trie內二分唄。維護 \(d-u+1\) 個指針，判斷答案這一位如果為 \(1\) 時的個數是否 \(\ge k\)，如果滿足則為 \(1\)，所有指針同時跳 \(1\)。否則為 \(0\)，所有指針同時跳 \(0\)。

時間復雜度 \(O(m\log m+nq\log V)\)。

提交記錄

8. 【0306 B組】 D. 種植 **

題目鏈接

題意：

一個 \(n\times m\) 的網格。網格上有障礙，有障礙的地方不能通過?，F在要從 \((1,1)\) 走到 \((n,m)\)，每一次只能向下或向右走一個。

你需要在網格中選一些不是障礙的點，使得任意一條從 \((1,1)\) 到 \((n,m)\) 的路徑上恰好有一個點被選中。求方案數，對 \(10^9+7\) 取模。

\(n,m\le 5000\)。

本質上是一個割的問題，割掉點使得 \((1,1)\) 與 \((n,m)\) 不連通。

先將所有不能到達 \((n,m)\) 或者由 \((1,1)\) 不可達的點拋開不看，因為他們是否被選中不重要。設有 \(x\) 個這樣的點，則方案數需 \(\times 2^{x}\)。

現在有一個條件，就是每條路徑恰好有一個點被選中。翻譯一下，就是被選中的點之間互相不可達。

所以考慮平面圖轉對偶圖，參考平面圖最小割轉對偶圖最短路。

對于一條點，如果我們把它割掉了，就相當于將他的出邊都給割掉了。那么我們會建出一個圖來。

現在有以下樣例：

輸入：

5 8
......##
.##..#..
...#....
.....##.
#.......

輸出：

我們把障礙與 \(3\) 個不可達的點給刪去，就得到以下的圖：

一個空白的格子為一個點。

因為 \((n,m)\) 也可以割掉的，所以還需加一條邊。

那么方案數就是從右上走到左下的方案數。也就是圖中 \(2^3\times (6\times 6+4\times 4+2)=432\)。

直接模擬即可。時間復雜度 \(O(nm)\)。

提交記錄

9. P5298 [PKUWC2018] Minimax *

這個題感覺很線段樹合并啊。因為 \(n\le 3\times 10^5\)，而且每一個葉子的值都不相等。

所以直接對于葉子的值離散化，然后考慮用值域線段樹存下來。對每一個兒子用動態開點值域線段樹存下。

線段樹 \(u\) 中下標為 \(i\) 的位置存的是節點 \(u\) 權值為 \(i\) 的概率，記為 \(p_{u,i}\)。同時我們還要維護概率的區間和。

因為保證兒子個數不超過 \(2\) 個，所以當只有一個兒子時，就可以直接繼承。否則就需要合并兩個兒子的線段樹。

如何合并呢？為了保證時間復雜度，我們需要對每一個線段樹上每一個節點進行合并。

我們考慮對于節點 \(u\) 的兒子 \(x,y\) 線段樹的區間 \([l,r]\) 進行合并。

設 \(xpre=\sum_{i=1}^{l-1} p_{x,i}，xsuf=\sum_{i=r+1}^{n} p_{x,i}，ypre=\sum_{i=1}^{l-1} p_{y,i}，ysuf=\sum_{i=r+1}^{n} p_{y,i}\)。

同時設 \(xsum=\sum_{i=l}^r p_{x,i}，ysum=\sum_{i=l}^r p_{y,i}\)。

則有：

\[\sum_{i=l}^r p_{\text{merge(x,y),i}}=(xsum\times ysum)+(1-p_u)(ysuf\times xsum+xsuf\times ysum)+p_u(xpre\times ysum+ypre\times xsum) \]

其它的都好說，就是關于 \(xpre,xsuf,ypre,ysuf\) 怎么求？如果用 \(O(\log n)\) 查詢，那么在動開線段樹的加持下肯定TLE。

其實我們可以在往下遞歸時順帶求出來。就如在遞歸左子樹時，就讓 \(xsuf\gets xsuf+右子樹 xsum，ysuf\gets ysuf+右子樹 ysum\)。

那么就可以直接求出來了。

但是還有一個問題。正常來說，合并 \(x,y\) ，當其中 \(y\) （\(x\) 同理）為空時，正常來說應該直接返回\(x\)。但是此題 \(x\) 的子孫的值應該被更改。因此此處不能直接返回 \(x\)。

那該怎么辦？直接遞歸下去會導致時間復雜度假了，變成 \(O(n^2)\)，我們如何使得可以不用遞歸下去？

我們先來研究一下這些應該被更改的點會被更改成什么。因為 \(y\) 節點是空節點。所以 \(ysum=0\)。

那么此時

\[\sum_{i=l}^r p_{\text{merge(x,y),i}}=(xsum\times ysum)+(1-p_u)(ysuf\times xsum+xsuf\times ysum)+p_u(xpre\times ysum+ypre\times xsum) \\=(1-p_u)(ysuf\times xsum)+p_u(ypre\times xsum) \\= xsum\times ((1-p_u)\times ysuf+p_u\times ypre)\]

發現其實是同時乘上了一個數。所以可以直接打lazy tag。打一個乘法懶標記就行了。

所以對于 \(x,y\) 中有一個是空節點的情況，直接在另一個節點上打一個乘法懶標記即可。

時間復雜度 \(O(n\log n)\)。

提交記錄

10. P4284 [SHOI2014] 概率充電器

考慮期望的線性性。對于元件 \(i\)，設其通電的概率為 \(p_i\)，則答案為 \(\sum_{i=1}^n p_i\times 1=\sum_{i=1}^n p_i\)。=

先考慮 \(O(n^2)\) 做法。

對于一個點，我們設其為樹根。然后嘗試一下跑dp。

\(dp_{u}\) 表示 \(u\) 不通電的概率，則有轉移：

\[dp_{u}=(1-q_u)\prod_{v\in son_u}[1-P(u,v)+P(u,v)dp_v] \]

則 \(i\) 的答案需要以 \(i\) 為根跑一遍dp，讓 \(ans\gets ans+dp_{i}\)。

然后就可以 \(O(n^2)\) 進行dp了。

如何優化到 \(O(n)\)？

考慮用換根dp進行加速。通過 \(f_u\) 推出 \(f_v\)。

你會發現，因為 \(dp_u\) 是若干個值乘起來，所以撤銷/更改就會比較方便。

因為 \(dp_u=(1-q_u)\prod_{v\in son_u}[1-P(u,v)+P(u,v)dp_v]\)，更改后 \(v\) 不再是 \(u\) 的兒子，所以需要讓 \(dp_u\gets dp_u\times [1-P(u,v)+P(u,v)dp_v]^{-1}\)。

同時，\(u\) 會成為 \(v\) 的新兒子，所以讓 \(dp_v\gets dp_v\times [1-P(u,v)+P(u,v)dp_u]\) 即可。

但是 \([1-P(u,v)+P(u,v)dp_v]\) 可能會等于 \(0\)，此時讓 \(dp_{u}=1\) 即可。

提交記錄

11. P10764 [BalticOI 2024] Wall **

設 \(p_i=\max_{j=1}^i h_j，s_i=\max_{j=i}^n h_j\)。

所以答案就是 \(\sum_{i=1}^n \min(p_i,s_i)-h_i\)。

因為 \(p_i,s_i\) 都跟 \(\max\) 有關，而式子里卻有 \(\min\)，所以轉化一下：

\[\sum_{i=1}^n \min(p_i,s_i)=\sum_{i=1}^n p_i+s_i-\max(p_i,s_i)-h_i\\=-n\times p_n+\sum_{i=1}^n p_i+\sum_{i=1}^ns_i-\sum_{i=1}^nh_i \]

這里面 \(\sum_{i=1}^n h_i=2^{n-1}(a_i+b_i)\)。

接下來就要求 \(\sum_{i=1}^n p_i\) 。

考慮設 \((i,j,h_i)\) 為 \(p_j=h_i\) 的權值和。因為可能出現 \(p_j=h_i\) 的 \(i\) 有多個的情況，所以我們欽定為最小的那個 \(i\) 為最大值所在位置，也就是只計算最小的 \(i\) 與 \(j\) 的在 \(h_i\) 的貢獻。

首先先把式子列出來：

\[(i,j,h_i)=h_i\times \prod_{k=1}^{i-1}([a_k<h_i]+[b_k<h_i])\times \prod_{k=i+1}^j ([a_k\le h_i]+[b_k\le h_i])\times 2^{n-j} \]

可以暴力求，就有 \(O(n^2)\) 。

如何優化？

考慮對于一個 \(i\)，將所有 \(j\) 一起處理。為了方便，我們設 \(w(i,h_i)=\prod_{k=1}^{i-1} ([a_k< h_i]+[b_k< h_i])\)。 \(w(i,h_i)\) 可以通過從小到大加入 \(a_i,b_i\)，用單點修改、區間乘積線段樹預處理出。

所以有：

\[(i,h_i)=h_i\times w(i,h_i)\times \sum_{j=i}^n 2^{n-j} \prod_{k=i+1}^{j}([a_k\le h_i]+[b_k\le h_i]) \]

此時我們維護 \(f(j,h_i)=\sum_{i=1}^j 2^{n-j} \prod_{k=1}^{j}([a_k\le h_i]+[b_k\le h_i])\)，則有：

\[(i,h_i)=h_i\times w(i,h_i)\times f(n,h_i)\times f(i,h_i)^{-1} \]

而 \(f(j,h_i)\) 相當于對于每一個位置，有一個 \(2^{n-j}\) 的權值，然后求權值乘上一個前綴乘積之和?？梢杂镁€段樹維護。

所以綜上，二者都可以用線段樹求得。時間復雜度 \(O(n\log n)\)。

然后 \(\sum_{i=1}^n s_i\) 可以通過左右翻轉 \(a,b\) 序列，再跑一遍上述算法得到。

然后 \(p_n=\sum_{i=1}^n (i,n,h_i)\)，可以在上述算法中順便求出。

時間復雜度 \(O(n\log n)\)。

提交記錄

12. CF2077C Binary Subsequence Value Sum

告誡后人：*2300 的題我做了2h，原因是把子序列看成子段了！?。《铱荚嚨臅r候也看錯了，不長記性?。?！

\(F(v)\) 本質上是求該序列 \(1\) 的個數 \(-\) 該序列 \(0\) 的個數。

現在我們要將 \(v\) 分成兩個部分，然后將 \(F\) 值乘起來。我們發現，當往一個序列后面加入一個數字時，它的 \(F\) 會 \(+1\) 或 \(-1\)。所以對于我們 \(v\) 一定可以拆出一個部分的 \(F\) 值在 \([0,F(v)]\) 之間。

所以

當 \(|v|\) 為偶數時，一定可以將 \(F(v)\) 拆成 \(\frac{F(v)}2+ \frac{F(v)}2\)

此時 \(v\) 的價值為 \(\frac{F(v)}2\times \frac{F(v)}2\)；
而當 \(|v|\) 為奇數時，一定可以將 \(F(v)\) 拆成 \(\frac{F(v)+1}2+ \frac{F(v)-1}2=\frac{[F(v)]^2}4\)

此時 \(v\) 的價值為 \(\frac{F(v)+1}2\times \frac{F(v)-1}2=\frac{[F(v)]^2-1}4\)；

為了讓兩式一樣，我們將 \(\frac 14\) 提出來，然后將 \(|v|\) 為奇數時分子的 \(-1\) 給提出來單獨計算，也就是長度為奇數的子序列的個數，即 \(\sum_{i=0}^{\lfloor\frac{n-1}2\rfloor} c_n^{2i+1}\)。

現在問題就轉化為對所有子序列 \(v\) ，求 \([F(v)]^2\)。

所以我們設 \(c0\) 和 \(c1\) 為整個序列 \(0\) 的個數和 \(1\) 的個數。

則有

\[\sum_{v}[F(v)]^2=\sum_{i=0}^{c0}\sum_{j=0}^{c1}C_{c0}^iC_{c1}^j(i-j)^2 \\= \sum_{i=0}^{c0}C_{c0}^ii^2+\sum_{j=0}^{c1}C_{c1}^jj^2-2\sum_{i=0}^{c0}\sum_{j=0}^{c1}C_{c0}^iC_{c1}^jij \]

設 \(w_n=\sum_{i=0}^nC_n^ii^2\)。

則有轉移 \(w_i=2w_{i-1}+i\times 2^{i-1}\)。

于是式子就是

\[\sum_{v}[F(v)]^2= w_{c0}+w_{c1}-2\sum_{i=0}^{c0}C_{c0}^ii\sum_{j=0}^{c1}C_{c1}^jj \\= w_{c0}+w_{c1}-2\times 2^{c0-1}\times c0\times 2^{c1-1}\times c1 \\= w_{c0}+w_{c1}-2^{n-1}\times c0\times c1 \]

于是每一次修改，只要知道 \(c0\) 和 \(c1\) 就可以 \(O(1)\) 求解。

設 \(l=\sum_{i=0}^{\lfloor\frac{n-1}2\rfloor} c_n^{2i+1}\)。所以答案就是

\[\frac14( w_{c0}+w_{c1}-2^{n-1}\times c0\times c1-l)\]

時間復雜度 \(O(n+q)\)。

提交記錄

posted @ 2025-04-08 07:35 Twilight_star 閱讀(13) 評論(0) 收藏舉報

刷新頁面返回頂部