摘要：
題目內容 ZHY 有一個 \(n\) 個點的完全圖，點 \(u\) 與點 \(v\) 的距離為 \(\gcd(u,v)\)，求這個完全圖的最大生成樹的邊權之和。 思路 方法一 很明顯這道題目是在求最大生成樹，但由于數據中 $1≤n≤ 10^{7} $ ,明顯不能使用暴力枚舉每兩個點之間的 \(\gc
閱讀全文
摘要：
首先，這道題目要求最后保留的序列單調不減，那么同樣的顏色必須連續排列。 為了保證這一點，我們可以記錄下每個顏色第一次出現的位置以及最后一次出現的位置，每次只有當前位置為此顏色的第一個并且上一個位置為此顏色的最后一個才考慮將當前位置接在上一個位置后面。 接下來，我們可以開始考慮如何動態規劃，\(dp_
閱讀全文
摘要：
首先，我們來分析一下題目中給出的兩種移動方法： 移動至當前結點的父結點。特殊地，如果當前位于根結點，則不進行移動； 移動至當前結點的所有子結點中編號最小的結點。特殊地，如果當前位于葉子結點，則不進行移動。 預處理 不難發現，對于每個節點 \(i\) 來說，它最高能達到的節點一定是根節點 \(1\)，
閱讀全文
摘要：
我們考慮這道題目要求我們在數列 \(s\) 中找到一個一個區間 \([i,j]\) 滿足： \(l\in[1,l-1],r\in [r+1,n]\) \(j-i+1\) 最小化 在數列 \(s\) 中找不到一個與區間 \([i,j]\) 不同的區間 \([p,q]\) (即 \(i\ne p,j\n
閱讀全文
摘要：
被 hack 的缺陷做法 我們考慮任意一個節點 \(i\) 如果已經是當前平均數最大值，那么必然不存在一個節點能夠使節點 \(i\) 的平均數更大。考慮到節點 \(i\) 的父節點 \(j\) ，此時節點 \(j\) 的平均值一定 \(\le\) 節點 \(i\) 的平均值，所以此時可以通過節點 \
閱讀全文
摘要：
我們不妨先尋找 Alice 的出招序列 \(a\) 中的 \(a_i\) 與 Bob 的出招序列 \(b\) 中的 \(b_j\) 在什么時候會在同一局中出現，考慮 Alice 與 Bob 會進行 \(10^{100}\) 局游戲，所以可以認為是無限局游戲，那么只要 \(nx+i=by+j\) 存在
閱讀全文
摘要：
我們不妨先維護出按照題目要求插入數據后的數列 \(a\)，很明顯，每次將 \(i\) 插入 第 \(p\) 位就是要找到數列 \(a\) 中的第 \(p-1\) 號元素，然后將 \(i\) 插入到 \(p-1\) 號元素與 \(p\) 號元素之間，這可以非常輕松的用平衡樹維護，具體來說就是將排名小于
閱讀全文
摘要：
[列隊春游] 題解 題意 給定整數序列 \(a\)，對于隨機排列 \(p\)，求 \(\sum f_i\) 的期望。 對于位置 \(i\)，\(f_i\) 定義為最小的 \(x\)，滿足對于任意位置 \(j,1 \leq x \leq j \leq i\)，均有 \(a_{p_j} \leq a_{
閱讀全文
浙公網安備 33010602011771號