--- tags: 成大高階競技程式設計 2020 --- # 2020 高階競程 Contest #7 - 題解 ## [Digital Firends 3](https://judge.csie.ncku.edu.tw/problems/72) - Task Provider: raiso - Task Setter: raiso ### 首殺 team20_23 (00:06) ### 解法說明 這題就是一棵樹去遍歷,以 $k$ 開始當作樹根,找到每個節點的父節點,就結束了。 這題的考點還有一個就是會使用輸入輸出加速,這樣你就成功了! ### 標準程式 :::spoiler ```cpp #include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 1; int vis[maxn]; set<int> lk[maxn]; queue< pair<int, int> > Q; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, q, k; cin >> n >> m >> q >> k; for(int i = 0; i <= n; i++) vis[i] = -1; for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; lk[a].insert(b); lk[b].insert(a); } Q.push(make_pair(k, k)); //(pre, tar) while(!Q.empty()) { auto nw = Q.front(); Q.pop(); int tar = nw.second; int pre = nw.first; if(vis[tar] != -1) continue; vis[tar] = pre; for(auto i: lk[tar]) if(vis[i] == -1) Q.push(make_pair(tar, i)); } for(int nw,i = 0; i < q; i++) { cin >> nw; cout << (i==0? "": " ") << vis[nw]; } cout << endl; return 0; } ``` ::: ## [藍的競程之旅--欸可是 our](https://judge.csie.ncku.edu.tw/problems/73) - Task Provider: Ian - Task Setter: Ian ### 首殺 team20_18 (00:07) ### 解法說明 簡單來說是做前綴和,在提示中有提到 xor 其實是在數某個 bit 的 1 到底出現過奇數次還是偶數次,也就是說 xor 運算有各種有的沒的交換結合率,並且 $(a \oplus b \oplus c \oplus d) \oplus (a \oplus b) = c \oplus d$ 也就是說可以透過再 xor 運算一次逆運算出 $c \oplus d$ 的結果 定義 $a \oplus \oplus b = X_{a} \oplus X_{a+1} \oplus ... \oplus X_{b}$ $(0 \oplus \oplus b) \oplus (0 \oplus \oplus a-1)$ 其實就等於 $a \oplus \oplus b$ 也就是消去掉 $0 \oplus \oplus a-1$ 的部分 ### 標準程式 :::spoiler ```cpp #include <bits/stdc++.h> using namespace std; int data[100010]; int quian[100010]; int main() { int n, m, i, j, k; quian[0] = 0; cin >> n >> m; for (i = 0; i < n; i++) { cin >> data[i]; } for (i = 1; i <= n; i++) { quian[i] = quian[i - 1] ^ data[i - 1]; } int a, b; while (m--) { cin >> a >> b; cout << (quian[b] ^ quian[a - 1]) << endl; } return 0; } ``` ::: ## [次小生成樹](https://oj.leo900807.tw/problems/74) - Task Provider: MiohitoKiri5474 - Task Setter: MiohitoKiri5474 ### 首殺 team20_23 (01:24) ### 解法說明 次小,代表權重和為第二小 所以觀察一下剩下還沒有用到的邊,檢查這個邊加進去現有的 MST 中,所形成的環拿掉最小的邊的權重和,是否為除了 MST 以外、最小的生成樹 所以步驟會像是這樣: 1. 做 MST 2. 對 MST 做倍增(或剖分,反正能用來找 LCA 的東西皆可) 3. 查詢沒有用到的點鐘, $w_i - LCA ( u_i, v_i )$ 的最小值 另外 $LCA ( u_i, v_i )$ 是代表在 MST 上,$u_i, v_i$ 的路徑上所經過的邊的最大值 dp 表單的 first 就是存標準倍增法的節點 而 second 是存點 $i$ 到第 $2 ^ {k - 1}$ 個祖先之間,以及 $2 ^ {k - 1}$ 的祖先到 $2 ^ { k }$ 之間,最大的邊 所以倍增轉移式如下 $$dp[i][k].first = dp[dp[i][k - 1].first][k - 1].first$$ $$dp[i][k].second = \max ( dp[i][k - 1].second, dp[dp[i][k - 1].first][k - 1].second )$$ ### 標準程式 :::spoiler ```cpp // by. MiohitoKiri5474 #include<bits/stdc++.h> using namespace std; #define pb push_back #define INF 0x3f3f3f3f #define maxN 200005 #define maxLog 20 typedef pair < int, int > pii; #define F first #define S second struct bri{ int u, v, w; }; inline bool cmp ( bri a, bri b ){ return a.w < b.w; } vector < bri > edges; vector < pii > mst[maxN]; int ma, dis[maxN], n, D[maxN]; pii dp[maxN][maxLog]; vector < int > LOG; inline void Init ( void ){ for ( int i = 0 ; i < maxN ; i++ ) dis[i] = i; } inline int find ( int d ){ return dis[d] == d ? d : dis[d] = find ( dis[d] ); } inline void Union ( int a, int b ){ dis[find ( a )] = find ( b ); } inline bool same ( int a, int b ){ return find ( a ) == find ( b ); } inline void dfs ( int d, int p, int dep ){ D[d] = dep++; dp[d][0].F = p; for ( auto i: mst[d] ){ if ( i.F == p ) continue; dp[i.F][0] = pii ( d, i.S ); dfs ( i.F, d, dep ); } } inline void buildLCA ( void ){ memset ( dp, -1, sizeof dp ); memset ( D, 0, sizeof D ); dfs ( 0, -1, 0 ); for ( int k = 1 ; k < maxLog ; k++ ){ for ( int i = 0 ; i < n ; i++ ){ if ( dp[i][k - 1].F == -1 ) continue; dp[i][k].F = dp[dp[i][k - 1].F][k - 1].F; dp[i][k].S = max ( dp[i][k - 1].S, dp[dp[i][k - 1].F][k - 1].S ); } } } inline void findLCA ( int x, int y ){ if ( D[x] < D[y] ) swap ( x, y ); for ( int i = maxLog - 1 ; i >= 0 ; i-- ){ if ( dp[x][i].F != -1 && D[dp[x][i].F] >= D[y] ){ ma = max ( ma, dp[x][i].S ); x = dp[x][i].F; } } if ( x == y ) return; for ( int i = maxLog - 1 ; i >= 0 ; i-- ){ if ( dp[x][i].F != dp[y][i].F ){ ma = max ( ma, max ( dp[x][i].S, dp[y][i].S ) ); x = dp[x][i].F, y = dp[y][i].F; } } ma = max ( ma, max ( dp[x][0].S, dp[y][0].S ) ); } int main(){ ios::sync_with_stdio ( false ); cin.tie ( 0 ); cout.tie ( 0 ); int m, t = 1, ans, swp = 0, u, v, w; vector < int > unUsed; for ( int i = 0 ; i < maxLog ; i++ ){ LOG.pb ( t ); t <<= 1; } t = 1; cin >> n >> m; Init(); ans = INF; ma = -1; for ( int i = 0 ; i < m ; i++ ){ cin >> u >> v >> w; edges.pb ( bri { u, v, w } ); } sort ( edges.begin(), edges.end(), cmp ); for ( int i = 0 ; i < m ; i++ ){ if ( same ( edges[i].u, edges[i].v ) ){ unUsed.pb ( i ); continue; } Union ( edges[i].u, edges[i].v ); mst[edges[i].u].pb ( pii ( edges[i].v, edges[i].w ) ); mst[edges[i].v].pb ( pii ( edges[i].u, edges[i].w ) ); swp += edges[i].w; } buildLCA(); for ( auto i: unUsed ){ ma = -1; findLCA ( edges[i].u, edges[i].v ); ans = min ( ans, edges[i].w - ma ); } cout << ans + swp << '\n'; } ``` ::: ## [丸亀製麺買一送一](https://oj.leo900807.tw/problems/75) - Task Provider: ys - Task Setter: ys ### 首殺 team20_05 (00:16) ### 解法說明 - 令 $x$ 為 $m$ 個人過來**前**,桌子上目前**佔最多**人的人數 - 令 $k$ 為題目要求的最多人的那桌的**最小**解 若先去坐 $x$ 人的那個桌子,$k$ 會變大,所以 $m$ 個人應先分配到其他桌子上 於是求除了 $x$ 人的桌子外,還**剩下**多少位置(`rem`) ```cpp for (int i = 0; i < N; i++) rem += x-a[i]; ``` 若 $m \le \text{rem}$ 則顯然 $k = x$ 若 $m > \text{rem}$ 就將部份人分配到剩下的位置中(此時桌子人數都為 $x$), 接著將剩餘的人 $(m-\text{rem})$ 平均分配到每張桌子上,$k = x + \lceil {m - \text{rem}\over N} \rceil$ ### 標準程式 :::spoiler ```cpp #include<bits/stdc++.h> using namespace std; int const maxN = 110; int N, m, a[maxN]; int main() { scanf("%d%d", &N, &m); for(int i = 0; i < N; i++) scanf("%d", &a[i]); int x = *max_element(a, a+N), rem = 0; // remainder for(int i = 0; i < N; i++) rem += x-a[i]; if(m > rem) printf("%d", x + (m-rem)/N + !!((m-rem)%N)); else printf("%d", x); return 0; } ``` ::: ## [【潤羽るしあ】新衣装と新ゲーム【ホロライブ】](https://judge.csie.ncku.edu.tw/contests/11/problems/76) - Task Provider: leo900807 - Task Setter: leo900807 ### 首殺 -- (-:-) ### 解法說明 #### Subtask 1 $P^m_n$ 暴力匹配,每架飛機都匹配一個機場,看是否能降落,共 $P^m_n$ 種可能,最後取 $\max$ 。 #### Subtask 2 $O(NM)$ 將每架飛機與機場,視為二分圖兩邊的點,對於每架飛機,將其與其航程內所有機場連邊,最後對這張圖做最大匹配即可。 ### 標準程式 :::spoiler ```cpp #include <iostream> #include <utility> #include <bitset> #include <vector> #define x first #define y second using namespace std; pair<int, int> p[1001], a[1001]; vector<int> v[1001]; bitset<1001> vis; int mp[1001], mq[1001]; bool matching(int u){ vis[u] = 1; for(int i : v[u]) if(!mq[i] || !vis[mq[i]] && matching(mq[i])) return mq[mp[u] = i] = u, 1; return 0; } int dis2(pair<int, int> a, pair<int, int> b){ return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); } int main() { int n, m, d[1001], cnt = 0; cin >> n >> m; for(int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y >> d[i]; for(int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(dis2(p[i], a[j]) <= d[i] * d[i]) v[i].push_back(j); for(int i = 1; i <= n; i++) if(vis.reset(), matching(i)) cnt++; cout << cnt << "\n"; for(int i = 1; i <= n; i++) if(mp[i]) cout << i << " " << mp[i] << "\n"; } ``` ::: ## [快晴](https://oj.leo900807.tw/problems/77) - Task Provider: ys - Task Setter: ys ### 首殺 team20_12 (02:17) ### 解法說明 顯然這是一種找**最短路徑**的問題,當 $K = 1$ 時,直接用 BFS 算出起點到終點的最短路徑。 而 $K > 1$ 時,一個位置 $(a, b)$ 可在 $1$ 秒內飛到 $j \le K$ 遠的位置 $(na, nb)$: ```cpp while(q.size()) { auto [a, b] = q.front(); q.pop(); for(int i = 0; i < 4; i++) // 方向 i for(int j = 1; j <= K; j++) { int na = a + j*da[i], nb = b + j*db[i]; // j 單位遠的下個位置 if(maze[na][nb] != '.') break; // 該方向中途遇到障礙物 if(vis[na][nb]) continue; q.push({na, nb}); t[na][nb] = t[a][b] + 1; // 原位置秒數加 1 秒 vis[na][nb] = true; } } ``` 這樣複雜度為 $O(N\cdot M \cdot K)$,若飛行途中都沒遇到障礙物,則會 TLE 仔細觀察**同個方向**飛行時無障礙物的狀況, 若下個位置 $(na, nb)$ 到達時間較小,那麼從 $(na, nb)$ 開始飛會比較省時, 於是同個方向的搜尋可提早結束: ```cpp if(t[na][nb] < t[a][b] + 1) break; ``` 複雜度為 $O(N \cdot M)$ ### 標準程式 :::spoiler ```cpp #include<bits/stdc++.h> using namespace std; int const maxN = 1e3 + 10; int da[] = {1, -1, 0, 0}; // direction int db[] = {0, 0, -1, 1}; int N, M, K, a0, b0, a1, b1, t[maxN][maxN]; // t := time char maze[maxN][maxN]; bool vis[maxN][maxN]; // vis := visited int main() { scanf("%d%d%d", &N, &M, &K); for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) cin >> maze[i][j]; scanf("%d%d%d%d", &a0, &b0, &a1, &b1); queue<pair<int, int>> q; q.push({a0, b0}); memset(t, 0x3f, sizeof t); // 初始無限大 memset(vis, false, sizeof vis); t[a0][b0] = 0; vis[a0][b0] = true; while(q.size()) { auto [a, b] = q.front(); q.pop(); for(int i = 0; i < 4; i++) for(int j = 1; j <= K; j++) { int na = a + j*da[i], nb = b + j*db[i]; if(maze[na][nb] != '.') break; if(t[na][nb] < t[a][b] + 1) break; if(vis[na][nb]) continue; q.push({na, nb}); t[na][nb] = t[a][b] + 1; vis[na][nb] = true; } } printf("%d\n", vis[a1][b1]? t[a1][b1] : -1); return 0; } ``` ::: ## [增殖序列](https://judge.csie.ncku.edu.tw/contests/11/problems/78) - Task Provider: [TIOJ 2005](https://tioj.ck.tp.edu.tw/problems/2005) - Task Setter: leo900807 ### 首殺 -- (-:-) ### 解法說明 #### Subtask 1 $O(n)$ 不會超出 long long 範圍,直接做就好。 #### Subtask 2 $O(n)$ 由題目敘述可以導出遞迴式 $a_n=\begin{align}\begin{cases}1 & ,\text{ if } n=1\\a_{n-1}\times10^{\lfloor\log_{10}{n}\rfloor+1}+n & ,\text{ if }n>1\end{cases}\end{align}$ 那就直接 $O(n)$ 做,要記得 $\mod{m}$。 #### Subtask 3 $O(lg\ N)$ 這種線性遞迴的題目,就會想到可以用矩陣快速冪來優化,但是 $10^{\lfloor\log_{10}{n}\rfloor+1}$ 該如何處理呢? 不妨將其拆成 $0\sim9,10\sim99,100\sim999,\cdots$ 並分開進行矩陣快速冪,就能將 $10^{\lfloor\log_{10}{n}\rfloor+1}$ 視為常數,而矩陣的形式如下: $$ A=\left[\begin{matrix}10^{\lfloor\log_{10}{n}\rfloor+1} & 1 & 0\\0 & 1 & 1\\0 & 0 & 1\end{matrix}\right],B=\left[\begin{matrix}a_n\\n\\1\end{matrix}\right] $$ 那麼 $$ AB=\left[\begin{matrix}a_{n+1}\\n+1\\1\end{matrix}\right] $$ 因此一開始若將 $B$ 設為 $\left[\begin{matrix}0\\1\\1\end{matrix}\right]$ ,那麼 $a_n=A^nB$ 接著只要用上述的方法分段快速冪就可以得到答案了,要記得過程中都要 $\mod{m}$ ### 標準程式 看起來很亂,其實主要都是矩陣運算,實際上程式碼不長 :::spoiler ```cpp #include <iostream> #include <cmath> using namespace std; int main() { long long t, n, m, lim, a[3][3], b[3], tmp[3][3], x; cin >> t; while(t--){ cin >> n >> m; x = log10(n) + 1; lim = 1; while(x--) lim *= 10; b[0] = 0, b[1] = 1, b[2] = 1; for(long long mul = 10; mul <= lim; mul *= 10){ a[0][0] = mul, a[0][1] = 1, a[0][2] = 0; a[1][0] = 0, a[1][1] = 1, a[1][2] = 1; a[2][0] = 0, a[2][1] = 0, a[2][2] = 1; x = min(mul - 1, n) - mul / 10 + 1; while(x){ if(x & 1){ for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++){ tmp[i][j] = 0; for(int k = 0; k < 3; k++) tmp[i][j] = (tmp[i][j] + a[i][k] * b[k] % m) % m; } for(int i = 0; i < 3; i++) b[i] = tmp[i][0]; } for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++){ tmp[i][j] = 0; for(int k = 0; k < 3; k++) tmp[i][j] = (tmp[i][j] + a[i][k] * a[k][j] % m) % m; } for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) a[i][j] = tmp[i][j]; x >>= 1; } } cout << b[0] << "\n"; } } ``` :::