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

# 111 學年度師大附中資訊學科能力競賽上機題解 --- # 工作人員 ---- ## 出題 author/setter A 林哲宇/林哲宇 B 侯欣緯/侯欣緯 C 林哲宇/侯欣緯 D 侯欣緯/侯欣緯 E 侯欣緯/侯欣緯 F 林哲宇/林哲宇 ---- ## 驗題黃致皓賴昭勳王褕立李政遠林柏瑄林煜傑王品翔鄭允臻鄭詠堯 ---  pA 特戰英豪 (Valorant) ---- ## Subtask 1 $N \le 12$ - 不用考慮攻守交換、延長賽的問題 - 一定是 Match in Progress - 數有幾個 A 跟 D 就好 ---- ## Subtask 2, 3 $N \le 24$ - 不用考慮延長賽的問題 - 比賽結束條件：其中一隊到達 13 分 - 如果到達 13 分後還有後面的局數則回報出錯 - 記得處理 9-3 詛咒 - 紀錄半場哪一隊 9 分，注意後半場攻守互換 ---- ## Subtask 2, 4 前 12 局結束時兩隊的分數皆不為 9 分 - 不用處理 9-3 詛咒 - 延長賽 - 前 24 局達到 13 分則比賽結束 - 否則判斷是否連續兩局由同一隊拿下 - 可以將延長賽視為每局都攻守交換 ---- ## Subtask 5 無額外限制 - 處理所有狀況 - 實作題（好像太難了） ---- ## 常見錯誤 - 注意若比賽尚未結束，輸出的是最後一局的進攻及防守方 - 有人輸出成下一局的了 - 可以把換局視為某一局開始的事件，不是結束後的 - 記錄 9-3 詛咒時，詛咒是在「隊伍」上 - 不是記錄在攻方或守方 ---- ```cpp= #include<bits/stdc++.h> using namespace std; //{ //#pragma gcc optimize("Ofast,unroll-loops") //#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native") //#define int long long //#define double long double #define MP make_pair #define F first #define S second #define P 3 // #define MOD 998244353 //} signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; for (int Case = 1; Case <= T; Case++) { cout << "Match " << Case << ":\n"; int N; string A, D, S; cin >> N >> A >> D >> S; int Ascr = 0, Bscr = 0, Aatk = 0, edr = 0, tag = 0; for (int i = 1; i <= N; i++) { if (i == 1 || i == 13 || i > 24) Aatk = !Aatk; if ((S[i - 1] == 'A' && Aatk) || (S[i - 1] == 'D' && !Aatk)) Ascr++; else Bscr++; if (max(Ascr, Bscr) >= 13 && abs(Ascr - Bscr) >= 2) { edr = i; break; } if (i == 12) if (Ascr == 9) tag = -1; else if (Bscr == 9) tag = 1; else; } if (edr > 0 && edr != N) cout << "something went wrong :(\n"; else { string X = "DEF", Y = "ATK"; if (Aatk) swap(X, Y); cout << X << ' ' << A << " | " << Ascr << " : " << Bscr << " | " << D << ' ' << Y << '\n'; if (edr > 0) { if (S[N - 1] == 'A') cout << "Attackers Win"; else cout << "Defenders Win"; if ((tag == -1 && Bscr > Ascr) || (tag == 1 && Ascr > Bscr)) cout << ", 9-3 Curse!"; cout << '\n'; } else cout << "Match in Progress\n"; } } return 0; } // ***** ***** * * * ***** * * ***** ***** // * * * * * * * ** * * * * // * * * ***** * * * * * * ***** // * * * * * * * * ** * * // **** ***** * ***** ***** * * * * ``` ---  pB 垃圾清理 (Garbage) ---- ~~pA 應該要被清理掉~~ （確實） ---- ## Subtask 1 $N=2$ 你只要知道第一個撿的是哪個就好 ---- ## Subtask 2 $c_1 = 3$ 對於 $1 \leq i < Q$，若 $c_i = 3$ 則 $c_{i+1} = 1$ 或 $c_{i+1} = 3$；若 $c_i = 1$ 則 $c_{i+1} = 3$ 白話文：已經撿的區間是連續的維護撿了的區間左右界往前一格移的時候就是移到左界前一格撿東西的話就是看現在在左界還右界，擴展那一邊後移到右界後一格 ---- ## Subtask 3 $N,Q \leq 1000$ 暴力模擬 ---- ## Subtask 4 linked list or set ~~相信大家在筆試時都有學會 linked list~~ ---- ```cpp= #include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define eb(a) emplace_back(a) #define ef(a) emplace_front(a) #define pob pop_back() #define pof pop_front() #define mp(a, b) make_pair(a, b) #define F first #define S second #define mt make_tuple #define gt(t, i) get(t) #define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " ";\ pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef long double ld; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; using tiii = tuple<int, int, int>; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } ll ifloor(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a < 0) return (a - b + 1) / b; else return a / b; } ll iceil(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a > 0) return (a + b - 1) / b; else return a / b; } int main(){ StarBurstStream cin.tie(0); int n, q; cin >> n >> q; vector<int> l(n), r(n); for(int i = 0; i < n; i++){ l[i] = (i - 1 + n) % n; r[i] = (i + 1) % n; } int now = 0; for(int i = 0; i < q; i++){ //cerr << "owo " << now << "\n"; int c; cin >> c; if(c == 1){ now = l[now]; continue; } else if(c == 2){ now = r[now]; continue; } cout << now + 1 << " "; l[r[now]] = l[now]; r[l[now]] = r[now]; now = r[now]; } cout << "\n"; return 0; } ``` ---  pC 彈珠汽水 (Ramune) ---- 我以為那個彈珠是用來阻止你喝太快的這題是驗題者公認最簡單題 (?) ---- ## Subtask 1 $K=2$ 喝兩個送一個 = 你喝掉一瓶時，如果還剩至少一瓶，那你會多得到一瓶不能拿來換的一開始有 $M$ 瓶，你最後會喝到 $2M-1$ 瓶 $2M-1 \geq N \implies M \geq \frac{N+1}{2}$ ---- ## Subtask 2 $K=3$ 喝三個送一個 = 你喝掉兩瓶時，如果還剩至少一瓶，那你會多得到一瓶不能拿來換的一開始有 $M$ 瓶，你最後會喝到 $M+\lfloor\frac{M-1}{2}\rfloor$ 瓶 ---- ## Subtask 3,4 $N,T \leq 100$ $N,T \leq 1000$ 暴力 ---- ## Subtask 5 $T \leq 10^5$ 注意到一開始的汽水越多，最後就可以喝越多二分搜 + 暴力模擬暴力模擬：一次喝掉 $\lfloor \frac{M}{K}K \rfloor$ 瓶複雜度 $O(T \log^2 N)$ 常數太大可能會被卡 ---- ## Subtask 6 如果你一開始有 $M$ 瓶那你最後可以喝這麼多瓶 \\[ M + \left\lceil \frac{M}{K-1} \right\rceil - 1 \\] \+ 二分搜複雜度 $O(T \log N)$ ---- Bonus: $O(1)$ solution ---- ```cpp= #include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define eb(a) emplace_back(a) #define ef(a) emplace_front(a) #define pob pop_back() #define pof pop_front() #define mp(a, b) make_pair(a, b) #define F first #define S second #define mt make_tuple #define gt(t, i) get(t) #define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef long double ld; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; using tiii = tuple<int, int, int>; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } ll ifloor(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a < 0) return (a - b + 1) / b; else return a / b; } ll iceil(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a > 0) return (a + b - 1) / b; else return a / b; } ll calc(ll K, ll c){ return iceil(c, K - 1) - 1 + c; } void solve(){ ll n, K; cin >> n >> K; ll l = 1, r = n; while(l < r){ ll mid = (l + r) / 2; if(calc(K, mid) < n) l = mid + 1; else r = mid; } cout << l << "\n"; } int main(){ StarBurstStream int T; cin >> T; while(T--) solve(); return 0; } ``` ---  pD 轉移據點 (Rotate) ---- 白話文：有敵人的點之間的邊不能走可以看成操作是在刪邊 ---- ## Subtask 1 圖是一條 $1,2,\dots,N$ 的鏈用 set 存被刪掉的邊詢問時只要看兩個點之間有沒有被刪的邊就好 ---- ## Subtask 2 $N,M,Q \leq 1000$ BFS/DFS 暴力 ---- ## Subtask 3 這是一個「不斷刪邊問連通性」的問題倒過來看就變成「不斷加邊問連通性」的問題 DSU ~~相信大家在筆試都有學會 DSU~~ ---- ```cpp= #include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define eb(a) emplace_back(a) #define ef(a) emplace_front(a) #define pob pop_back() #define pof pop_front() #define mp(a, b) make_pair(a, b) #define F first #define S second #define mt make_tuple #define gt(t, i) get(t) #define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef long double ld; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; using tiii = tuple<int, int, int>; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } ll ifloor(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a < 0) return (a - b + 1) / b; else return a / b; } ll iceil(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a > 0) return (a + b - 1) / b; else return a / b; } vector<int> dsu; int findDSU(int a){ if(dsu[a] != a) dsu[a] = findDSU(dsu[a]); return dsu[a]; } void unionDSU(int a, int b){ a = findDSU(a); b = findDSU(b); dsu[b] = a; } int main(){ StarBurstStream int n, m; cin >> n >> m; dsu.resize(n + 1); iota(iter(dsu), 0); vector<pii> e(m); vector<vector<int>> g(n + 1); for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; g[u].eb(v); g[v].eb(u); e[i] = mp(u, v); } vector<bool> black(n + 1); int q; cin >> q; vector<vector<pair<int, pii>>> qry(q); for(int i = 0; i < q; i++){ int ty; cin >> ty; if(ty == 1){ int w; cin >> w; black[w] = true; for(int j : g[w]){ if(!black[j]) continue; qry[i].eb(mp(1, mp(w, j))); } } else{ int a, b; cin >> a >> b; qry[i].eb(mp(2, mp(a, b))); } } for(pii i : e){ if(black[i.F] && black[i.S]) continue; unionDSU(i.F, i.S); } vector<int> ans(q, -1); for(int i = q - 1; i >= 0; i--){ for(auto j : qry[i]){ if(j.F == 1) unionDSU(j.S.F, j.S.S); else ans[i] = findDSU(j.S.F) == findDSU(j.S.S); } } for(int i = 0; i < q; i++){ if(ans[i] != -1){ if(ans[i] == 0) cout << "NO\n"; else cout << "YES\n"; } } return 0; } ``` ---  pE 斯普拉遁 (Splatoon) ---- 白話文：每兩個格子的交界有一個權重操作問一段區間不同色交界的權重和 ---- ## Subtask 1 $N=2$ 只有兩個格子和一個交界應該很好做 ---- ## Subtask 2 $N,Q \leq 1000$ 暴力 ---- ## Subtask 3 所有佔領都在詢問之前先把最後的顏色長相處理好（有很多方法一種方法是倒著塗配 DSU 或 set 等等或直接用 set 塗顏色） ~~如果你用線段樹的話你應該要會做滿分~~ 詢問：區間和 -> 前綴和 ---- ## Subtask 4 每次佔領塗的顏色都不一樣塗色 = 範圍中間的交界都會消失要判斷的只有兩邊有沒有其他顏色這個子題只要維護哪裡有塗過顏色就好因為前面塗的顏色一定是不一樣的 ---- ## Subtask 5 $g_i=1$ 不會寫線段樹？你還有 PBDS ---- ## Subtask 6 維護總和的部分：線段樹維護顏色的部分：線段樹 or set （兩個線段樹其實是一樣的） ---- ```cpp= #include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define eb(a) emplace_back(a) #define ef(a) emplace_front(a) #define pob pop_back() #define pof pop_front() #define mp(a, b) make_pair(a, b) #define F first #define S second #define mt make_tuple #define gt(t, i) get(t) #define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; \ pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef long double ld; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; using tiii = tuple<int, int, int>; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } ll ifloor(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a < 0) return (a - b + 1) / b; else return a / b; } ll iceil(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a > 0) return (a + b - 1) / b; else return a / b; } struct Node{ ll sum = 0, tag = -1; int sz = 0; }; int n; vector<Node> st; #define lc 2 * id + 1 #define rc 2 * id + 2 void addtag(ll v, int id){ st[id].tag = v; st[id].sum = v * st[id].sz; } void push(int id){ if(st[id].tag == -1) return; addtag(st[id].tag, lc); addtag(st[id].tag, rc); st[id].tag = -1; } void pull(int id){ st[id].sum = st[lc].sum + st[rc].sum; } void build(int L = 1, int R = n, int id = 0){ st[id].sz = R - L + 1; if(L == R) return; int M = (L + R) / 2; build(L, M, lc); build(M + 1, R, rc); } void modify(int l, int r, ll v, int L = 1, int R = n, int id = 0){ if(l <= L && R <= r){ addtag(v, id); return; } push(id); int M = (L + R) / 2; if(r <= M) modify(l, r, v, L, M, lc); else if(l > M) modify(l, r, v, M + 1, R, rc); else{ modify(l, r, v, L, M, lc); modify(l, r, v, M + 1, R, rc); } pull(id); } ll query(int l, int r, int L = 1, int R = n, int id = 0){ if(l <= L && R <= r) return st[id].sum; push(id); int M = (L + R) / 2; if(r <= M) return query(l, r, L, M, lc); else if(l > M) return query(l, r, M + 1, R, rc); else{ return query(l, r, L, M, lc) + query(l, r, M + 1, R, rc); } } int main(){ StarBurstStream cin >> n; int q; cin >> q; st.resize(4 * n); vector<ll> s(n + 1); for(int i = 1; i < n; i++) cin >> s[i]; build(); map<int, int> clr; clr.insert(mp(1, 0)); auto getcolor = [&](int x){ return prev(clr.upper_bound(x))->S; }; auto check = [&](int x){ if(x >= n || x < 1) return; int cx = getcolor(x), cy = getcolor(x + 1); if(cx != 0 && cy != 0 && cx != cy) modify(x, x, s[x]); else modify(x, x, 0); }; while(q--){ int ty; cin >> ty; if(ty == 2){ int l, r; cin >> l >> r; cout << query(l, r - 1) << "\n"; continue; } int l, r, c; cin >> l >> r >> c; if(r + 1 <= n){ int t = getcolor(r + 1); clr[r + 1] = t; } auto it = clr.lower_bound(l); while(it != clr.end() && it->F <= r){ it = clr.erase(it); } clr[l] = c; if(l < r) modify(l, r - 1, 0); check(l - 1); check(r); } return 0; } ``` ---  pF 學力測驗 (Quiz) ---- ## Subtask 3 $v_i=1$ - $1$ 跟任何數互質 - 全部都要換掉 - 換成 $2$ 就好了 - 答案為 $2N$ - **故不管一開始的 $v_i$ 長怎樣，答案都不會超過 $2N$** ---- ## Subtask 1 $N=2$ - 只有兩個數字 - 如果它們不互質，答案為 $0$ - 如果互質，則可以： - 把其中一邊換成另一邊的因數，或 - 把兩邊都換成 $2$ ---- 不管一開始的 $v_i$ 長怎樣，答案都不會超過 $2N$ - 每個數字只可能是 - 不改變 - 變為某個不超過 $2N$ 的數字 ---- ## Subtask 2 $N \le 100$ - 設 $dp1[u][j]$ 為將 $v_u$ 設為 $j$ 的且整棵子樹滿足不互質條件的花費 - 設 $dp2[u]$ 為將 $v_u$ 維持不變且整棵子樹滿足不互質條件的花費 ---- 每個 $j$（或維持原狀），對於每個子節點 $c$ 分別選擇與 $j$ 不互質的數字，並將各個子節點花費最小的可行數字加總 - 更新 $dp1[u][j]$： - 枚舉 $x$，選所有 $j$ 與 $x$ 不互質的最小 $dp1[c][x]$ - 若 $j$ 與 $v_c$ 不互質，也可以選 $dp2[c]$ - 更新 $dp2[u]$： - 枚舉 $x$，選所有 $v_u$ 與 $x$ 不互質的最小 $dp1[c][x]$ - 若 $v_u$ 與 $v_c$ 不互質，也可以選 $dp2[c]$ ---- 處理 $N$ 個節點時，對於每個子節點，我們枚舉 $O(N)$ 個可能值子節點數量總和為 $N-1$，總時間複雜度 $O(N^3)$ ---- ## Subtask 4, 5 $v_i \le N$ $p_i=i$（一條鏈） - 或許有特別的作法(？ ---- ## Subtask 6 無額外限制 - 考慮是否互質時，可以只維護 $j$ 是質數的 $dp1[u][j]$ - 一個數 $x$ 的質因數不超過 $\log{x}$ 個 - 時間複雜度下降到 $O(N^2\log{N})$ ---- ```cpp= #include<bits/stdc++.h> using namespace std; //{ //#pragma gcc optimize("Ofast,unroll-loops") //#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native") //#define int long long //#define double long double #define MP make_pair #define F first #define S second #define MOD 1000000007 //} int N; vector<bool> vis; vector<int> v, pfac, prime, par; vector<vector<int>> edge, plst, dp; void dfs(int u) { vis[u] = true; for (int &i : edge[u]) if (!vis[i]) par[i] = u, dfs(i); for (int i = 2; i <= N * 2; i++) { int ans = 0; if (v[u] != i) ans = i; for (int &j : edge[u]) { int tmp = MOD; if (__gcd(i, v[j]) > 1) tmp = min(tmp, dp[j][1]); for (int &k : plst[i]) tmp = min(tmp, dp[j][k]); ans += tmp; } for (int &j : plst[i]) dp[u][j] = min(dp[u][j], ans); } int t = v[u]; vector<int> spe; for (int &i : prime) { int cc = 0; while (t % i == 0) t /= i, cc++; if (cc) spe.push_back(i); } dp[u][1] = 0; for (int &j : edge[u]) { int tmp = MOD; if (__gcd(v[u], v[j]) > 1) tmp = min(tmp, dp[j][1]); for (int &k : spe) tmp = min(tmp, dp[j][k]); dp[u][1] = min(MOD, dp[u][1] + tmp); } for (int &j : spe) dp[u][j] = min(dp[u][j], dp[u][1]); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N, v = vector<int>(N + 1), edge = vector<vector<int>>(N + 1); for (int i = 1; i <= N; i++) cin >> v[i]; for (int i = 2; i <= N; i++) { int p; cin >> p, edge[p].push_back(i); } pfac = vector<int>(N * 2 + 1, 1); for (int i = 2; i <= N * 2; i++) { if (pfac[i] == 1) prime.push_back(i); for (int &j : prime) { if (i * j > N * 2) break; pfac[i * j] = j; if (i % j == 0) break; } } plst.resize(N * 2 + 1); for (int i = 2; i <= N * 2; i++) { int t = i; while (pfac[t] > 1) plst[i].push_back(pfac[t]), t /= pfac[t]; plst[i].push_back(t); sort(plst[i].begin(), plst[i].end()), plst[i].resize(unique(plst[i].begin(), plst[i].end()) - plst[i].begin()); } vis = vector<bool>(N + 1); par = vector<int>(N + 1); dp = vector<vector<int>>(N + 1, vector<int>(N * 2 + 1, MOD)); dfs(1); int ans = MOD; for (int i = 1; i <= N * 2; i++) ans = min(ans, dp[1][i]); cout << ans << '\n'; return 0; } // ***** ***** * * * ***** * * ***** ***** // * * * * * * * ** * * * * // * * * ***** * * * * * * ***** // * * * * * * * * ** * * // **** ***** * ***** ***** * * * * ```