<style> .reveal .slides { text-align: left; font-size:35px } </style> # 2023 I2CP Mock Contest 2 分析及簡易題解 ---- ### Scoreboard  --- ## A. Triangle Intersection 給定 N 個三角形 每個三角形三點座標分別為 (0, y) ($x_1$, 0) ($x_2$, 0) 求幾個三角形有相交 ---- ### Hint - BIT 如果常數大極可能 TLE - 官解使用分治 ---- 三角形相交有兩種可能 - 第一個點 $y$ 座標相同 $y_a = y_a$ - 對於點 $a, b$，其第一個點 $y_a < y_a$，且第二三個點 $x_{b1} \ge x_{a2}$ 第一種情況應該隨便都可以判斷，第二種情況? ---- $y_a < y_a$ 與 $x_{b1}\ge x_{a2}$ 同時符合 即為逆序數對問題，第一個維度可以先排序，第二個維度使用分治/資料結構處理 如果會寫作業中的第一題理論上這題就會了 再提醒一次，資料結構解高機率 TLE (尤其沒有好好離散化、偷懶用 map 離散化) --- ## B. K-th Larger Same Factored 求出所有比 n 還要大且與 n 的質因數相同的數字中第 k 小的 ---- ### Hint 如果你是 WA 不知道錯哪，想一下以下可能是其中一個? - 溢位(相乘超過 long long 範圍) - 算到重覆數字 - 有多個相同質因數要去除 (n = 12 要從 6 開始窮舉) 驗題者全部都有錯以上其中一種情況 ---- ### 作法一 直接從所有的質因數乘積 ( 12 的質因數乘積是 6 而不是 12) 開始，每次乘上所有的質因數產生新的數字，之後每次選最小的，再重複乘上去直到大於 n 中第 k 小的為止，每次選最小的數字可以用 priority_queue 維護。 而記得如果乘到相同的數字只能算一次 ---- ### 作法二 如果好好觀察實驗會發現 每個質因數組合在 $10^{18}$ 內最多只會有 $3\cdot 10^5$ 個不同的數字 因此可以直接暴力遞迴求出同一個質因數集合下所有可能的數字 求出所有數字後 sort 一下求出第 k 小即可 ---- 判斷是否溢位可以用除法 x*y <= 1e18 if(1e18 / y <= x) //為 true 代表相乘沒有超過 1e18 --- ## C. Stand in a Line n 個人站在一排，給每個人分別的身高以及前面有幾個人比他高 還原出這 n 個人站的順序 (只需輸出身高即可) ---- 由於只需輸出升高，因此給定的順序不重要，不需要紀錄 index 可以發現可以放第一個的一定是前面沒有人比他高，或者是最矮的。而如果當前最矮的前面有人代表為 Impossible ---- 因此可以每次都放前面沒人比他高的，最矮的那個 放到最前面的位置，而對於還沒放且比他矮的人 可以把那些的比他高的數量 -1，因為已經當前這個人放過了 所以前面比他高的少一個，就把這些人數量 -1 ---- 而如果一開始把所有人照身高排序，我們可以維護一棵線段樹 每次把當前比他小的人數量都 -1，即為區間減值 每次減掉後，檢查有沒有人前面比他高的數量為 0 代表可以加進去考慮的人選 每個人只會變成 0 一次，因此可以暴力檢查線段樹是否有 0 均攤是好的 ---- 每個人往比他矮的區間加值一次，總共 $N$ 個人 總複雜度 $O(N\log N)$ --- ## D. Extended-Extended Euclidean Algorithm 給 $a,b,c,d$ 求出一組 $x,y,z$ 使得 $ax+by+cz = d$ 可以得知需要使用到拓展歐幾里得 ---- ### hint * 如果是對於拓歐沒有更進一步的想法的話，建議從式子下手經過移項或取公因等操作變成可以拓展的式子 * 記得 a,b,c,d 有 0 的情況，要好好處理 有四種不同的狀況，且皆為可以直接求解的 ---- ### 作法一 首先會有根據裴蜀定理的先備知識，會發現 $ax+by = c$ 的整數解其有解的充要且必要條件為 $gcd(a,b)|c$ 然後移項式子後可以把 $ax+by+cz = d$ 變成 $ax+by = d-cz = gcd(a,b) (可整除d-cz)$ ， 整除的關係所以將兩邊同乘$k$ ， 會得式 $akx+bky = kd-ckz = k*gcd(a,b)$ 而我們已知其中 $a,b,c,d$ 所以可以通過兩次拓展歐幾里得得到解，第一次得到倍數解$k,z$第二次得到解$x,y$，其中值得且需要注意的是$k$倍需要小心用法，輸出需要$*k$倍。 ---- 2023/04/05 新增證明以及核心作法，感謝 @Lutein 提供完整且好懂得思路 推成 $ax+by=d-cz=gcd(a,b)$ 後， 可用exgcd得到一組 $x_1$ , $y_1$ ，使得 $ax_1+by_1=gcd(a,b)$ ， 但這組解不能保證整數的 $z_1$ 存在， 所以需要再乘上一個 $k$ 後可以得到所有可能的解， $x_2=kx_1，y_2=ky_1$ $ax_2+by_2=d-cz_2=gcd(a,b)*k$ $=akx_1+bky_1=d-cz_2=gcd(a,b)*k$ 這時未知數是 $k$ 和 $z_2$ ， ---- 整理一下式子得到 $ax_2+by_2=d-cz_2=gcd(a,b)*k$ $cz_2+k*gcd(a,b)=d$ 這時候可以再用一次exgcd得到 $z_2$ 和 $k$ ， 最後再算出 $x_2=kx_1，y_2=ky_1$ ---- 提供作法一的核心code(大概) ```cpp g=exgcd(a,b,x1,y1); dd=exgcd(c,g,aa,k); aa*=d/dd;k*=d/dd; ``` ---- ### 作法二 移項式子後可以把 $ax+by+cz = d$ 變成 $ax+by = d-cz$ 而其中值域為$\leq 10^6$ 因此只需要枚舉$z$然後代入$a,b,c,d$後使用拓歐找到一組-合理解即可。 --- ## E. Homework and Another Operation - 區間反轉 - 區間移動 ---- ### 作法 [見講義](https://hackmd.io/@LeeShoWhaodian/BIT_PBDS_Treap#/3/54) --- ## F. Travel - 單點修改 - 詢問區間最大值位置(多個輸出最左邊的那個位置) ---- ### 作法 線段樹上二分搜 [見講義](https://hackmd.io/@LeeShoWhaodian/segment#/1/50) --- ## G. Preparing Problem 求出任兩個相異數字相乘的期望值 由於期望值可以化減成 $\frac{x}{y}$ 的形式 求 $x\cdot y^{-1} (\mod 10^9)$ 的結果 也就是 $x\cdot y$ 的模逆元 ---- 這題原本考點是[模逆元](https://hackmd.io/@LeeShoWhaodian/NumberTheory#/4) 但好像大家沒看懂題目QQ 在算 $N\cdot (N-1) /2$ 的模逆元時要記得先 mod 算任兩數相乘總和要 $O(N)$ $O(N^2)$ 會 TLE