# 2021 ICPC Taiwan Online Programming Contest 簡易題解 ## 簡單偏簽到 Olympic Ranking 簡單字串處理與求最大值。會建議自行實作一個 class ,實作 Comparable 的 interface ,並有一個以單一 String 為引數的建構子,方便每次讀入一行,就建構一筆資料,可參考 sample code 的寫法。 ## 簡單 Aliquot Sum 給定整數,判斷是否為虧數、盈數、完全數。將詢問上限看作 $N$ 的話,可作到 $O(N\log N)$, $O(N\sqrt{N})$ 也會過,但 $O(N^2)$ 將會超過時限。 如何做到 $O(N\sqrt{N})$ :觀察除了完全平方數之外,因數均成對出現。如果 $d$ 是 $n$ 的因數,則 $\frac{n}{d}$ 也是 $n$ 的因數,僅在 $d = \sqrt{n}$ 時需要特殊判定,因此只需要 $O(\sqrt{n})$ 便可以列舉所有 $n$ 的因數。 如何做到 $O(N\log N)$:利用類似 [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) 的方式進行計算。考慮一個整數 $d$ ,他會是 $2d,3d,\dots,kd,\dots$ 的因數,因此列舉 $d=1, \dots, N$ ($N=200000$) ,將 $2d, 3d, \dots, \left\lfloor\frac{N}{d}\right\rfloor d$ 這些對應的數字的 Aliquot Sum 加上 $d$,即可求出所有會被問到的 Aliquot Sum 。時間複雜度為 $O(\sum_{d=1}^{N}\frac{N}{d})=O(N\sum_{d=1}^{N}\frac{1}{d})$,透過調和級數 $\sum_{i=1}^x\frac{1}{i}=\ln x + O(1)$ 的性質,我們可以推出時間複雜度為 $O(N\log N)$。 ## 中偏易 A Sorting Problem 若將 index 和數字互換,得到一新陣列,題目即變成可交換相鄰兩項,要將 array 排序最少需要做幾次操作,此題即為經典的計算逆序數對數量,可使用 BIT 或 merge sort 在 $O(n \log n)$ 算出答案。 ## 簡單 Drunk Passenger 可以依據提敘寫出一個實作簡單的 Dynamic programming 演算法,或是推出答案之數學式子$\frac{n}{2n-2}$ 直接算答案。實作請參考範例解答。 ## 中偏難 Eatcoin $f(x)=\sum_{i=1}^x i^5$ $f(x)$會是一個六次方程式 可以把f(0)~f(5)算出來後用拉格朗日插值法或高斯消去法把方程式求出來。$x$ 由題目敘述可知不會太大,可透過迴圈逐一嘗試即可求出。 $y$ 則利用二分法跟大數即可解出,要注意使用 double 或是 64-bit 整數精確度不夠的問題。 ## 中偏難 Flip 先備知識,區間修改線段樹 類似題,動態區間最大連續和 使用線段樹,節點存的資訊如下 ``` cpp struct Node { int tg; // lazytag int l, r; // 區間左右界 long long ans; // 區間內的交替子陣列數量 int li, ri; // 延伸至左右的交替陣列長度 int ls, rs; // 最左右的值 } ``` 合併時交替陣列的數量為,左右數量相加以及跨越左右的數量,此部分可使用 lenL, lenR, Lval, Rval求出,若交界處值不同,跨越的交替陣列即為兩邊界的交替長度相乘,合併 function 如下 ``` cpp Node pull(Node l, Node r) { s p; p.l = l.l; p.r = r.r; p.ls = l.ls; p.rs = r.rs; p.tg = 0; if (l.rs == r.ls) { p.li = l.li; p.ri = r.ri; p.ans = l.ans + r.ans; return p; } p.ans = l.ans + r.ans + l.ri * r.li; p.li = (l.li == (l.r - l.l + 1) ? l.li + r.li : l.li); p.ri = (r.ri == (r.r - r.l + 1) ? r.ri + l.ri : r.ri); return p; } ``` 其餘部分套入區間反轉線段樹模板即可 ## 中偏難 Garden Park 先將邊排序,從小到大依序處理每條邊,建立一 DP 陣列紀錄,目前已每個點為結尾的遞增 path 數量,初始 DP 值皆為 1。 加入一條新的邊 (x, y) - DP[x] += DP[y] (走 y -> x) - DP[y] += DP[x] (走 x -> y) 另實作上須注意,若有重複的邊權需要做一些小小的處理,避免使用到相同邊權更新的 DP 值,可參考如下的 code ``` cpp #define F first #define S second map<int,ll>ans; // DP 陣列 map<int,vector<pair<int,int>>>mp; //index : 邊權值, value : 該權值所有邊的兩端點 for (auto &i : mp) { map<int,ll>chg; // 本次更動的 DP 值 for (auto &j : i.S) { if (chg.count(j.F)) { chg[j.F]++; } else { chg[j.F] = ans[j.F] + 1; } chg[j.F] += ans[j.S]; if (chg.count(j.S)) { chg[j.S]++; } else { chg[j.S] = ans[j.S] + 1; } chg[j.S] += ans[j.F]; } for (auto &i : chg) { ans[i.F] = i.S; } } ``` ## 難題 A Hard Problem - 先考慮沒有限制的版本, 可以發現每個 bit 都是獨立的, 因此可以將每個 bit 分開討論並把問題轉化為給一張圖, 把點分成兩組, 有些點已經分好組, 將沒有組別的點分組並讓邊兩端不同組的數量最少 - 轉化成 min cut 問題, 確定組別的邊連起點和終點跑一次 flow - 考慮限制們, 限制總共有兩種 - 某兩個點要同組, 就將兩點連一個無限大的邊 - 若跑出來的 cut 不是無限大, 代表沒有切到這條邊而使得你們位於同一側 - 某兩點 u 和 v 要不同組, 則嘗試 u 接起點 v 接終點, 或是 u 接終點 v 接起點, 接起來的邊邊權都無限大 - 若跑出來的 cut 不是無限大, 則沒有切到這些邊使得兩點分別在在不同組 - 總共最多有 q 條要相異的限制, 因此枚舉每一種接法並跑 flow 找最小值即可, 若跑出來的 cut 是無限大代表違反上述其中一項即沒有解, 時間複雜度為 $O(2^q \times FLOW(16 \times |V|, 16 \times |E|))$ ## 難題 ICPC Kingdom 關鍵字:Matroid Intersection 假設現在已經選了一些邊 第一個條件是 這些邊是一個森林 第二個條件是 存在一個匹配 使的每條邊都有一個工人可以修 假設現在新加一條邊 使得這條邊+原本的邊還是一個森林 我們稱這些邊的set為$S_A$ 那如果現在新加一條邊 使得第二個條件還是滿足 我們稱這些邊的set 為$S_B$ 然後這些待選邊集合是$S$ 已選邊集合是$G$ 現在 如果選了一條待選邊$u$進去 發現不滿足第一個條件 代表說我要從已選邊裡拿一條邊$v$出來才行 也就是那個環上的某條邊$v$ 那我們做一個路徑從$u$->$v$ 我發現如果選了一條待選邊$u_2$進去 發現不滿足第二個條件 代表我要從已選邊拿一條邊$v_2$出來 也就是走匹配擴充路徑從$u_2$能走到的某條邊$v_2$ 我們做一條路徑$v_2$->$u_2$ 那我們現在就是要找$S_A$的某個點到$S_B$的某個點 的最長路 權重在點上 且 $S$的點權為正 $G$的點權為負 然後將該條路徑上的點 原本在$S$拿到$G$ 原本在$G$拿到$S$ 因為每條路徑一定是一邊在$S$一邊在$G$ 且開頭結尾都在$S$ 所以交換後$G$的size +1 $S$的size-1 最多選n-1條邊所以上述的流程會執行n-1次 對於每次做最大匹配 $n*\sum x$ $O(nm^2)$ 找樹上環$O(nm)$ 最短路$O(n*m)$條邊$O(m)$個點 用bellman-ford$O(nm^2)$ $O(n^2m^2)$ 標程實際上很快 應該可以把n跟m都放大兩倍 這樣有一隊$AC$變$TLE$ ## 簽到題 - JavaScript 判斷兩個字串中是否純粹都是數字,如果是,那就轉成整數後相減,否則輸出 NaN 。