110 學年度師大附中資訊學科能力競賽上機測驗題解

### 110 學年度師大附中資訊學科能力競賽 # 上機測驗題解 joylintp / WiwiHo ---  Virtual to LIVE (VTuber) joylintp ---- ### Virtual to LIVE 單推指數 $B = \max_{x \in v}\frac{c_x}{N}$ → $max_{x \in v}c_x = N$ 時 $B$ 有最大值 → 輸出 $N$ 個相同的名字時 $B=1$ 100 / 100 ---- ```cpp= #include<bits/stdc++.h> using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int N; cin >> N; while (N--) cout << "Ninomae Ina\'nis\n"; return 0; } ``` ---- ### Virtual to LIVE - 一些廢話 * 題本內只列出了 $15$ 個 VTuber * checker 內一共有 $51$ 個可以輸出的 VTuber * 輸出其中 $20$ 個 VTuber 拿到滿分會得到彩蛋 ![](https://i.imgur.com/vMIm2HQ.png) ---- ### Virtual to LIVE - 一些廢話拿到滿分的人輸出的 VTuber： * Ninomae Ina'nis：10 * Hoshimachi Suisei：3 * Nanashi Mumei：3 * Gawr Gura：2 * Kizuna AI：2 * Tokino Sora：2 ---  貪吃蛇 (Snake) WiwiHo ---- ## 貪吃蛇 - Subtask 2 蛇只會往同一個方向移動 → 在繞一圈回到原點前長度每次增加 $1$ → 撞到後長度固定為 $N$ → 第 $i$ 個答案為 $\min(N, i+1)$ 5 / 100 ---- ## 貪吃蛇 - Subtask 3 蛇只會往上或往下移動設目前長度為 $L$ → 若往前一步的反方向移動，則長度變為 $2$ → 否則長度變為 $\min(N, L+1)$ 7 / 100 ---- ## 貪吃蛇 - Subtask 4 使用 $N \times N$ 的陣列記錄每一格被蛇佔據的時間 → 若新走到的格子沒有被佔據則將該格的時間更新 → 若被佔據則掃過每個格子，將佔據時間比該格早的格子清空時間複雜度 $O(N^2M)$ 12 / 100 ---- ## 貪吃蛇 - Subtask 5 使用 $N \times N$ 的陣列記錄每一格被蛇佔據的時間將目前蛇佔據的格子用 queue 維護 → 若沒有被佔據則更新該格時間，並 push 進 queue → 若被佔據則一直 pop 到該格並同時清空格子時間複雜度 $O(N^2 + M)$ (12 + 21) / 100 ---- ## 貪吃蛇 - Subtask 6 ~~使用陣列記錄每一格被蛇佔據的時間~~ 使用 map 或 set 等資料結構維護時間複雜度 $O(M \log M)$ 100 / 100 ---- ```cpp= #include <bits/stdc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define mp(a, b) make_pair(a, b) #define F first #define S second using namespace std; using pii = pair<int, int>; int main(){ StarBurstStream int n, m, x, y; cin >> n >> m >> x >> y; x--; y--; string s; cin >> s; set<pii> st; st.insert(mp(x, y)); map<char, pii> dir; dir['R'] = mp(0, 1); dir['L'] = mp(0, -1); dir['U'] = mp(-1, 0); dir['D'] = mp(1, 0); queue<pii> q; q.push(mp(x, y)); for(char i : s){ x += dir[i].F; y += dir[i].S; x = (x % n + n) % n; y = (y % n + n) % n; if(st.find(mp(x, y)) != st.end()){ while(true){ pii tmp = q.front(); q.pop(); st.erase(tmp); if(tmp == mp(x, y)) break; } } st.insert(mp(x, y)); q.push(mp(x, y)); cout << q.size() << "\n"; } return 0; } ``` ---  入社手續 (Procedure) WiwiHo ---- ### 入社手續將文件間的關係建成一張有向圖 $G$：對於節點 $v$，若存在 $a_{u,j,k} = u$，則建一條邊 $(u,v)$ 由於文件不會循環，故 $G$ 為一張 DAG 其中邊數 $|E| = \Sigma C_{i,j}$，點數 $|V| = N$ ---- ### 入社手續 - Subtask 3 $K \le 1$ → 對於 $K = 0$ 的文件可以直接申請 → 對於 $K = 1$ 的文件 $u$，只須申請其中一份 $a_{u,1,j}$ → 求從各 $K=0$ 的文件到 $N$ 的最短路徑時間複雜度 $O(|E| + |V| \log |V|)$ 17 / 100 ---- ### 入社手續 - Subtask 4 $C_{u,j} = 1$ → 在申請 $u$ 之前需要先申請所有連到 $u$ 的文件 → 拓樸排序後計算每個節點的答案時間複雜度 $O(|E| + |V|)$ 26 / 100 ---- ### 入社手續 - Subtask 5 設 $dp[u]$ 為拿到第 $u$ 份文件的最早時間， * 初始化 $dp[u] = \infty$ * $dp[v]=\max_{1\leq i \leq K_v}\{\min_{1 \leq j \leq C_{v,i}} \{ dp[j] \}\} + T_v$ 更新 $N$ 輪後即可得到答案時間複雜度 $O(|V|(|E| + |V|))$ (9 + 12) / 100 ---- ### 入社手續 - Subtask 6 $G$ 為一張 DAG → 將 $dp[u]$ 的更新順序改為 $G$ 的拓樸排序時間複雜度 $O(|E| + |V|)$ 100 / 100 ---- ```cpp= #include <bits/stdc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define eb(a) emplace_back(a) using namespace std; typedef long long ll; const ll LLMAX = 1LL << 60; int main(){ StarBurstStream int n; cin >> n; vector<int> tm(n + 1); for(int i = 1; i <= n; i++) cin >> tm[i]; vector<vector<vector<int>>> a(n + 1); vector<vector<int>> g(n + 1); vector<int> deg(n + 1); for(int i = 1; i <= n; i++){ int K; cin >> K; a[i].resize(K); for(int j = 0; j < K; j++){ int c; cin >> c; a[i][j].resize(c); for(int k = 0; k < c; k++){ cin >> a[i][j][k]; g[a[i][j][k]].eb(i); deg[i]++; } } } queue<int> q; for(int i = 1; i <= n; i++){ if(deg[i] == 0) q.push(i); } vector<ll> dp(n + 1); while(!q.empty()){ int now = q.front(); q.pop(); for(auto& i : a[now]){ ll mn = LLMAX; for(int j : i){ mn = min(mn, dp[j]); } dp[now] = max(dp[now], mn); } dp[now] += tm[now]; for(int i : g[now]){ deg[i]--; if(deg[i] == 0) q.push(i); } } cout << dp[n] << "\n"; return 0; } ``` ---- ### 入社手續 - Extra 如果 $G$ 不是 DAG 要怎麼作？ ---  船帆 (Sail) WiwiHo ---- ### 船帆當角度為 $\theta$ 時成本為 $f(\theta)=L(a\sin\theta + b\cos\theta)$ ---- ### 船帆 - Subtask 2 若 $a = 0$ → $f(\theta) = b\cos\theta$ 若 $b = 0$ → $f(\theta) = a\sin\theta$ 可以直接使用反三角函數求出解 13 / 100 ---- ### 船帆 - Subtask 3 $a > b$，且 $\beta \approx \frac{\pi}{4}$ → $f(\theta)$ 在 $[\alpha, \beta]$ 會是遞增的 → 對 $\theta$ 二分搜 25 / 100 ---- ### 船帆 - Subtask 4 $a = b$ → $f(\theta)$ 最大值發生在 $\theta = \frac{\pi}{4}$ → 分別對最大值兩側二分搜，找出在 $[\alpha, \beta]$ 內的解 29 / 100 ---- ### 船帆 - Subtask 5 $f(\theta)$ 為一個中間高的單峰函數 → 三分搜找出 $f(\theta)$ 最大值 → 分別對最大值兩側二分搜，找出在 $[\alpha, \beta]$ 內的解 100 / 100 ---- ```cpp= #include <bits/stdc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; typedef long double ld; ld PI = acos(-1); double eps = 1e-8; double anseps = 1e-4; int L, a, b; ld c, alp, bt; ld f(ld x){ return L * (a * sin(x) + b * cos(x)); } void solve(){ cin >> L >> a >> b >> c >> alp >> bt; ld l = alp, r = bt; while(r - l > eps){ ld m1 = (l * 2 + r) / 3; ld m2 = (l + r * 2) / 3; if(f(m1) < f(m2)) l = m1; else r = m2; } ld mid = l; if(f(alp) - anseps <= c && c <= f(mid) + anseps){ l = alp, r = mid; while(r - l > eps){ ld m = (l + r) / 2; if(f(m) < c) l = m; else r = m; } if(abs(f(l) - c) <= anseps){ cout << fixed << setprecision(20) << l << "\n"; return; } } if(f(mid) + anseps >= c && c >= f(bt) - anseps){ l = mid, r = bt; while(r - l > eps){ ld m = (l + r) / 2; if(f(m) > c) l = m; else r = m; } if(abs(f(l) - c) <= anseps){ cout << fixed << setprecision(20) << l << "\n"; return; } } assert(false); } int main(){ StarBurstStream int T; cin >> T; while(T--){ solve(); } return 0; } ``` ---- ### 船帆 - 一元二次方程式解設垂直船桅長度為 $x$，則水平木桿長度為 $\frac{c - ax}{b}$ 列出關係式：$x^2 + (\frac{c - ax}{b})^2 = L^2$，求出 $x$ 後算出 $\theta$，取在 $[\alpha, \beta]$ 內的解即可 ---- ### 船帆 - 三角函數解疊合三角函數： $f(\theta) = L(a\sin\theta + b\cos\theta) = L\sqrt{a^2+b^2}\sin(\theta+\theta')$ （$\theta' = \arccos\frac{a}{\sqrt{a^2+b^2}}$）令 $\gamma = \arcsin\frac{c}{L\sqrt{a^2+b^2}}$，則兩組解分別為 $\gamma - \theta'$ 及 $\pi - \gamma - \theta'$，取在 $[\alpha, \beta]$ 內的解即可 ---  手鍊 (Bracelet) joylintp ---- ### 手鍊 - Subtask 2 列出每顆珍珠的顏色枚舉 $l$，在移動 $r$ 的過程中同時檢查手鍊是否合法時間複雜度 $O((\Sigma d_i)^2)$ 9 / 100 ---- ### 手鍊 - Subtask 3 設 $l$ 在第 $L$ 段，$r$ 在第 $R$ 段，枚舉 $L, R$ 若 $L = R$ 則可選擇的方式有 $\frac{d_L(d_L - 1)}{2}$ 種 ---- ### 手鍊 - Subtask 3 (cond.) 若 $L + 1 = R$，則必須符合 $c_L < c_R$ 才能選擇，若 $d_L \le d_R$，則可選擇的方式有 $\Sigma_{i=1}^{d_L}(d_R - i + 1) = \frac{d_L(d_R + d_R - d_L + 1)}{2}$ 種若 $d_L > d_R$，則可選擇的方式有 $\Sigma_{i=1}^{d_R}i = \frac{d_R(d_R + 1)}{2}$ 種 ---- ### 手鍊 - Subtask 3 (cond.) 若 $L < R$ 則必須符合以下條件才能選擇： * $c_L < c_{L+1} < \ldots < c_R$ * $d_{L+1} \le d_{L+2} \le \dots \le d_R$ 有 $\min(d_L, d_{L+1}) \times (d_R - d_{R - 1} + 1)$ 種選擇方式總複雜度 $O(K^2)$ (9 + 12) / 100 ---- ### 手鍊 - Subtask 5 $d_i = 1$ → 對於連續遞增的 $c_i$，可選擇任兩顆作為 $l, r$ → 設連續遞增的 $c_i$ 長分別為 $x_1, x_2, \ldots, x_k$，則答案為 $\Sigma_{i=1}^{k}\frac{x_i(x_i - 1)}{2}$ 時間複雜度 $O(K)$ 7 / 100 ---- ### 手鍊 - Subtask 4 $c_i < c_{i+1}$ → 不須考慮顏色遞增，只須確保各段珍珠的數量先假設只有一顆珍珠也是合法的手鍊設 $dp1[i]$ 為以第 $i$ 段最左側那顆為 $l$ 的數量，則： $dp1[i] = \begin{cases} d_i &, i = K \lor d_i > d_{i+1}\\ d_i + (dp1[i+1] - d_i + 1) &, otherwise\\ \end{cases}$ ---- ### 手鍊 - Subtask 4 (cond.) 設 $dp2[i]$ 為以第 $i$ 段任意一顆為 $l$ 的數量，則： $dp2[i] = \begin{cases} \frac{d_i(d_i + 1)}{2} &, i = K\\ (dp1[i+1] + 1) \times d_i &, d_i \le d_{i+1}\\ (dp1[i+1] + 1) \times d_i + \frac{(d_i + d_{i+1} + 1)(d_i - d{i+1})}{2} &, otherwise\\ \end{cases}$ $\Sigma dp2[i]$ 即為答案時間複雜度 $O(K)$ 17 / 100 ---- ### 手鍊 - Subtask 7 將序列拆成各段連續遞增的 $c_i$，分別進行 Subtask 4 的 DP 即可求出答案 100 / 100 ---- ```cpp= #include<bits/stdc++.h> using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int K; cin >> K; int N = 0; vector<int> c(K), d(K); for (int i = 0; i < K; i++) cin >> c[i] >> d[i], N += d[i]; vector<long long> dp1(K); for (int i = K - 1; i >= 0; i--) if (i == K - 1 || c[i] > c[i + 1] || d[i] > d[i + 1]) dp1[i] = d[i]; else dp1[i] = dp1[i + 1] + 1; vector<long long> dp2(K); for (int i = K - 1; i >= 0; i--) if (i == K - 1 || c[i] > c[i + 1]) dp2[i] = dp1[i] * (dp1[i] + 1) / 2; else if (d[i] <= d[i + 1]) dp2[i] = (dp1[i + 1] + 1) * d[i]; else dp2[i] = (dp1[i + 1] + 1) * d[i + 1] + (long long)(d[i] + d[i + 1] + 1) * (d[i] - d[i + 1]) / 2; long long ans = 0; for (long long i : dp2) ans += i; cout << ans - N << '\n'; return 0; } ``` ---  快艇骰子 (Yacht) joylintp ---- ### 快艇骰子 - Subtask 2 $N=3$ → 投擲結束，選擇能得最高分的役種即可 $S=$`111111000000` → 可以選擇的役種只有前六個輸出 $1$ 到 $6$ 之中點數乘以數量最大者 3 / 100 ---- ### 快艇骰子 - Subtask 3 $N=3$ → 投擲結束，選擇能得最高分的役種即可 → 仔細實作各役種判斷 (3 + 8) / 100 ---- ### 快艇骰子 - Subtask 4 $N=2$ → 選擇要保留哪些骰子 → 枚舉剩下投擲的骰子的點數情況，計算得分期望值 → 選擇期望值最高的保留組合骰子保留組合：$2^5 = 32$ 剩餘骰子的點數情況：不超過 $6^5 = 7776$ $32 \times 7776 \approx 2.5 \times 10^5$ → 暴力枚舉 (3 + 8 + 24) / 100 ---- ### 快艇骰子骰子的順序不重要 → $[1, 2, 3, 1, 6], [1, 1, 2, 3, 6]$ 是一樣的實際上一到五顆骰子點數的組合數分別只有 $6, 21, 56, 126, 252$ 種 → 預處理每種骰子組合的出現機率 ---- ### 快艇骰子 - Subtask 5 $N=1$ → 比 $N=2$ 多重複一次選擇及投擲的過程 → 只枚舉各個組合，再將期望值乘上出現的機率骰子保留組合：$2^5 = 32$ 剩餘骰子的點數情況：不超過 $252$ $(32 \times 252)^2 \approx 6.5 \times 10^7$ → 暴力枚舉 (3 + 8 + 24 + 20) / 100 ---- ### 快艇骰子 - Subtask 7 $N=0$ → 多枚舉一次骰子的點數組合 → 儲存每個狀態 $(n, S)$ 的答案 $n$，目前投擲次數：$3$ $S$，骰子點數集合：不超過 $252$ 可能的轉移：不超過 $32 \times 252 = 8064$ $3 \times 252 \times 32 \times 252 \approx 6 \times 10^6$ 100 / 100 ---- ```cpp= #include<bits/stdc++.h> using namespace std; vector<bool> yk(12); vector<double> ans(566667, -1); vector<pair<vector<int>, double>> pos[6]; int hh(int n, vector<int> *d) { int ret = n; for (int &i : *d) ret = ret * 10 + i; return ret; } double solve(int n, vector<int> d) { if (ans[hh(n, &d)] > -1) return ans[hh(n, &d)]; if (n == 3) { int ret = 0, cnt[6] = {}, sum = 0; for (int &i : d) cnt[i - 1]++, sum += i; vector<int> vc; for (int i = 0; i < 6; i++) if (cnt[i]) vc.push_back(cnt[i]); sort(vc.begin(), vc.end(), greater<int>()); /// Aces, Deuces, Threes, Fours, Fives, Sixes for (int i = 0; i < 6; i++) if (yk[i]) ret = max(ret, cnt[i] * (i + 1)); /// Choice if (yk[6]) ret = max(ret, sum); /// 4 of a Kind if (yk[7]) if (vc[0] >= 4) ret = max(ret, sum); /// Full House if (yk[8]) if (vc[0] == 5 || (vc[0] == 3 && vc[1] == 2)) ret = max(ret, sum); /// S. Straight if (yk[9]) if ((cnt[0] && cnt[1] && cnt[2] && cnt[3]) || (cnt[1] && cnt[2] && cnt[3] && cnt[4]) || (cnt[2] && cnt[3] && cnt[4] && cnt[5])) ret = max(ret, 15); /// B. Straight if (yk[10]) if ((cnt[0] && cnt[1] && cnt[2] && cnt[3] && cnt[4]) || (cnt[1] && cnt[2] && cnt[3] && cnt[4] && cnt[5])) ret = max(ret, 30); /// Yacht if (yk[11]) if (vc[0] == 5) ret = max(ret, 50); return ans[hh(n, &d)] = ret; } if (n == 0) { double ret = 0; for (auto &p : pos[5]) ret += solve(1, p.F) * p.S; return ans[hh(n, &d)] = ret; } if (n == 1 || n == 2) { double ret = 0; for (int i = 0; i < 32; i++) { int t = i, cc = 0; vector<int> nd; for (int j = 0; j < 5; j++, t /= 2) if (t % 2) nd.push_back(d[j]), cc++; nd.resize(5); double sum = 0; for (auto &p : pos[5 - cc]) { for (int j = cc; j < 5; j++) nd[j] = p.F[j - cc]; sum += solve(n + 1, nd) * p.S; } ret = max(ret, sum); } return ans[hh(n, &d)] = ret; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); pos[0].push_back(MP(vector<int>(0), 1)); for (int i = 1; i <= 5; i++) { int ttl = 1; for (int j = 0; j < i; j++) ttl *= 6; map<vector<int>, int> cnt; for (int j = 0; j < ttl; j++) { int t = j; vector<int> v; for (int k = 0; k < i; k++) v.push_back(t % 6 + 1), t /= 6; sort(v.begin(), v.end()), cnt[v]++; } for (auto p : cnt) pos[i].push_back(MP(p.F, (double)p.S / ttl)); } int N; cin >> N; vector<int> d(5); for (int &i : d) cin >> i; string S; cin >> S; for (int i = 0; i < 12; i++) yk[i] = (S[i] - '0'); cout << fixed << setprecision(16) << solve(N, d) << '\n'; return 0; } ```