摘要：
題目內容 ZHY 有一個 \(n\) 個點的完全圖，點 \(u\) 與點 \(v\) 的距離為 \(\gcd(u,v)\)，求這個完全圖的最大生成樹的邊權之和。 思路 方法一 很明顯這道題目是在求最大生成樹，但由于數據中 $1≤n≤ 10^{7} $ ,明顯不能使用暴力枚舉每兩個點之間的 \(\gc 閱讀全文
posted @ 2025-10-30 18:32
cogimyun
閱讀(12)
評論(0)
推薦(0)
摘要：
首先，這道題目要求最后保留的序列單調不減，那么同樣的顏色必須連續排列。 為了保證這一點，我們可以記錄下每個顏色第一次出現的位置以及最后一次出現的位置，每次只有當前位置為此顏色的第一個并且上一個位置為此顏色的最后一個才考慮將當前位置接在上一個位置后面。 接下來，我們可以開始考慮如何動態規劃，\(dp_ 閱讀全文
posted @ 2025-10-30 18:31
cogimyun
閱讀(0)
評論(0)
推薦(0)
摘要：
首先，我們來分析一下題目中給出的兩種移動方法： 移動至當前結點的父結點。特殊地，如果當前位于根結點，則不進行移動； 移動至當前結點的所有子結點中編號最小的結點。特殊地，如果當前位于葉子結點，則不進行移動。 預處理 不難發現，對于每個節點 \(i\) 來說，它最高能達到的節點一定是根節點 \(1\)， 閱讀全文
posted @ 2025-10-30 18:28
cogimyun
閱讀(1)
評論(0)
推薦(0)
摘要：
我們考慮這道題目要求我們在數列 \(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 閱讀全文
posted @ 2025-10-30 18:26
cogimyun
閱讀(0)
評論(0)
推薦(0)
摘要：
被 hack 的缺陷做法 我們考慮任意一個節點 \(i\) 如果已經是當前平均數最大值，那么必然不存在一個節點能夠使節點 \(i\) 的平均數更大?？紤]到節點 \(i\) 的父節點 \(j\) ，此時節點 \(j\) 的平均值一定 \(\le\) 節點 \(i\) 的平均值，所以此時可以通過節點 \ 閱讀全文
posted @ 2025-10-30 18:25
cogimyun
閱讀(3)
評論(0)
推薦(0)
摘要：
我們不妨先尋找 Alice 的出招序列 \(a\) 中的 \(a_i\) 與 Bob 的出招序列 \(b\) 中的 \(b_j\) 在什么時候會在同一局中出現，考慮 Alice 與 Bob 會進行 \(10^{100}\) 局游戲，所以可以認為是無限局游戲，那么只要 \(nx+i=by+j\) 存在 閱讀全文
posted @ 2025-10-30 18:25
cogimyun
閱讀(2)
評論(0)
推薦(0)
摘要：
我們不妨先維護出按照題目要求插入數據后的數列 \(a\)，很明顯，每次將 \(i\) 插入 第 \(p\) 位就是要找到數列 \(a\) 中的第 \(p-1\) 號元素，然后將 \(i\) 插入到 \(p-1\) 號元素與 \(p\) 號元素之間，這可以非常輕松的用平衡樹維護，具體來說就是將排名小于 閱讀全文
posted @ 2025-10-30 18:22
cogimyun
閱讀(1)
評論(0)
推薦(0)
摘要：
[列隊春游] 題解 題意 給定整數序列 \(a\)，對于隨機排列 \(p\)，求 \(\sum f_i\) 的期望。 對于位置 \(i\)，\(f_i\) 定義為最小的 \(x\)，滿足對于任意位置 \(j,1 \leq x \leq j \leq i\)，均有 \(a_{p_j} \leq a_{ 閱讀全文
posted @ 2025-10-30 18:21
cogimyun
閱讀(1)
評論(0)
推薦(0)
摘要：
題目描述 有一顆 \(n\) 個節點的樹，樹上的每一個點有一個爆炸半徑 \(r_i\)，每條邊 \((a_i,b_i)\) 有一個長度 \(c_i\)，一個炸彈 \(i\) 能引爆另一個炸彈 \(j\) 當且僅當 \(dis(i,j)\le r_i\)。 問題分析 我們可以建一個有向圖 \(G\)， 閱讀全文
posted @ 2025-10-30 18:20
cogimyun
閱讀(7)
評論(0)
推薦(0)
摘要：
一種比較暴力的方法。 考慮 \(n\le10,a_i\le10\) 所以陷阱的狀態僅 \(n\) 種，而且每 \(\operatorname{lcm}(a_0,a_1,...,a_{n-1})\) 個格子就是一個陷阱狀態的周期，我們不妨記 \(l=\operatorname{lcm}(a_0,a_1 閱讀全文
posted @ 2025-10-30 18:19
cogimyun
閱讀(3)
評論(0)
推薦(0)
摘要：
我們考慮一個字符串 \(s_i\) 與另外 \(n-1\) 個字符串均有 \(k\) 個字符不同，但一個一個字符串枚舉比較的時間復雜度顯然是 \(O(n^2m)\) 的。所以考慮更優的實現方法，我們發現 \(s_i\) 與其它字符串應該一共有 \((n-1)k\) 個字符不同，我們只需要用桶記錄每個 閱讀全文
posted @ 2025-10-30 18:17
cogimyun
閱讀(4)
評論(0)
推薦(0)
摘要：
前置知識 積性函數 顧名思義，積性函數是一類滿足 \(f(ab)=f(a)\times f(b)\) 的函數，當然 \(f(ab)=f(a)\times f(b)\) 是有成立條件的，它的成立條件是 \(\gcd(a,b)=1\)。 線性篩 可以用 \(O(n)\) 的時間復雜度篩出積性函數 \(f 閱讀全文
posted @ 2025-10-30 18:16
cogimyun
閱讀(3)
評論(0)
推薦(0)
摘要：
校內模擬賽上場切紫題 *800？ 我們不妨先考慮從 \(u\) 出發直接走到 \(v\) 的貢獻，此時對于 \(\forall i\in[u+1,v]\) 第 \(i\) 堆石頭數量都會加一。接下來我們考慮在從 \(u\) 走到 \(v\) 的過程中不是直接走到的，那么走法無非三種： 走到 \(u\ 閱讀全文
posted @ 2025-10-30 18:15
cogimyun
閱讀(4)
評論(0)
推薦(0)
摘要：
我們首先考慮葉節點 \(u\)，我們必然要向 1 到 \(x\) 的鏈加上一個權值 \(c\in[l_u,r_u]\)，不難發現，由于對一個鏈加上的權值從根到葉節點滿足 \(c_1\le c_2\le c_3\le ...\le c_k\)，那么 \(c\) 取最大值 \(r_u\) 自然不劣。接下 閱讀全文
posted @ 2025-10-30 18:14
cogimyun
閱讀(1)
評論(0)
推薦(0)
摘要：
考慮斐波那契數 \(fib_i\) 具有性質 \(fib_i=fib_{i-1}+fib_{i-2}\)，又考慮到相鄰塊的構成字母不同，所以我們不難想到，對于目前剩余數最大的字母 \(x\) 來說，我們應該用 \(x\) 來形成現在最大的斐波那契數 \(fib_i\)，否則非常明顯的是，如果不這么干 閱讀全文
posted @ 2025-10-30 18:11
cogimyun
閱讀(1)
評論(0)
推薦(0)
浙公網安備 33010602011771號