NOIP模拟77

「最大或·答題·聯合權值?改·主仆見證了 Hobo 的離别」on 10.15

前言

感覺最近太飄了，這次考試是挺好的一次打擊（好像也不算是）。

犯了一個智障錯誤（雙向邊一倍數組 100pts->30pts）别的就。。

T1 最大或

一開始我以為是一個找規律，然而在打表找規律 20min 後無果。。

然後開始考慮二進制位上的東西，畫了一顆 Tire 樹，發現從高位到低位相同的位我們無論如何或貢獻都是一樣的。。

直到第一個不同的位開始都是可以通過 \(or\) 操作成為 1 的。

然後擴充一下，我試了試左右短點在 \([1000,1000]\) 區間内的情況把詢問改成 \(xor\) 也是類似的關系，隻不過之前的位都是 0了。

代碼也就和題目做法差了一句話 <code>for(int i=60;i&gt;=0;i--)if(((l&gt;&gt;i)&amp;1)!=((r&gt;&gt;i)&amp;1)){ans+=(1ll&lt;&lt;i+1)-1;break;}</code>

T2 答題

個人感覺這個題的思路較于這個題目本身要重要。

本道題的實質其實是求用所給的 \(n\) 個數組成的 \(2^n\) 個數中的第 \(\operatorname{ceil}(2^n\times p)\) 大值。

直接枚舉顯然不能通過，是以我們需要進行折半枚舉（\(meet\;in\;the\;middle\)），即枚舉求出前 \(\frac{n}{2}\) 個數可以組成的所有值，以及後 \(\frac{n}{2}\) 個數可以組成的所有值。

二分需要求的最後答案是多少。

對于每一個二分到的值，我們要求出所有組合中小于它的數字個數。

雙指針掃一遍即可。

T3 聯合權值?改

正解不是特别會，但是 <code>bitset</code> 卡空間卡時間可以跑過。。（建邊數組開兩倍。。。）

思路就比較簡單了，枚舉每一個三元組的中轉點，再枚舉連邊判斷兩者之間是否有連邊。

時間複雜度 \(\mathcal{O}((n+m)m)\) 空間複雜度 \(\mathcal{O}(\frac{n^2}{32})\)

T4 主仆見證了 Hobo 的離别

發現把建立的點與之前點的關系當做連邊的話，其實就形成了一棵樹（畢竟題目保證了每個節點最多被融合一次）

那麼我們考慮如何維護，可以對于不同的關系視為不同的邊權。

對于詢問的 \(X,Y\) 之間一定存在着祖先關系，是以可以利用 DFS 序進行判斷。

如果 \(X\) 是 \(Y\) 的祖先那麼着一路的關系都隻能是交。

同樣的，如果 \(X\) 是 \(Y\) 的祖先那麼着一路的關系都隻能是并。

并茶幾維護即可，注意特判 \(K=1\) 也就是兩個完全相同的點的情況。