# 112學年度建國中學校內資訊能力競賽 初試題解 --- # pA 書櫃整理 ## Setter : PCC ---- 應該可以發現字串根本不會用到吧? ---- ## Subtask 1 : $N \le 20$ ---- 可能拿來練習一下位元枚舉之類 ---- ## Subtask2 : 無其他限制 ---- 可以將輸入進來的所有時間都轉成從 $0$ 年開始總共經過了多久，答案就是 $\le M \times 12+K$ 的數字數量，複雜度 $O(N)$ ~~當然，排序之後二分搜或者是對值域開線段樹之類的都可以~~，複雜度 $O(N\log N)$ ---- 官解 ```!= #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 int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n; cin>>n; int tar; int arr[n]; for(auto &i:arr){ string s; int a,b; cin>>s>>a>>b; i = a*100+b; } int a,b; cin>>a>>b; tar = a*100+b; int ans = 0; for(auto &i:arr)ans += (tar>=i); cout<<ans; } ``` --- # pB 煎鍋貼 ## Setter : alvingogo ---- # Subtask 1 位元枚舉 ---- # Subtask 2 從左到右掃，假設現在的左界是 l，枚舉起鍋時間跟他可以延伸到的右界 r 就可以了 複雜度 O(nA) ---- # Subtask 3 承上，對於左界 l 可以維護目前的起鍋時間區間然後想辦法擴展右界 複雜度 O(n) --- # pC 進擊的俄羅斯娃娃 ## Setter : becaido ---- ## Subtask 1 : $n\leq 10^3$ ---- 枚舉每個 $k$，每次 $O(n)$ 算 $S$ 複雜度 $O(n^2)$ ---- ## Subtask 2 : $a_i\leq a_{i+1}$ ---- $a$ 是一個遞增數列 ---- 對於一個固定的 $k$，最小值 $S$ 只會發生在 $a_0$ 或 $b_0$ 的地方 ---- 每次只要檢查這兩個地方 複雜度 $O(n)$ ---- ## Subtask 3 : 無其他限制 ---- 如果不知道怎麼求最大的 $S$ 怎麼辦？ ---- 可以對 $S$ 二分搜！ ---- 發現對於一個 $a_i$，會讓總和 $\geq S$ 的 $k$ 會是一段或兩段連續的區間 形如 $[l,r]$ 或 $[0,r],[l,n-1]$ ---- $S$ 為合法的解若且為若存在至少一個 $k$ 同時被 $n$ 個區間包含 ---- 找被幾個區間包含的方法： 對 $[l,r]$ 或 $[0,r],[l,n-1]$ 加 $1$ 可以利用差分 ---- 對區間 $[l,r]$ 加 $1$ 相當於 對差分陣列的 $d_l$ 加 $1$，$d_{r+1}$ 減 $1$ ---- 複雜度 $O(n\log n\log C)$ 的做法： ---- 對每個 $a_i$ 二分搜（lower_bound）出 $b$ 對應到的區間 最後檢查是否有位置被加到 $n$ 次 ---- 複雜度 $O(n(\log n+\log C))$ 的做法： ---- 發現當 $a$ 的值遞增， $b$ 對應到區間的左界會越來越左邊 ---- 可以先將 $a$ 排序好， 利用雙指針找對應到 $b$ 的區間 ---- [$O(n(\log n +\log C))$ solution](https://ideone.com/vWES7T) --- # pD 拆譜問題 ## Setter : PCC ---- ## Subtask 1 : $N \le 15$ ---- 枚舉要用多少隻手指，再枚舉每個時間點各個手指的位置。 ---- ## Subtask 2 : $M \le 4$ ---- cout<<1; ---- ## Subtask 3 : $M \le 6$ ---- 稍微觀察一下發現只要用兩隻手指，所以如果試出來一隻手指不行就表示答案是2 可以令 $DP_{i,j}$ 表示目前到第 $i$ 列的譜面，手指在 $j$ 的位置是否有解。 則$dp_{i,j} =$ $(dp_{i-1,j-1}|dp_{i-1,j}|dp_{i-1,j+1})$ &(按在j是否可以成功打擊該列) 感性理解為何最多用兩隻: $m = 6$ 時，將兩根手指放在 (2,4) ---- 但是被假解唬爛過了... ---- ```!= ... int main(){ cin.tie(0),ios::sync_with_stdio(0); cin >> t; while(t--){ int maxamnt=0,cnt=0; cin >> n >> m; while(n--){ cnt=0; cin >> ins; for(int i=2;i<m;i++){ if(ins[i-2]=='*'&&ins[i-1]=='-'&&ins[i]=='-') cnt++; } if(ins[0]=='-'&&ins[1]=='-') cnt++; maxamnt=max(maxamnt,cnt); } cout << maxamnt << '\n'; } uwu } ``` ---- ## Subtask 4 : 無其他限制 ---- 可以證明最多需要三隻手指 感性證明: $m=8$ 時一隻手指在中間其中一排，剩下兩根一根顧左邊另一根顧右邊，左右兩邊都可以當成 $m \le 4$ 的譜面 ---- 所以要寫三維版的DP跟二維版的DP跟一維的DP? ---- 檢查用一根手指與兩根手指是否可以成功就好。 如果一隻手指有解:cout<<1 如果兩隻手指有解:cout<<2 否則cout<<3 ---- 定義 $dp_{i,l,r}$表示打到第 $i$ 列的時候雙手分別在 $l,r$ (若 $r = -1$表示要一隻手指打) 則 $dp_{i,l,r} = orsum_{-1\leq d1,d2 \leq 1}(dp_{i-1,l+d1,r+d2})$ & 按在 $l,r$ 是否可以成功打擊該列。 這樣做可以同時算一隻手指與兩隻手指的答案。 ---- 官解 ```!= #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 const int mxn = 9; bool dp[2][mxn][mxn]; vector<pii> keys; vector<pii> dx; int n,m; inline bool check(pii &p){ if(p.fs == 0&&p.sc == 0)return false; if(p.fs<0||p.sc<0||p.fs>m||p.sc>m)return false; return true; } inline bool cover(int l,int r){ int tmp = 0; for(int i = 0;i<keys.size();i++){ if(keys[i].fs<=l&&keys[i].sc>=l)tmp++; else if(keys[i].fs<=r&&keys[i].sc>=r)tmp++; } return tmp == keys.size(); } void solve(){ cin>>n>>m; bool roll = 0; for(int i = 0;i<=m;i++)for(int j = 0;j<=m;j++)dp[roll][i][j] = 1; for(int i = 0;i<n;i++){ string s; cin>>s; s = "#"+s; roll ^= 1; keys.clear(); for(int j = 1;j<=m;j++){ if(s[j] == '-'){ if(keys.empty()||keys.back().sc+1 != j)keys.push_back({j,j}); else keys.back().sc = j; } } memset(dp[roll],0,sizeof(dp[roll])); for(int j = 0;j<=m;j++){ for(int k = 0;k<=m;k++){ bool flag = false; for(auto &d:dx){ pii tmp = {j+d.fs,k+d.sc}; if(j == 0&&tmp.fs != j)continue; if(k == 0&&tmp.sc != j)continue; if(check(tmp)&&dp[roll^1][tmp.fs][tmp.sc])flag = true; } if(flag&&cover(j,k))dp[roll][j][k] = true; } } /* for(auto &j:keys)cout<<j.fs<<' '<<j.sc<<',';cout<<endl; for(int j = 0;j<=m;j++){ for(int k = 0;k<=m;k++){ cout<<dp[roll][j][k]; } cout<<endl; } cout<<endl; */ } for(int i = 1;i<=m;i++){ if(dp[roll][0][i]){ cout<<"1\n"; return; } } for(int i = 1;i<=m;i++){ for(int j = 1;j<=m;j++){ if(dp[roll][i][j]){ cout<<"2\n"; return; } } } cout<<"3\n"; return; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); for(int i = -1;i<=1;i++)for(int j = -1;j<=1;j++)dx.push_back({i,j}); int t;cin>>t; while(t--)solve(); } ``` --- # pE 小七的變身魔法 ## Setter : PCC ---- ## Subtask 1 : $a_i,S$ 皆為質數 如果 $a_i = S$那答案就是0 因為小七不可能可以變身 ---- ## Subtask 2 : $a_i,S$ 的因數數量 $\le$ 4 ---- 以防萬一有人只想到怎麼質因數分解卻想不到建圖 ---- ## Subtask 3 : $a_i,S \leq 10 ^ 6$ ---- 建圖，將每個數字因數分解之後，建一張二分圖，左側為 $1,2,3,...n+1$，右側為因數。 建 $a_i(i \neq n+1)$ 的因數往 $i$ 邊權 $b_i$ 的邊，而反向建邊權為 $0$ 的邊。 也建 $S$ 向其因數邊權為 $0$ 的邊 。之後由 $S$ 開始跑最短路即可。 另一個建法是將每個數字的因數兩兩建邊，再對 $S$ 的所有因數距離設成0跑多點源最短路。 ---- 但是這樣還是不夠快 ---- 觀察到不用對所有因數都建邊，只要建質因數就好。複雜度 $O(NlogClogN)$ ---- ## Subtask 4 : 無其他限制 瓶頸應該在是質因數分解上，所以來優化一下。 ---- 觀察到枚舉質因數時，for 迴圈會跑過很多合數，是不必要的。 然後一個數字比 $\sqrt C$ 大的質因數只有一個，所以枚舉質數就好 複雜度 $O(NlogClogN + \frac {\sqrt C \times N}{ln(N)})$ ---- 然後Subtask 3 測資太弱了.... 貌似沒有卡到大質數測資 ---- 然後有人用 pollard rho 過 :EEEEE: ---- 官解 ```!= #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 const int mxn = 5e4+10; const int MXN = sqrt(1e9)+1; const ll inf = 1e18; int arr[mxn]; bitset<MXN> isp; vector<int> primes; vector<int> all; vector<int> facs[mxn]; vector<pll> paths[mxn*12]; ll dist[mxn*12],cost[mxn]; int n; void DIJKSTRA(int start){ fill(dist,dist+mxn*12,inf); dist[start] = 0; priority_queue<pll,vector<pll>,greater<pll>> pq; pq.push({dist[start],start}); while(!pq.empty()){ auto now = pq.top(); pq.pop(); if(now.fs != dist[now.sc])continue; for(auto nxt:paths[now.sc]){ if(dist[nxt.fs]>dist[now.sc]+nxt.sc){ dist[nxt.fs] = dist[now.sc]+nxt.sc; pq.push({dist[nxt.fs],nxt.fs}); } } } return; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); for(int i = 2;i<MXN;i++){ if(!isp[i]){ primes.push_back(i); for(int j = i+i;j<MXN;j+=i)isp[j] = true; } } cin>>n; for(int i = 1;i<=n;i++)cin>>arr[i]; for(int i = 1;i<=n;i++)cin>>cost[i]; cin>>arr[n+1]; for(int i = 1;i<=n+1;i++){ for(auto &j:primes){ if(j>arr[i])break; if(arr[i]%j == 0){ facs[i].push_back(j); while(arr[i]%j == 0){ arr[i]/=j; } } } if(arr[i]>primes.back())facs[i].push_back(arr[i]); for(auto &j:facs[i])all.push_back(j); } all.push_back(0); sort(all.begin(),all.end()); all.erase(unique(all.begin(),all.end()),all.end()); for(int i = 1;i<=n+1;i++){ for(auto &j:facs[i]){ auto rp = lower_bound(all.begin(),all.end(),j)-all.begin(); int lp = all.size()+i; if(i != n+1)paths[rp].push_back({lp,cost[i]}); paths[lp].push_back({rp,0}); } } DIJKSTRA(all.size()+n+1); assert(all.size()+n+1<mxn*12); for(int i = 1;i<=n;i++){ ll ans = inf; for(auto &j:facs[i]){ int p = lower_bound(all.begin(),all.end(),j)-all.begin(); ans = min(ans,dist[p]); } if(ans==inf)cout<<"-1 "; else cout<<ans<<' '; } return 0; } ``` --- # 鞭屍 ----  上傳程式碼，不是exe ---- ## pA : 沒用到的資訊可以不用存 不然就是開全域變數 @很多人 ```!= #include<iostream> using namespace std; int main(){ int n,m,k,ans=0; string book[10000]; int year[10000]; int mon[10000]; cin>>n; for(int i=0;i<n;i++){ cin>>book[i]>>year[i]>>mon[i]; } cin>>m>>k; } ``` ---- ckpre_044 ???? ``` != фдф ``` ---- ... ckpre083 ```!= ... #define PCCORZ true // $$$$ $$$$ $$$$ $$$ $$$$ $$$$$ // $ $ $ $ $ $ $ $ $ // $$$$ $ $ $ $ $$$$ $ // $ $ $ $ $ $ $ $ // $ $$$$ $$$$ $$$ $ $ $$$$$ const int MXN = 100005; ... ``` ---- ckpre076 先cin>>n... ``` != #include <bits/stdc++.h> using namespace std; int main(){ long long n; vector <long long> a(n), b(n); cin >> n; for (int i=0;i<n;i++){ cin >> a[i]; } for (int i=0;i<n;i++){ cin >> b[i]; } long long S = -1, s = 100000000000000000; long long sum = 0; for (int i=0;i<n;i++){ for (int j=0;j<n;j++){ sum = a[(i+j)%n]+b[j]; s = min(s,sum); } S = max(S,s); s = 100000000000000000; } cout << S << endl; } ``` ---- 把judge當成編譯器