建中資訊校內賽題解

# 113學年度建國中學校內資訊能力競賽初試題解 ---- ## 難度 $A<B<C \approx D \approx E$ --- # pA Hangman with Artificial Idiot ## Setter : pacybwoah ---- ### Subtask 1：$A=B$ 字串都一樣的時候會發生什麼事情？ ---- ### Subtask 1：$A=B$ 假設大家的字串都是 sass A : sass B : sass ---- ### Subtask 1：$A=B$ 你猜了 s 之後 A : sass B : sass ---- ### Subtask 1：$A=B$ 你猜了 a 之後 A : sass B : sass ---- ### Subtask 1：$A=B$ 不管怎麼樣都會平手 => cout << "No\n"; ---- ### Subtask 2：$n, m \leq 100$，$A,B$ 由 a~h 的小寫字母組成對每種猜字母的方法用 next_permutation 暴力模擬，複雜度 $O(n \cdot |c|!)$ ---- ### Subtask 3：無特別限制模擬遊戲的過程中應該會發現一件事：字母出現的次數與答案沒關係，只需要在乎有沒有出現 ---- ### Subtask 3：無特別限制如果所有出現在 $A$ 裡的字母都出現在 $B$ 中，那當你猜完 $B$ 的所有字母，$A$ 的所有字母也會被猜中，因此不可能贏 ---- ### Subtask 3：無特別限制如果一個字母出現在 $A$ 內但沒有出現在 $B$ 內，那你猜中 $B$ 時 $A$ 可能有字母還沒被猜到，因此有可能贏 ---- ### Subtask 3：無特別限制開一個布林陣列紀錄字母有沒有出現在兩個字串並檢查上述條件，複雜度 $O(n + |c|)$ ---- ### Code ``` #include<iostream> #include<vector> #include<string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; string a, b; cin >> a >> b; vector<bool> visa(26), visb(26); for(int i = 0; i < n; i++) visa[a[i] - 'a'] = 1; for(int i = 0; i < m; i++) visb[b[i] - 'a'] = 1; for(int i = 0; i < 26; i++){ if(visa[i] == 1 && visb[i] == 0){ cout << "Yes\n"; return 0; } } cout << "No\n"; return 0; } ``` ---- --- # pB 小祥的生日禮物 ## Setter : becaido ---- ### Subtask 1：$a_i>0$（$1\le i\le n$） ---- 可以選 $1$，直接把所有點都標記起來。這樣子字典序會是最大的，因為不管怎麼選都沒辦法超過總和。 ---- ### Subtask 2：$a_i=0$（$1\le i\le n$） ---- 注意到 $[0,0,0,0]$ 的字典序大於 $[0,0,0]$。也就是說，$0$ 越多字典序越大。 ---- 如果從 $n$ 開始標記到 $1$，那每次都只會標記到自己，最後的陣列中會有 $n$ 個 $0$，字典序最大。 ---- ### Subtask 3：恰好有一個 $i$（$1\le i\le n$），使得 $a_i>0$ ---- 想要把 $a_i$ 標記走，只能選他或是他的因數。因為留下來越多 $0$ 越好，所以應該標記 $a_i$，再把剩下還沒被標記的 $0$ 從大到小標記。 ---- ### Subtask 4：無特別限制 ---- 因為可以直接選 $1$ 標記走所有數字，所以第一個選的數字一定要能把所有大於 $0$ 的數字都標記走！ ---- 解法 1：對於一個數字來說，只要被選的數字是他的因數，這個數字就會被標記到。因此，第一個選的數字一定會是所有大於 0 的數字位置的最大公因數。 ---- 使用內建的 gcd 函數，可以在 $O(n+logn)$ 的時間內得到第一個數字。接著再輸出 $n - \left \lfloor{\frac{n}{gcd}}\right \rfloor$ 個 $0$ 就可以了。 ---- 解法 2：枚舉所有數字當第一個選的數字，檢查他的倍數總和是否等於全部數字的總和。時間複雜度為 $O(n + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n})$ = $O(nlogn)$ ---- ### Code ``` #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n; int g, sum, a[N]; int main() { ios::sync_with_stdio(false), cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { if (a[i] > 0) { g = gcd(g, i); sum += a[i]; } } if (g == 0) { cout << n << '\n'; for (int i = 1; i <= n; i++) cout << 0 << " \n"[i == n]; return 0; } int zero = n - n / g; cout << zero + 1 << '\n'; cout << sum; for (int i = 1; i <= zero; i++) cout << " 0"; cout << '\n'; } ``` --- # pC 見習魔法師宜恩 ## Setter : owoovo ---- ## Subtask 1 $N,a_i$很小發現到會減少時間一定是把$x+1,x,x,...,x,x+1$中間的$x$變成$x+1$(填洞) 而且這樣都是減少兩單位的時間 ---- 把可以補的洞切成一段一段 ![image](https://hackmd.io/_uploads/ryEkszT2A.png) ---- 把每一段照花費排序從花費小的開始拿 ---- ## 真的嗎真的因為在其他洞上面的洞一定不會比較小 ---- 最多會有$O(cN)$個洞複雜度：$O(cN\log{cN})$ 如果沒有好好找洞會被卡記憶體 ---- ## Subtask 2 只有一個大洞一定會從下面填上來 ---- 要找到最大的$x$讓$\displaystyle\sum_{i=1}^N{\max(0, x-a_i)}\leq K$ 把$a_i$排序後二分搜或好好數數 ---- ## full 現在的問題在洞太多了沒有辦法一個一個找(存) 有沒有辦法一起找(存)？ ---- 以$a_i$當左邊的洞在遇到一個$\geq a_i$的人之後就沒有了單調stack! 以stack存現在還能當左邊的人每遇到新的一座山就把一些洞的(寬度,高度)存起來把他們照寬度排序然後好好加就做完了! 複雜度：$O(N\log{N})$ ---- ## Code ``` #include<bits/stdc++.h> #define ll long long #define F first #define S second using namespace std; ll n,k,a[1000010]; vector<pair<ll,ll>> use; int main(){ cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; ll ans=0; for(int i=1;i<n;i++){ ans+=abs(a[i]-a[i+1]); } stack<pair<ll,ll>> sk; for(int i=1;i<=n;i++){ while(!sk.empty()&&a[i]>=sk.top().F){ auto [val,pos]=sk.top(); sk.pop(); if(!sk.empty()){ auto [val2,pos2]=sk.top(); use.push_back({i-pos2-1,min(val2,a[i])-val}); } } sk.push(make_pair(a[i],i)); } sort(use.begin(),use.end()); for(auto [val,t]:use){ if(val*t<=k){ k-=val*t; ans-=t*2; }else{ ll T=k/val; k-=val*T; ans-=T*2; break; } } cout<<ans<<"\n"; } ``` --- # pD 電梯難題 ## Setter : pacybwoah ---- 為了方便，我們讓$s_0=e_0=0$ ---- ## Subtask 1 $k=1$ 國中數學算$\displaystyle\sum_{i=1}^n(\mid s_{i}-e_{i-1} \mid+\mid e_i-s_i\mid)$ ---- ## Subtask 2 $n\leq 20$ 枚舉所有給兩座電梯的分法再分別把他們當作$k=1$ 複雜度：$O(n\times 2^n)$ ---- ## Subtask 3 $n\leq 5000$ 發現到在送完第$i$組人後一定有一座電梯在$e_i$ 考慮定義$dp$狀態 $dp_{i,j}$為載完前$i$組人，電梯在$e_i,e_j$需要的最小時間 ---- $$ dp_{i,j} = \begin{cases} dp_{i-1,j}+\mid s_{i}-e_{i-1} \mid+\mid e_i-s_i\mid & \text{if } j \neq i-1 \\ \min\{dp_{i-1,k}+\mid s_{i}-e_{k} \mid+\mid e_i-s_i\mid\} &\text{if } j=i-1 \end{cases} $$ 轉移總共只有$O(n^2)$項 ---- ## full 我們再來觀察一下dp式狀態太多了! 換一種寫法試試看發現到如果第$i,i-1$組人用不同電梯它們的位置會是$e_i,e_{i-1}$ 我們設$dp_i$為第$i,i-1$組人用不同電梯時接完前$i$組最少的時間 ---- ## dp式 $dp_i=\min_{j<i}\{dp_j+\displaystyle \sum_{k=j+1}^{i} \mid e_{k}-s_{k} \mid$ $+\displaystyle\sum_{k=j+1}^{i-1}\mid s_{k}-e_{k-1} \mid+\mid s_i-e_{j-1}\mid\}$ ---- 大家都有$\mid e_i-s_i\mid$ 把$\displaystyle\sum_{i=1}^n\mid e_i-s_i\mid$拿出來，算完dp後再加回去要區間的加$\mid e_i-s_{i-1}\mid$，讓$\displaystyle pre_i=\sum_{j=1}^i{\mid s_j-e_{j-1} \mid}$ 接著用前綴和算 ---- ## 現在的dp式 $dp_i=\min_{j<i}\{dp_j +pre_{i-1}-pre_j+\mid s_i-e_{j-1}\mid\}$ 把$dp'_i$設為$dp_i-pre_i$ $dp'_i=\mid s_i-e_{i-1}\mid+\min_{j<i}\{dp'_j +\mid s_i-e_{j-1}\mid\}$ ---- 把絕對值拆開來 $$ dp'_i = \mid s_i-e_{i-1}\mid+\min_{j<i}\begin{cases} dp'_j-e_{j-1}+s_i & \text{if } e_{j-1} \leq s_i \\ dp'_j+e_{j-1}-s_i & \text{otherwise. } \end{cases} $$ 對$e_i$開兩顆線段樹存$dp'_i-e_{i-1}$和$dp'_i+e_{i-1}$分別的最小值 (要記得離散化) 這樣就做完了! 複雜度：$O(n\log n)$ ---- ## 還有一件事發現到轉移的詢問其實是一個前(後)綴 BIT! ---- ## Code ``` #include<iostream> #include<vector> #include<algorithm> #include<utility> #include<cmath> using namespace std; typedef long long ll; const ll inf = 1e18; struct BIT{ int n; vector<ll> bit; BIT(int _n){ n = _n; bit.resize(n + 1); fill(bit.begin(), bit.end(), inf); } void modify(int pos, ll num){ while(pos <= n){ bit[pos] = min(bit[pos], num); pos += pos & -pos; } } ll query(int pos){ ll ans = inf; while(pos > 0){ ans = min(ans, bit[pos]); pos -= pos & -pos; } return ans; } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> k >> n; vector<pair<ll, ll>> vec(n + 1), cp(n + 1); vector<ll> cc; for(int i = 1; i <= n; i++){ cin >> vec[i].first >> vec[i].second; cc.push_back(vec[i].first); cc.push_back(vec[i].second); } cc.push_back(0); sort(cc.begin(), cc.end()); cc.resize(unique(cc.begin(), cc.end()) - cc.begin()); int sz = cc.size(); for(int i = 1; i <= n; i++){ cp[i].first = lower_bound(cc.begin(), cc.end(), vec[i].first) - cc.begin() + 1; cp[i].second = lower_bound(cc.begin(), cc.end(), vec[i].second) - cc.begin() + 1; } vec[0] = make_pair(0, 0); ll ans = 1e18, last = 0; if(k == 1){ ans = 0; for(auto &[s, e]: vec){ ans += llabs(s - last); ans += llabs(e - s); last = e; } cout << ans << "\n"; return 0; } for(auto &[s, e]: vec) last += llabs(e - s); vector<ll> suf(n + 1), dp(n + 1); suf[n] = llabs(vec[n].first - vec[n - 1].second); for(int i = n - 1; i > 0; i--) suf[i] = suf[i + 1] + llabs(vec[i].first - vec[i - 1].second); dp[1] = vec[1].first; BIT cis(sz), trans(sz); cis.modify(1, dp[1]); trans.modify(sz, dp[1]); ll rest = 0; for(int i = 2; i <= n; i++){ dp[i] = min(cis.query(cp[i].first) + vec[i].first, trans.query(sz + 1 - cp[i].first) - vec[i].first) + rest; rest += llabs(vec[i].first - vec[i - 1].second); cis.modify(cp[i - 1].second, dp[i] - vec[i - 1].second - rest); trans.modify(sz + 1 - cp[i - 1].second, dp[i] + vec[i - 1].second - rest); } ans = dp[n]; for(int i = 1; i < n; i++) ans = min(ans, dp[i] + suf[i + 1]); cout << ans + last << "\n"; } ``` --- # pE 火車難題 ## Setter : PCC ---- ### 題目好長不想看？簡短題敘：有一個邊權都是 1 的無向圖，邊上會有一些泡泡紙，你想要在走最短距離的情況下踩最多張泡泡紙。問從每個點到 $n$ 最多能踩幾張泡泡紙。 ---- ### 題目好長不想看？但是不是所有邊都可以走，轉彎需要花錢。對於每個點來說，都會有一個指針指向第一條邊，想要往別條邊走需要花錢。每個點目前有 $c_i$ 元，可以花 $a_i$ 元把指針往後搬 $x_i$ 格，或花 $b_i$ 元把指針往後搬 $y_i$ 格 ---- ### Subtask 1：$a_i = b_i > c_i$ ---- 完全不能移指針！那有些邊就完全不能用到了。不是第 $1$ 條邊的邊都可以刪掉。 ---- 「所有到終點的最短路」其實就是把邊反轉之後的「所有從起點開始的最短路」。可以 BFS，過程中順便紀錄最多能踩幾張泡泡紙。複雜度 $O(n + m)$ ---- ### Subtask 2、3：$x_i = y_i = 1,b_i = a_i$ ---- 每次可以把指針往後移一格，最多可以往後移 $\left \lfloor{\frac{c_i}{a_i}}\right \rfloor$ 格。一樣把移不到的邊都拔掉，在剩下的圖上跑 BFS。 ---- 值得注意的是，每個點的指針是各自獨立的。接下來都會對每個點各自算出哪些邊可以用，哪些邊不能用，把不能用的邊刪掉後再跑 BFS。 ---- ### Subtask 4：$a_i = b_i,x_i = y_i$ ---- 只有一個指針。可以一直把指針往後移 $x_i$ 格，把指針可以移到的邊都標記起來。如果指針移到已經走過的邊，就代表陷入循環，可以跳出。 ---- 因為走完所有邊之前一定會陷入循環，所以每個點只會花 $O(d_i)$ 的時間確認。總複雜度為 $O(n + m)$ ---- ### Subtask 5、6：無其他限制 ---- 有兩個指針。如果我們對所有邊算出「把指針移到這裡的最小花費」，就知道哪些邊可以用了。 ---- 假設指針現在指向第 $p$ 條邊，那我可以花 $a_i$ 讓他指向第 $(p + x_i - 1) \text{ mod } d_i + 1$ 條邊，或是花 $b_i$ 讓他指向第 $(p + y_i - 1) \text{ mod } d_i + 1$ 條邊有沒有覺得很像什麼東西？ ---- 最短路！對每個車站來說，可以幫所有軌道建一個點，每個點建兩條邊出去，分別代表用 $a_i$ 跟用 $b_i$ 的情況。把一號軌道的距離設為 $0$ ，跑 Dijkstra 之後就可以把距離 $> c_i$ 的邊刪掉。最後在新圖上跑 BFS 就是答案了。複雜度 $O(m\log m + n)$ ---- ### Code ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int mxn = 2e5+10; const ll inf = 2e18; vector<pii> all[mxn]; vector<pii> paths[mxn]; int a[mxn],b[mxn],x[mxn],y[mxn]; ll c[mxn]; int N; ll dist[mxn]; bool vis[mxn]; ll ans[mxn]; void calc(int id){ int d = all[id].size(); priority_queue<pll,vector<pll>,greater<pll>> pq; fill(dist,dist+d,inf); fill(vis,vis+d,0); dist[0] = 0; pq.push(pll(dist[0],0)); while(!pq.empty()){ auto [_,now] = pq.top();pq.pop(); if(vis[now])continue; vis[now] = true; int nxt = (now+x[id])%d; if(!vis[nxt]&&dist[nxt]>dist[now]+a[id]){ dist[nxt] = dist[now]+a[id]; pq.push(pll(dist[nxt],nxt)); } nxt = (now+y[id])%d; if(!vis[nxt]&&dist[nxt]>dist[now]+b[id]){ dist[nxt] = dist[now]+b[id]; pq.push(pll(dist[nxt],nxt)); } } for(int i = 0;i<d;i++){ auto [nxt,dis] = all[id][i]; if(dist[i]>c[id])continue; paths[nxt].push_back(pii(id,dis)); } return; } namespace BFS{ pll dp[mxn]; void GO(int s){ queue<int> q; for(int i = 1;i<=N;i++)dp[i] = pll(-1,-1); dp[s] = pll(0,0); q.push(s); while(!q.empty()){ auto now = q.front(); q.pop(); for(auto [nxt,w]:paths[now]){ if(dp[nxt].fs == -1){ dp[nxt] = pll(dp[now].fs+1,dp[now].sc+w); q.push(nxt); } else if(dp[nxt].fs == dp[now].fs+1)dp[nxt].sc = max(dp[nxt].sc,dp[now].sc+w); } } for(int i = 1;i<=N;i++)ans[i] = dp[i].sc; return; } } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N; for(int i = 1;i<=N;i++){ int d; cin>>d; while(d--){ pii p; cin>>p.fs>>p.sc; all[i].push_back(p); } } for(int i = 1;i<=N;i++)cin>>a[i]; for(int i = 1;i<=N;i++)cin>>x[i]; for(int i = 1;i<=N;i++)cin>>b[i]; for(int i = 1;i<=N;i++)cin>>y[i]; for(int i = 1;i<=N;i++)cin>>c[i]; for(int i = 1;i<=N;i++)calc(i); BFS::GO(N); for(int i = 1;i<=N;i++)cout<<ans[i]<<'\n'; return 0; } ```