建中資訊校內賽複賽題解

## 建中資訊校內賽複賽題解 by 8e7, FHVirus and Jass --- ## A. 只走一次「你是得吧」—WayneYan ---- ### Subtask 1/3/4: $N, Q \leq 2000$ ---- 考慮$LCA$的暴力做法。讓詢問的兩個點先到同一深度，之後同時往父節點爬。紀錄每條邊是否有被走過，最後答案為$路徑長度 - 標記的邊數$，複雜度$O(NQ)$。 ---- ### Subtask 2: 對於每個城市最多只有兩條道路連接該城市和其他城市 ---- 上述條件為: 每個節點的最大度數(degree)為$2$，這樣的圖，加上了連通、無環的條件，一定是一條鏈。可以把這條鏈當成一個序列來看，那麼一條路徑就是這個鏈上的區間。將節點依照鏈上的位置重新編號，把走過的節點標記起來，就可以用線段樹或是BIT + set等方法解決。 ---- ### Subtask 5: 無其他限制 ---- 經典梗。考慮兩點往 LCA 走時，每次都會重複經過被標記的點。想辦法維護每個「走過的點的連通塊」深度最小的節點，每次走進一個連通塊就跳到最上面。維護連通塊→並查集！ ---- 每次從某個節點 $u$ 往上走到 $p$ 的時候，如果 $u$ 還沒被標記，就標記起來，並和 $p$ 所在連通塊合併，再往上跳到頂。每條邊只會被合併掉一次，均攤複雜度 $O(n \alpha(n))$ ---- ### 實作細節實際上並不用求 LCA ，只要每次看比較深的點並往上走即可。 ```cpp= for(int a, b, i = 1; i <= Q; ++i){ cin >> a >> b; int ans = 0; while(a != b){ if(dep[a] < dep[b]) swap(a, b); if(!vis[a]) ans += cost[a]; vis[a] = true; a = par[a]; } cout << ans << '\n'; } ``` ---- 另解: 樹鏈剖分 (毒瘤) --- ## B. 動態資料結構「為了繼續幫助孟嘗君選賢與能，馮諼出了一道會用到傅立葉轉換的題目，而來應徵食客的人全部都被嚇的「咻」一聲跑走了，因此有了『一傅眾咻』的說法。」—ㄌㄓㄒ題目：SeanLiu 題敘：SeanLiu ---- 小抱怨，好好判掉 Subtask 很難嗎？只要 `if(type != 3) return 0;` 就好了耶 owo ---- ### Subtask 1: 只有 `3` 這種運算每個物品的動能不會改變 -> 預處理 + 前綴和! ---- ### Subtask 2: $NQ \leq 10^6$ 暴力做，每次詢問的時候一個一個算。 ---- ### Subtask 3: 只有 `1`，`3` 兩種運算 ![](https://i.imgur.com/7f6FpAg.jpg) ---- 假設原本區間$l, r$的物品質量和動能分別為$m_l, m_{l+1}, ..., m_r$跟$v_l, v_{l+1}, ..., v_r$。那麼當質量改變$x$時，動能總和會改變$xv_l ^ 2 + xv_{l+1} ^ 2 + ... + xv_r ^ 2 = x \sum_{l \leq i \leq r} v_i ^ 2$。用線段樹維護每個區間的$v_i ^ 2$總和與動能總和，支援區間修改，區間求和操作! ---- ### Subtask 4: 只有 `2`，`3` 兩種運算，$m_i = 1$ ---- 當速度改變$x$的時候，速度平方由$v^2$變為$(v+x)^2$，變化量$x^2 + 2vx$。用線段樹維護每個區間的$v_i$與$v_i^2$總和，支援區間修改，區間求和操作! ---- ### Subtask 5: 只有 `2`，`3` 兩種運算 ---- 和前面一樣，只是要多維護$m_i, mv_i$。以下就直接講整題做法 ---- ### Subtask 6: 無其他限制 ---- ### 整體式子對每個線段樹維護五個變數 $m_i, v_i, mv_i, v^2_i, mv^2_i$ 其中 $m_i, v_i$ 是基礎的區間加值分別考慮兩種操作 ---- ### 區間質量 `+= k` - $\sum{m_i v_i} += \sum{(m_i + k)v_i - m_i v_i} = k \sum{ v_i }$ - $\sum{m_i (v_i)^2} += \sum{(m_i + k)v_i^2 - m_i v_i^2} = k \sum{ v_i^2 }$ ---- ### 區間速度 `+= k` - $\sum{v_i^2} += \sum{ (v_i + k)^2 - v_i^2} = \\ \sum{ 2kv_i + k^2} = (r-l+1)k^2 + 2k \sum{ v_i }$ - $\sum{m_i v_i} += \sum{m_i(v_i + k) - m_i v_i} = k \sum{ m_i }$ - $\sum{m_i (v_i)^2} += \sum{m_i(v_i + k)^2 - m_i v_i^2} \\ = \sum{ m_i(2kv_i + k^2) } = 2k \sum{ m_i v_i } + k^2 \sum{ m_i }$ ---- ### 維護資訊 - 懶標 $m_i, v_i$，順序：兩者先皆可（想一下） - 懶標下推的時候互相獨立 - 修改節點資訊的時候要注意順序！ - 線段樹實作上行數：官解 60 行（稍慢），另解 90 行（較快） - 實際上就是普通的區間加值區間和線段樹＋上面的式子 ---- ### 動態資料結構 Kinetic heater，在 TOI 2021 選訓營裡定下了「模考成績排名第四的國手要實做出來」的規則，最後由 `Wiwiho` 獲得這個難得的機會。聽說要寫 400 行左右。有興趣的歡迎去找 `AY`。 --- ## C. 交替路徑「TOI 初選是一場有二十題的比賽」—王品庠題目：FHVirus 題敘：FHVirus ---- ### 超多 Subtask - 怎麼樣找到最有效率的 Subtask 撈分 - 怎麼從 Subtask 邁向正解 ---- ### Subtask 的意義 - $w_i = 1$ ：不帶權 - $c_i = i$ ：所有邊都不同顏色→忽略顏色限制！ ---- ### Subtask 1: $w_i = 1, c_i = i$ 全點對： - 不帶權 - 最短~~交替~~路徑 - →每個點做一次 BFS！ ---- ### Subtask 2: $n \le 300, c_i = i$ 全點對： - 帶權 - 最短~~交替~~路徑 - →每個點做一次 Dijkstra $O(VE \log V)$！ - →或是 Floyd-Warshall 也可以！ ---- ### Subtask 3: $c_i = i$ 全點對： - 帶權 - 最短~~交替~~路徑 - →Floyd-Warshall 23 分到手！ - Dijkstra $O(VE \log V)$ 會被卡掉耶…… ---- ### 接下來呢？假設你拿到 FW 23 分了…… - 拿了就跑（經濟又實惠） - 繼續觀察，想辦法做下去 ---- ### Subtask 4: $n \le 100, c_i \le 5$ 開始有顏色限制了！重點觀察： - 想要維護最短路的末端（兩頭）顏色，這樣 Dijkstra (FW) 在鬆弛（合併）的時候才可以處理…… - 顏色數量很少…… - 能不能對每一個點都紀錄各種顏色結尾的最短路？ - 建模！每個點變成五個點，分別代表以不同顏色結尾的路徑！ ---- ### 在繼續之前顏色變多了！不能一個一個維護了，怎麼辦？ - 真的有必要維護這麼多顏色嗎？ - 考慮 `i -> j` 是一條最短交替路徑，現在我想要從 `j` 延伸出去（鬆弛），我一定是拿這條最短的嘛！ - 除非某條邊 `(j, k)` 的顏色和 `i -> j` 的結尾顏色一樣，那要怎麼做？ - 這個時候一定是拿「顏色不一樣的次短交替路徑」！還有其他狀況嗎？ - 沒有！那就做完了！ ---- ### 邁向正解 - 紀錄「最短交替路徑」的長度及結尾顏色 - 紀錄「次短交替路徑」的長度及結尾顏色 - 鬆弛的時候好好更新兩種資訊！ - Floyd Warshall 要紀錄太多的狀況了（頭尾），不考慮（常數會爆炸大） ---- ### Subtask 5: $w_i = 1$ - 次小值＋BFS ---- ### Subtask 6: $n \le 300$ - 次小值＋Dijkstra ---- ### Subtask 7: 無其他限制 - Dijkstra 被卡了？ - 還記得[運送蛋餅](https://tioj.ck.tp.edu.tw/problems/2164)嗎？ - 當邊數量很大的時候，$O(V^3)$ 會比 $O(VE \log V)$ 還要好！ - AC！ ---- ### 實做細節 - 你就真的要紀錄有點多東西 - 也可以把最小值跟次小值當成不同點來想 ---- ### 卡掉帶 log Dijkstra ```cpp= // p: 邊編號，完全圖 // a: 權重 int p = 0; for(int i = 0; i < n; ++i) for(int j = i+1; j < n; ++j){ a[p] = pair<int, int>(j == i+1 ? 1 : kC - 2 * i, p+1); ++p; } ``` --- ## D. 函數愛蛋餅「蛋餅的code絕對不會有bug，有的話一定是測資錯了。」—pdpd123 題目：2qbingxuan 題敘：Jass ---- ### Subtask 1: $N\leq 800$ ---- 把 $f(1)$ 到$f(N)$都枚舉一遍，沒什麼好說的。 ---- ### Subtask 2: $N\leq 10^5$ 先轉換一下想法:我現在在一張有向圖上，其中$i$指向$f(i)$，我要找到指向$1$的節點是誰。這張圖只會是一堆有向環，找到$1$所在的環的大小，就能得到答案。 ---- 環可能會很大，若一格一格走會走不完。但若一次走很多格，不知道什麼時候要停下。怎麼辦? ---- 正解:大步小步走如果一次走$k$步，我只要知道$1$後面$k-1$個人是誰，就保證可以在繞完一圈後停下來。總詢問次數為$k+\frac{N}{k}$，$k$取$\sqrt N$時會有最小值$2\sqrt N$。 AC --- ## E. 花枝遊戲「我在看魷魚遊戲的時候，一直想著要怎麼把裡面的遊戲出成題目」—8e7 題目：8e7 題敘：8e7 ---- ### Subtask 1: $a_i \geq 0$ ---- 對於任意一對人，他們如果有決鬥過的話會有$\geq 0$的精彩度，所以讓他們決鬥一定不會比較差。因此，最佳解一定是讓所有人都互相決鬥一次。每次把最左邊的人跟剩下的人分開，然後淘汰左邊就能達到這個條件，總精彩度為$\sum_{1 \leq i < j \leq n} a_i a_j$。 ---- ### Subtask 2: $n \leq 10$ ---- 枚舉每次分界點跟最後留哪一邊，複雜度依實作不同而異，可能是$C_n$，也就是第$n$個卡特蘭數。 ---- ### Subtask 3: $n \leq 400, m = 0$ ---- 觀察: 任何時候剩下的人都是原本的子區間。而且，一個子區間只有一個可能的最佳解... DP!令 $dp[i][j]$ 代表從$[i, j]$的人裡面選到剩一個人的最佳解，最後要的答案就是$dp[1][n]$。 ---- 已知$dp[i][i] = 0$，轉移式: $dp[i][j] = max_{i \leq k < j}(cost(i, k, j) + max(dp[i][k], dp[k+1][j]))$，其中$cost(i, k, j)$是$[i, k], [k+1, j]$對決的總精彩度，為$\sum [i, k] * \sum [k+1, j]$，可以用前綴和在$O(1)$求出。總複雜度: $O(n^3)$ ---- ### Subtask 4: $n \leq 400$ ---- 我們把$m$組對決視為數線上的線段，可以發現，在刪除一邊的時候，那一邊的區間不能完全包含任何線段(否則那個對決就不會發生)。稍微修改一下$DP$式。保證在刪除一邊的時候那邊沒有包含區間就好，複雜度仍為$O(n^3)$ ---- ### Subtask 5: $n \leq 5000, m = 0$ ---- 流程圖: ![](https://i.imgur.com/h6Nv1U2.png) ---- ![](https://i.imgur.com/CM4MM8N.png) ---- 觀察上面的區間，一個區間裡的人會跟與他不同區間的每個人都決鬥一次! 而每個區間所「貢獻」到的精彩度就是$S*(T-S)$，其中$S$是該區間的數字總和，$T$是整個序列的數字和。最後答案就是每個區間貢獻的精彩度和$/2$。 ---- 考慮把序列分成子區間，只要這個分法有至少一個長度為$1$的區間，就存在一個安排比賽的方式達到這個結果。令$dp[0/1][i]$代表是否選過長度為$1$的區間，前$i$項的最佳分法。那麼 $dp[0/1][i] = max_{j<i}(dp[0/1][j] + F(j+1, i))$，另外$dp[1][i] = max(dp[1][i], dp[0][i-1] + F(i, i))$ ---- ### Subtask 6: $n \leq 5000$ ---- 和前面一樣，加上限制了之後怎麼辦? 在轉移$j->i$的時候，實際的意義是把$[j, i]$分在同一個區間，而不能有任何一個區間$[l, r]$使$j \leq l < r \leq i$。對於每個$i$，考慮他最左邊的轉移點$l_i$，那麼$l_i$會是單調遞增的! 加上這個限制再DP就好了w ---- Code: ~~~cpp //Challenge: Accepted #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <utility> #include <assert.h> using namespace std; void debug() {cout << endl;} template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);} template <class T> void pary(T l, T r) { while (l != r) {cout << *l << " ";l++;} cout << endl; } #define ll long long #define ld long double #define maxn 5005 #define mod 1000000007 #define pii pair<int, int> #define ff first #define ss second #define io ios_base::sync_with_stdio(0);cin.tie(0); const ll inf = 1LL<<60; ll a[maxn], pref[maxn], dp[2][maxn]; int lim[maxn]; inline ll subseg(int l, int r) { // [l, r] return pref[r] - pref[l-1]; } int main() { io int t; cin >> t; while (t--) { for (int i = 0;i < maxn;i++) a[i] = 0, pref[i] = 0, dp[0][i] = dp[1][i] = 0, lim[i] = 0; int n, m; cin >> n >> m; for (int i = 1;i <= n;i++) { cin >> a[i]; pref[i] = a[i] + pref[i-1]; } ll tot = pref[n]; for (int i = 0;i < m;i++) { int u, v; cin >> u >> v; lim[v] = max(lim[v], u); } for (int i = 1;i <= n;i++) lim[i] = max(lim[i], lim[i-1]); dp[1][0] = -inf; for (int i = 1;i <= n;i++) { dp[0][i] = dp[1][i] = -inf; for (int j = i - 1;j >= lim[i];j--) { ll s = subseg(j + 1, i); dp[0][i] = max(dp[0][i], dp[0][j] + s * (tot - s)); dp[1][i] = max(dp[1][i], dp[1][j] + s * (tot - s)); if (j == i - 1) { dp[1][i] = max(dp[1][i], dp[0][j] + s * (tot - s)); } } } cout << dp[1][n] / 2 << "\n"; } } /* 4 0 1 -2 3 5 */ ~~~ ---- ### Subtask 7: 無其他限制 ---- 以下令$p_i$為前$i$項的戰力值和。 DP式: $dp[i] = \max_{l_i \leq j < i}(dp[j] + (S - (p_i - p_j)) * (p_i - p_j))$ 整理一下: $dp[i] = \max_{l_i \leq j < i}(p_j(2p_i - S) - p_j ^ 2 + dp[j]) + Sp_i - p_i ^ 2$ ---- 令 $p_j = m, -p_j ^ 2 + dp[j] = k, 2p_i - S = x$，那麼 $dp[i] = \max_{l_i \leq j < i}(mx + k) + C$ 斜率優化! 但是斜率不單調，詢問不單調，線段會過期... ---- 考慮分塊做法: 把$[Bx, B(x+1) - 1]$的線段都存成一個凸包，在轉移的時候，如果轉移區間包含那一整塊就從凸包取極值，否則暴力做。左右兩邊最多各$B$個暴力轉移的，從一個凸包取極值的複雜度是$\log B$，總轉移時間為$2n(2B + \frac{n}{B}\log B)$，取$B = \sqrt{\frac{n \log n}{2}}$的話複雜度為$O(n \sqrt{n \log n})$。 ---- Code: ~~~cpp //Challenge: Accepted #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <utility> #include <assert.h> using namespace std; void debug() {cout << endl;} template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);} template <class T> void pary(T l, T r) { while (l != r) {cout << *l << " ";l++;} cout << endl; } #define ll long long #define ld long double #define mod 1000000007 #define pii pair<ll, ll> #define ff first #define ss second #define io ios_base::sync_with_stdio(0);cin.tie(0); const ll inf = 1LL<<60; const int maxn = 50005, bs = 600; struct hull{ vector<pii> v; ll val(pii p, ll x){return p.ff * x + p.ss;} void build(vector<pii> p) { sort(p.begin(), p.end()); for (auto l:p) { while (v.size() >= 2) { pii l1 = v[v.size()-2], l2 = v.back(); v.pop_back(); ll v1 = l2.ss-l1.ss, v2 = l.ss-l1.ss; v1 *= l1.ff - l.ff, v2 *= l1.ff - l2.ff; if (v1 < v2) { v.push_back(l2); break; } } v.push_back(l); } } ll query(ll x) { if (v.size() == 1) return val(v.back(), x); int l = 0, r = v.size() - 1; while (r - l > 1) { int m = (l + r) / 2; if (val(v[m], x) <= val(v[m+1], x)) l = m; else r = m; } return max(val(v[l], x), val(v[r], x)); } } conv[2][maxn / bs + 1]; ll a[maxn], pref[maxn], dp[2][maxn]; pii line[2][maxn]; int lim[maxn]; inline ll subseg(int l, int r) { // [l, r] return pref[r] - pref[l-1]; } int main() { io int t; cin >> t; while (t--) { int n, m; cin >> n >> m; for (int i = 0;i < maxn / bs + 1;i++) conv[0][i].v.clear(), conv[1][i].v.clear(); for (int i = 0;i <= n;i++) a[i] = 0, pref[i] = 0, dp[0][i] = dp[1][i] = -inf, lim[i] = 0; for (int i = 1;i <= n;i++) { cin >> a[i]; pref[i] = a[i] + pref[i-1]; } ll S = pref[n]; for (int i = 0;i < m;i++) { int u, v; cin >> u >> v; lim[v] = max(lim[v], u); } for (int i = 1;i <= n;i++) lim[i] = max(lim[i], lim[i-1]); dp[0][0] = 0; for (int i = 1;i <= n;i++) { ll x = 2 * pref[i] - S, y = S * pref[i] - pref[i] * pref[i]; int j = lim[i]; auto upd = [&] (int j) { ll s = subseg(j + 1, i); dp[0][i] = max(dp[0][i], dp[0][j] + s * (S - s)); dp[1][i] = max(dp[1][i], dp[1][j] + s * (S - s)); }; for (;j < i;j++) { if (j % bs == 0) break; upd(j); } for (;j + bs < i;j+=bs) { dp[0][i] = max(dp[0][i], conv[0][j/bs].query(x) + y); dp[1][i] = max(dp[1][i], conv[1][j/bs].query(x) + y); } for (;j < i;j++) upd(j); dp[1][i] = max(dp[1][i], dp[0][i-1] + a[i] * (S - a[i])); line[0][i] = {pref[i], -(pref[i]*pref[i]) + dp[0][i]}; line[1][i] = {pref[i], -(pref[i]*pref[i]) + dp[1][i]}; if (i % bs == bs - 1) { vector<pii> l1, l2; for (int j = i - bs+1;j <= i;j++) { l1.push_back(line[0][j]), l2.push_back(line[1][j]); } conv[0][i/bs].build(l1); conv[1][i/bs].build(l2); } //debug(dp[0][i], dp[1][i]); } cout << dp[1][n] / 2 << "\n"; } } /* 1 4 0 1 -2 -1 5 */ ~~~ ---- 其他: * 本題是 `TIOJ 1170` 的加強版，該題只要$O(n^3)$就能過，但是寫$O(n^2)$會超快。 * 可以用線段樹套動態凸包 / 時間線段樹套動態凸包做到$O(n \log^2 n)$ --- ## 暴力總分 - pA : $N, Q \le 2000$ 36 - pB : Only query, $NQ \le 10^6$ 17 - pC : FW 23 - pD : Brute force 36 - pE : 簡單性質 6 + 區間 DP 12 ![](https://i.imgur.com/G55HZSy.png)