Round prepared by rsabcmoi and tangent 2017年建中資訊校內第二次 模擬賽宇宙大題解 Round prepared by rsabcmoi and tangent
pA 2025. 反手無力 19分：大暴力(其實我也不知道怎麼暴力 49分：首先看完題敘就知道顯然有不動點。O(n)枚舉不動點 dp[x][y]:前x陣風左側merge了x個的話右側最多能merge幾個 => O(n^2 k)
pA 2025. 反手無力 把風倒著吹，一樣的DP=> O(nk)
pB 2026. 正手不精 19分：每次sort => O(q^2 log q) 每次nth_element => O(q^2)
pB 2026. 正手不精 19分：每次sort => O(q^2 log q) 每次nth_element => O(q^2) 49分：聽說你會treap(?
pB 2026. 正手不精 19分：每次sort => O(q^2 log q) 每次nth_element => O(q^2) 49分：聽說你會treap(? 聽說你會黑魔法(?
pB 2026. 正手不精 19分：每次sort => O(q^2 log q) 每次nth_element => O(q^2) 49分：聽說你會treap(? 聽說你會黑魔法(? 聽說你會priority_queue(?
pB 2026. 正手不精 19分：每次sort => O(q^2 log q) 每次nth_element => O(q^2) 49分：聽說你會treap(? 聽說你會黑魔法(? 聽說你會priority_queue(?
pB 2026. 正手不精 100分：離線倒著做，變成刪除 用linked-list維護當前排序好的數列 瓶頸只剩排序，可以用radix sort 或counting sort => O(c+q) priority_queue也有100分喔，總共只慢一秒而已(?
pC 2027. 腳步鬆散 19分：聽說你會寫程式(? 49分：考慮分治。最大值在左邊或在右 邊且是遞增的此時xor會在O(log C)個區間裡。
pC 2027. 腳步鬆散 19分：聽說你會寫程式(? 49分：考慮分治。最大值在左邊或在右 邊且是遞增的此時xor會在O(log C)個區間裡。聽說你會treap(?
pC 2027. 腳步鬆散 100分：可以發現剛剛的做法裡每次要查詢的O(log C)個區間都形如[x, x+2^k-1] 用堆式存儲的線段樹就可以O(1)定位到要查詢的區間=>O(n log n log c)
pD 2028. 反應遲鈍 100分：注意到威爾森定理提供 𝑖=1 𝑝−1 𝑖 =−1 (mod 𝑝) 多項式 𝑖=1 𝑝−1 (𝑥−𝑖) = −1 ,𝑖𝑓𝑥==𝑝 0,𝑒𝑙𝑠𝑒 可以表徵成 𝑥 𝑝−1 −1
pD 2028. 反應遲鈍 上式比較係數得到任意𝐾元子集積的和=0 也就是 𝑓 𝑃,𝑋,𝐾 +−𝑋𝑓 𝑃,𝑋,𝐾−1 =0 即 𝑓 𝑃,𝑋,𝐾 = (−𝑋) 𝐾