第一次社內賽題解

# 第一次社內賽題解 problem setter: 賴冠澐，黃博崇 ---  ### pA. IF倍倍數我送分題出題者:黃博崇 ----  照題目做就好了 ---- AC code ```cpp= #include <bits/stdc++.h> using namespace std; int main() { long long a, b; cin>>a>>b; if(a%b==0) cout<<a/b; else cout<<-1; } ``` ---  ### pB. 階級三角形出題者:黃博崇 ---- 其實這題根本出爛了由於題目設定有問題你不輸出前面的空格也會給過 ---- subtask1 n<=10 ~~也出爛了~~ 原本想出n<10 不用取模(%)也能拿分 ---- subtask2 無額外限制前面的空格數量會從n-1每行遞減到0 後面的數字會從1每行遞增到n ---- AC code ```cpp= #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++){ for(int j = 0; j < n - i; j++){ printf(" "); } for(int j = 1; j <= i; j++){ printf("%d", (n - i + 1)%10); } printf("\n"); } } ``` ---  ### pC. 這個月砲彈虧損86箱你有頭緒嗎出題者:黃博崇 ---- subtask1 n=1 用一維陣列就能處理以0,1,-1分別代表沒被炸到的點,被炸到的點,防空炮的點 t=1的砲彈只要考慮落下的座標就可以 t=2的砲彈用迴圈向左右延伸，遇到0就改成1，遇到-1就break 最後計算有幾個1 ---- subtask2 無額外限制用二維陣列做法和subtask1一模一樣 ---- AC code ```cpp= #include <bits/stdc++.h> using namespace std; int n, m, k, w, a, b; int g[105][105], x[105], y[105], t[105]; int main() { scanf("%d%d%d%d", &n, &m, &k, &w); for(int i = 0; i < k; i++){ scanf("%d%d%d", &x[i], &y[i], &t[i]); } for(int i = 0; i < w; i++){ scanf("%d%d", &a, &b); g[a][b] = -1; } for(int i = 0; i < k; i++){ if(g[x[i]][y[i]] == -1) continue; g[x[i]][y[i]] = 1; if(t[i] == 1){ for(int j = x[i] - 1; j > 0; j--){ if(g[j][y[i]] == -1) break; g[j][y[i]] = 1; } for(int j = x[i] + 1; j <= n; j++){ if(g[j][y[i]] == -1) break; g[j][y[i]] = 1; } } else{ for(int j = y[i] - 1; j > 0; j--){ if(g[x[i]][j] == -1) break; g[x[i]][j] = 1; } for(int j = y[i] + 1; j <= m; j++){ if(g[x[i]][j] == -1) break; g[x[i]][j] = 1; } } } int ans = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(g[i][j] == 1) ans++; } } printf("%d", ans); } ``` ---  ### pD. 字典人 ~~個人覺得題序很有創意~~ 出題者:賴冠澐 ---- 子題1：字典裡的字放進一個陣列，查詢時直接爆搜，沒找到就輸出i $O(q\times n)$ ---- 滿分：stl應用，用set或map就可以在$O(\log n)$時間查詢一個字串存不存在。注意因為字串長度<=15，所以set/map在比對時最多只會比15次，可視為常數。 $O(q\times \log n)$ ---- AC code ```cpp= #include <bits/stdc++.h> using namespace std; int main(){ int n, q; cin>>n>>q; map<string, int> fd; for(int i=0;i<n;++i){ string s; cin>>s; fd[s]=i; } for(int i=0;i<q;++i){ string s; cin>>s; if(fd.count(s)==0) cout<<i<<"\n"; } } ``` --- ### pE. 給數學們的電神怎麼變滅台題QQ <span style="color:red;">\\whitecatorz/</span> 出題者:賴冠澐 ---- 子題1：隨便乘一乘就有了 $O(n)$ ---- 子題2：從小到大枚舉每一種距離，檢查所有人是不是都能跑到這個距離。 $O(n\times k)$ k是要枚舉到多少(~~我現在發現這子題怪怪的~~) ---- 怎麼檢查? 1. 從快到慢檢查 2. 如果某人跑完還有剩，就讓給後面的人。如果跑不完，就試試看能不能利用前面剩下的跑完。如果還是不行，就return false ---- 滿分：記得基地台那題觀察到的單調性如果最短距離越長，越不可能被達到，反之越有可能被達到 ---- 對答案二分搜 $O(n\times \log k)$ k是要枚舉到多少 ---- AC code ```cpp= #include <bits/stdc++.h> using namespace std; vector<long long> v; long long n, x; bool check(long long k){ long long left=0; for(long long a:v){ if(a*x>=k) left+=x-(k+a-1)/a; else left-=(k-a*x+a-1)/a; if(left<0) return 0; } return 1; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>x; v.resize(n); for(int i=0;i<n;++i) cin>>v[i]; sort(v.begin, v.end(), greater<long long>()); long long l=1, r=1e15+1; while(l<r-1){ long long mid=(l+r)>>1; if(check(mid)) l=mid; else r=mid; } cout<<l<<"\n"; } ``` 記得開long long ---  ### pF. 低山症不小心出太水QQ 出題者:賴冠澐 ---- 子題1：枚舉n^2個區間，邊枚舉邊檢查 $O(N^2)$ ---- 滿分：其實只要記上一次比k小的位直在哪就好，然後不斷更新最長距離 $O(n)$ ---- AC code： ```cpp= #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, k; cin>>n>>k; vector<int> ar(n+1); for(int i=1;i<=n;++i) cin>>ar[i]; int j=0, ans=0; for(int i=1;i<=n;++i){ if(ar[i]<k) j=i; ans=max(ans, i-j); } cout<<ans<<NL; } ``` --- ### final standings ---- top 20: ![](https://i.imgur.com/DEy74R7.png)