Round prepared by rsabcmoi and tangent

Presentation on theme: "Round prepared by rsabcmoi and tangent"— Presentation transcript:

1 Round prepared by rsabcmoi and tangent
2017年建中資訊校內第二次 模擬賽宇宙大題解 Round prepared by rsabcmoi and tangent

2 pA 反手無力 19分：大暴力(其實我也不知道怎麼暴力 49分：首先看完題敘就知道顯然有不動點。O(n)枚舉不動點 dp[x][y]:前x陣風左側merge了x個的話右側最多能merge幾個 => O(n^2 k)

3 pA 反手無力 把風倒著吹，一樣的DP=> O(nk)

4 pB 正手不精  19分：每次sort => O(q^2 log q) 每次nth_element => O(q^2)

5 pB 正手不精  19分：每次sort => O(q^2 log q) 每次nth_element => O(q^2) 49分：聽說你會treap(?

6 pB 正手不精  19分：每次sort => O(q^2 log q) 每次nth_element => O(q^2) 49分：聽說你會treap(? 聽說你會黑魔法(?

7 pB 正手不精  19分：每次sort => O(q^2 log q) 每次nth_element => O(q^2) 49分：聽說你會treap(? 聽說你會黑魔法(? 聽說你會priority_queue(?

8 pB 正手不精  19分：每次sort => O(q^2 log q) 每次nth_element => O(q^2) 49分：聽說你會treap(? 聽說你會黑魔法(? 聽說你會priority_queue(?

9 pB 2026. 正手不精 100分：離線倒著做，變成刪除 用linked-list維護當前排序好的數列
瓶頸只剩排序，可以用radix sort 或counting sort => O(c+q) priority_queue也有100分喔，總共只慢一秒而已(?

10 pC 腳步鬆散   19分：聽說你會寫程式(? 49分：考慮分治。最大值在左邊或在右 邊且是遞增的此時xor會在O(log C)個區間裡。

11 pC 腳步鬆散   19分：聽說你會寫程式(? 49分：考慮分治。最大值在左邊或在右 邊且是遞增的此時xor會在O(log C)個區間裡。聽說你會treap(?

12 pC 腳步鬆散   100分：可以發現剛剛的做法裡每次要查詢的O(log C)個區間都形如[x, x+2^k-1] 用堆式存儲的線段樹就可以O(1)定位到要查詢的區間=>O(n log n log c)

13 pD 2028. 反應遲鈍 100分：注意到威爾森定理提供 𝑖=1 𝑝−1 𝑖 =−1 (mod 𝑝) 多項式
𝑖=1 𝑝−1 (𝑥−𝑖) = −1 ,𝑖𝑓𝑥==𝑝 0,𝑒𝑙𝑠𝑒 可以表徵成 𝑥 𝑝−1 −1

14 pD 2028. 反應遲鈍 上式比較係數得到任意𝐾元子集積的和=0 也就是 𝑓 𝑃,𝑋,𝐾 +−𝑋𝑓 𝑃,𝑋,𝐾−1 =0 即
𝑓 𝑃,𝑋,𝐾 = (−𝑋) 𝐾