2021 ICPC Taiwan Online Programming Contest 簡易題解

# 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 。